Tri appliqué à un tableau à 2 dimensions basé sur la 2nde dimension [Résolu]

Messages postés
2
Date d'inscription
mardi 8 novembre 2011
Dernière intervention
8 novembre 2011
- - Dernière réponse : cptpingu
Messages postés
3830
Date d'inscription
dimanche 12 décembre 2004
Dernière intervention
19 novembre 2018
- 9 nov. 2011 à 00:40
Bonjour à tous.
Premièrement, j'espère que ce message est au bon endroit (qui m'a parut le plus logique, bien que l'algorithmique soit de mise).
Deuxièmement, je vous expose mon problème (en C++, si possible) :
- Je dispose d'un tableau d'entiers de dimension n*m rempli (int[10][3], par exemple)
- Je dois ensuite le trier par valeur croissante selon la valeur contenue dans tab[x][2] (les valeurs contenues dans tab[x][0] et tab[x][1] doivent suivre lors du tri, vu qu'elles sont associées à tab[x][2]).

J'ai donc essayé de recourir aux fonctions de la STL sans succès, à adapter un tri rapide, fusion, bulles, sans plus de succès.
Étant passablement mauvais en algorithmique et ayant passé un certain temps sur le problème, je me tourne vers vous en espérant ne pas passer pour un c*n.

Sinon, un petit trou de mémoire qui pourrait être comblé : comment un tel tableau est-il représenté en mémoire?
Mettons qu'on veut accéder à la valeur tab[4][2], comment la récupérer via les pointeurs? (tab+4+m+2? tab+4+2?...)


D'avance, merci à vous!
Afficher la suite 

Votre réponse

6 réponses

Meilleure réponse
Messages postés
181
Date d'inscription
mardi 6 avril 2010
Dernière intervention
7 janvier 2012
3
Merci
Salut, sans passer par les fonctions de la stl (ce qui n'est pas forcément une bonne chose...) ce petit bout de code pourra peut-être t'aider, il crée un tableau, affiche un élément par opérateurs [] et par pointeurs, puis le trie le tableau.
Par contre la méthode de tri est sûrement moins performante que celle que te donne CptPingu avec std::sort, ici c'est juste un truc improvisé, les colonnes sont triées 2 à 2 jusqu'à ce que ce ne soit plus possible, puis ça passe à la ligne suivante:


#include 


int main()
{
    bool tri;
    int tab[5][4];
    for (int i=0; i < 5; i++)
        for (int j=0; j < 4; j++)
              tab[i][j] = (i*j)%10; // Pour remplir le tableau un peu au hasard...

    tab[3][2] = -1; // met -1 ligne 3 colonne 2
    std::cout << "\n";

    for (int i=0; i < 5; i++)
    {
        for (int j=0; j < 4; j++)
              std::cout << tab[i][j] << " ";
         std::cout << "\n";
    }


    std::cout << "\nAvec pointeurs : " << *(*(tab + 3) + 2);  // *(*(tab + ligne) + colonne)
    std::cout << "\nAvec operateurs [] : " << tab[3][2]; // cette ligne comme la précédente affiche -1.



    for (int i=0; i < 5; i++) // pour le tri
    {
        tri=true;
        while (tri)
        {
            tri=false;
            for (int j=0; j < 4 - 1; j++)
            {

                if (tab[i][j] > tab[i][j+1])
                {
                    tri=true;
                    int temp = tab[i][j];
                    tab[i][j] = tab[i][j + 1];
                    tab[i][j + 1] = temp;
                }
            }
        }

    }

    std::cout << "\n\n";
    for (int i=0; i < 5; i++) // réaffiche le tableau
    {
        for (int j=0; j < 4; j++)
              std::cout << tab[i][j] << " ";
         std::cout << "\n";
    }

    return 0;
}



C++dialement,
Pop70

Merci pop70 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources a aidé 103 internautes ce mois-ci

Commenter la réponse de pop70
Messages postés
3830
Date d'inscription
dimanche 12 décembre 2004
Dernière intervention
19 novembre 2018
0
Merci
Bonjour.
Tu es au bon endroit :)

Si je puis me permettre, je pense que ta structure de données laisse à désirer. Pourquoi ne pas avoir un tableau de structure ?
Je vois plus un std::vector<MaStruct> avec MaStruct contenant 3 valeurs entières.
Il suffit alors d'appliquer un std::sort en précisant que la 3ème valeur est celle du tri.

Ce qui donnerait:
#include 
#include 
#include <vector>

struct MaStruct
{
  MaStruct(int a, int b, int c)
    : _a(a), _b(b), _c(c)
  {
  }

  int _a;
  int _b;
  int _c;
};

void display(const std::vector<MaStruct>& tab)
{
  for (std::vector<MaStruct>::const_iterator it = tab.begin();
       it != tab.end(); ++it)
    std::cout << it->_a << " " << it->_b << " " << it->_c << std::endl;
}

bool sortFunction(const MaStruct& obj1, const MaStruct& obj2)
{
  return obj1._c < obj2._c;
}

int main()
{
  std::vector<MaStruct> tab;
  tab.push_back(MaStruct(3, 3, 3));
  tab.push_back(MaStruct(2, 4, 4));
  tab.push_back(MaStruct(8, 7, 5));
  tab.push_back(MaStruct(6, 4, 3));
  tab.push_back(MaStruct(2, 1, 2));
  tab.push_back(MaStruct(1, 2, 1));

  std::cout << "Before:" << std::endl;
  display(tab);

  std::sort(tab.begin(), tab.end(), sortFunction);

  std::cout << "After:" << std::endl;
  display(tab);

  return 0;
}


________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question
Commenter la réponse de cptpingu
Messages postés
3830
Date d'inscription
dimanche 12 décembre 2004
Dernière intervention
19 novembre 2018
0
Merci
Mettons qu'on veut accéder à la valeur tab[4][2], comment la récupérer via les pointeurs? (tab+4+m+2? tab+4+2?...)

tab[4][2] équivaut à *(*(tab + 4) + 2) => On déréfence le premier tableau *(tab + 4), puis on déréfence le 2ème.

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question
Commenter la réponse de cptpingu
Messages postés
305
Date d'inscription
jeudi 29 avril 2004
Dernière intervention
18 janvier 2012
0
Merci
Et voilà, quand on prend le temps de rédiger correctement une question réfléchie au préalable on a des réponses en moins d'une heure, et de grande qualité.
Certains posteurs devraient en prendre de la graine
+1
Commenter la réponse de cs_LA_Tupac
Messages postés
2
Date d'inscription
mardi 8 novembre 2011
Dernière intervention
8 novembre 2011
0
Merci
Bon, merci à vous pour vos réponses.
CptPingu, c'est certes plus agréable à l’œil et plus optimisé d'utiliser une structure et un vecteur, mais j'avais comme contrainte d'utiliser cette forme.

J'ai donc utilisé le code de Pop70 légèrement modifié pour mes besoins. Dans le doute, je le mets à la suite au cas où quelqu'un aurait un jour le même souci que moi.
(à savoir, les modifications concernent le côté fixe de la valeur à prendre en compte pour le tri. Mais en fin de compte, ça tient très fortement du bubble, j'suis juste hyper mauvais )

void triDuSujet(int m, int[][3]){
        int temp1;
int temp2;
int temp3;
bool tri = true;
while (tri){    
tri=false;    	
        	for (int i=0; i < m-1; i++){
       			if (edge[i][2] > edge[i+1][2]){
        			tri=true;
        			temp1 = edge[i][0];
        			temp2 = edge[i][1];
        			temp3 = edge[i][2];
        			
        		        edge[i][0] = edge[i+1][0];
        		        edge[i][1] = edge[i+1][1];
        		        edge[i][2] = edge[i+1][2];
        		        
        		        edge[i+1][0] = temp1;
        		        edge[i+1][1] = temp2;
        		        edge[i+1][2] = temp3;
        		}
       		}
       	}
}
Commenter la réponse de Askirkela
Messages postés
3830
Date d'inscription
dimanche 12 décembre 2004
Dernière intervention
19 novembre 2018
0
Merci
Merci d'avoir mis à jour ce topic en postant ta solution.
En revanche, pense à bien préciser tes contraintes, afin que l'on puisse t'aider au mieux :)

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question
Commenter la réponse de cptpingu

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.