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

Signaler
Messages postés
2
Date d'inscription
mardi 8 novembre 2011
Statut
Membre
Dernière intervention
8 novembre 2011
-
Messages postés
3809
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
22 avril 2020
-
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!

6 réponses

Messages postés
181
Date d'inscription
mardi 6 avril 2010
Statut
Membre
Dernière intervention
7 janvier 2012
8
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
Messages postés
3809
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
22 avril 2020
105
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
Messages postés
3809
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
22 avril 2020
105
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
Messages postés
305
Date d'inscription
jeudi 29 avril 2004
Statut
Membre
Dernière intervention
18 janvier 2012

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
Messages postés
2
Date d'inscription
mardi 8 novembre 2011
Statut
Membre
Dernière intervention
8 novembre 2011

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;
        		}
       		}
       	}
}
Messages postés
3809
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
22 avril 2020
105
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