Tri appliqué à un tableau à 2 dimensions basé sur la 2nde dimensionRésolu

Question

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!

pop70 · Accepted Answer

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 << "
";

    for (int i=0; i < 5; i++)
    {
        for (int j=0; j < 4; j++)
              std::cout << tab[i][j] << " ";
         std::cout << "
";
    }


    std::cout << "
Avec pointeurs : " << *(*(tab + 3) + 2);  // *(*(tab + ligne) + colonne)
    std::cout << "
Avec 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 << "

";
    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 << "
";
    }

    return 0;
}


C++dialement,
Pop70

cptpingu · Answer

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 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 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& tab) { for (std::vector::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 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

cptpingu · Answer

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

cs_LA_Tupac · Answer

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

Askirkela · Answer

Bon, merci à vous pour vos réponses.
CptPingu, c'est certes plus agréable à l&#8217;œ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;
        		}
       		}
       	}
}

cptpingu · Answer

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

Tri appliqué à un tableau à 2 dimensions basé sur la 2nde dimension

6 réponses

Votre réponse

Discussions similaires