tri d'un tableau 1D c++

tri d'un tableau 1D c++ - C++ - Programmation

Marsh Posté le 20-02-2005 à 11:44:56    

Bonjour à tous,  
 
Quelqu'un pourrait m'aider à trier ce tableau en c++ comme suit:  
 
tab={-1, -1, 0,0 ,17,25,-1,8,0,28} en tab={-1,-1,0,0,2,3,-1,1,4 }.  
C'est à dire à reassigner les elements du tableau par ordre de grandeur sans toucher aux 0 et -1.  
Je suis confronté à un debordement de capacité de type int, ce qui m'oblige à reassigner mon tableau à chaque iteration.  
 
Je vous remercie d'avance.
 

Reply

Marsh Posté le 20-02-2005 à 11:44:56   

Reply

Marsh Posté le 20-02-2005 à 11:56:07    

ça n'est pas un tri. si tu veux faire un tri, extrait d'abord tes -1 et 0, tri le résultat, puis fusionne.
 
std::sort en tête

Reply

Marsh Posté le 20-02-2005 à 12:22:52    

Merci pour ton indication. Mais en fait, si j'extrais les -1 et 0, trie et fusionne, j'aurai plus l'ordre que je souhaite avoir.

Reply

Marsh Posté le 20-02-2005 à 12:29:04    

ben si

Reply

Marsh Posté le 20-02-2005 à 12:47:36    

Bon voilà, je vais donner des details. En fait, il s'agit de chercher mis à part les -1 et 0, le minimum du tableau lui assigner 1 (à cette position), refaire la recherche du minimum sur le reste, lui assigner deux (à cette position) ainsi de suite jusqu'à ce que le tableau soit reassigné en entier.
Merci.

Reply

Marsh Posté le 20-02-2005 à 13:29:21    

ben tu cris ton algo de tri voir mieux ton propre foncteur de tri pour le passer a std::sort [:dawa]

Reply

Marsh Posté le 20-02-2005 à 13:34:02    

Joel F a écrit :

ben tu cris ton algo de tri voir mieux ton propre foncteur de tri pour le passer a std::sort [:dawa]


ça ne peut pas marcher

Reply

Marsh Posté le 20-02-2005 à 23:54:38    

pardon o_O ??

Reply

Marsh Posté le 21-02-2005 à 01:09:35    

je ne comprend pas bien la demande :
il s'agit bien de remplacer le nombre par son rang en écartant les -1 et les 0 ...
 
Si oui, quel est l'algo que tu as utilisé pour savoir?

Reply

Marsh Posté le 21-02-2005 à 09:25:59    

Tu peux essayer ceci :
 

Code :
  1. #include <iostream>
  2. #include <list>
  4. using namespace std;
  6. int main()
  7. {
  8.   int tab[10] = {-1,0,3,-5,0,-1,2,-1,-4,0};
  9.   int* tab1;
  10.   int i,taille;
  11.   list<int> list_0,list_1,list_f;
  12.   list<int>::iterator it,it0,it1;
  13.  
  14.   // Calcul de la taille du tableau (si initialement inconnue)
  15.  
  16.   taille = sizeof(tab)/sizeof(int);
  17.  
  18.   // Remplissage des listes list_1, list_0, list_f
  19.  
  20.   for(i=0;i<taille;i++)
  21.     {
  22.       if (tab[i] == -1)
  23. {
  24.   list_1.push_back(i);
  25. }
  26.       else if (tab[i] == 0)
  27. {
  28.   list_0.push_back(i);
  29. }
  30.       else
  31. {
  32.   list_f.push_back(tab[i]);
  33. }
  34.     }
  35.  
  36.   // Tri de list_f
  37.  
  38.   list_f.sort();
  40.   // Retour des -1 et des 0 à leurs positions initiales
  41.  
  42.   it = list_f.begin();
  44.   it1 = list_1.begin();
  45.  
  46.   it0 = list_0.begin();
  47.  
  48.   tab1 = new int[taille];
  50.   for(i=0;i<taille;i++)
  51.     {
  52.       if ((*it1) == i)
  53. {
  54.   tab1[i] = -1;
  56.   it1++;
  57. }
  58.       else if ((*it0) == i)
  59. {
  60.   tab1[i] = 0;
  62.   it0++;
  63. }
  64.       else
  65. {
  66.   tab1[i] = (*it);
  68.   it++;
  69. }
  70.     }
  71.  
  72.   // Affichage de la liste list_f
  74.   for(i=0;i<taille;i++)
  75.     {
  76.       cout << tab1[i] << endl;
  77.     }
  78. }


 
Le tableau tab est initialisé ici mais on peut le remplir comme souhaité. Sa taille est ensuite calculée. On le parcours et, en différenciant les valeurs des éléments, on remplit 3 tableaux différemments. Seul le dernier est trié (list_f). Le tableay tab1 contient le résultat final car il a été remplis différemment selon l'indice de l'élément.
 
Cordialement

Reply

Marsh Posté le 21-02-2005 à 09:25:59   

Reply

Marsh Posté le 21-02-2005 à 09:27:26    

Bon, l'indentation est pas très bien passée et il faut lire :
 
// Affichage du tableau tab1  
 
à la fin (le commentaire est incorrect)

Reply

Marsh Posté le 21-02-2005 à 11:39:14    

vous faites chier à lui faire ses devoirs

Reply

Marsh Posté le 23-02-2005 à 10:40:31    

Bonjour à tous, merci aux contributions, merci nathan_g.
Je reexpose le problème car çà n'est pas du tout un tri normal comme l'a traité nathan mais plutôt il s'agit bien de remplacer le nombre par son rang en écartant les -1 et les 0 dans le même tableau à leur position evidemment.  
En fait, j'utilise un algorithme de parcours sur les graphes où à chaque fois je choisis le sommet en fonction de son etiquette. L'étiquette i étant la valeur du tableau correspondant au somme i. En triant, on ne doit pas decaler les valeurs, sinon on ne saurait à quel sommet telle ou telle etiquette correspond. Ensuite, le but c'est de transformer le tableau d'etiquettes en tableau de rang à chaque iteration car les etiquettes croissant vite, on risque un debordement.
Cordialement

Reply

Marsh Posté le 23-02-2005 à 20:29:07    

Bonjour,
 
je pense qu'une méthode de tri standard est la bonne...
Il faudrait faire qqch du style :
- en une passe du tableau initial : construire un tableau de pointeurs sur une structure (ou classe comme on veut) qui contient à la fois la valeur et la position dans le tableau original (pour les valeurs strictement positives)
- on applique un tri sur le tableau obtenu (tri rapide ou tri fusion...) : quelque chose de similaire à ce qui est fait là haut.
- on reparcourt le tableau trié pour mettre le rang dans la position mise dans la structure...
 
Je pense pas que ça soit trop compliqué à mettre en oeuvre...
 
++

Reply

Marsh Posté le 24-02-2005 à 09:44:38    

Je reexpose le problème car çà n'est pas du tout un tri normal comme l'a traité nathan mais plutôt il s'agit bien de remplacer le nombre par son rang en écartant les -1 et les 0 dans le même tableau à leur position evidemment.  
 
J'ai pas tout compris ...
 
En fait, si je considère ton exemple du début (même s'il manque un morceau), tu demande à ce qu'on remplace les éléments différents de -1 et 0 par l'indice de leur rang dans la liste " list_f " triée (compté à partir de 1) ?
J'ai bon ?
 
Dans ce cas (après qqs correction aussi sur le programme initial) :
 

Code :
  1. #include <iostream>
  2. #include <list>
  4. using namespace std;
  6. class Couple
  7. {
  8. public:
  10.   Couple() {}
  11.  
  12.   Couple(int init_rang,int init_val) {_rang = init_rang;_val = init_val;}
  14.   int rang() {return (_rang);}
  16.   int val()  {return (_val);}
  17.  
  18. protected:
  20.   int _rang;
  21.  
  22.   int _val;
  23. };
  26. struct Compar
  27. { 
  28.   bool operator()(Couple left,Couple right)
  29.     { 
  30.       return ((left.val())<(right.val())); 
  31.     } 
  32. };
  35. int main()
  36. {
  37.   int tab[10] = {-1,0,3,-5,0,-1,2,-1,-4,0};
  38.   int* tab1;
  39.   int i,jf,taille;
  40.   list<Couple> list_0,list_f;
  41.   list<Couple>::iterator it0,itf;
  42.  
  43.   // Calcul de la taille du tableau (si initialement inconnue)
  44.  
  45.   taille = sizeof(tab)/sizeof(int);
  46.  
  47.   // Remplissage des listes list_1, list_0, list_f
  48.  
  49.   for(i=0;i<taille;i++)
  50.     {
  51.       if (!(tab[i] == -1 || tab[i] == 0))
  52. {
  53.   // Enregistrement de la valeur et du rang
  54.  
  55.   list_f.push_back(Couple(i,tab[i]));
  56. }
  57.     }
  58.  
  59.   // Tri de list_f
  60.  
  61.   list_f.sort(Compar());
  63.   // Retour des -1 et des 0 à leurs positions initiales
  65.   it0 = list_0.begin();
  67.   jf = 1;
  68.  
  69.   itf = list_f.begin();
  70.  
  71.   tab1 = new int[taille];
  73.   for(i=0;i<taille;i++)
  74.     {
  75.       if (tab[i] == -1 || tab[i] == 0)
  76. {
  77.   // Retour d'une valeur -1 ou 0 dans la liste
  78.  
  79.   tab1[i] = tab[i];
  80. }
  81.       else
  82. {
  83.   // Retour de l'indice
  84.  
  85.   tab1[(*itf).rang()] = jf;
  87.   jf++;
  88.  
  89.   itf++;
  90. }
  91.     }
  92.  
  93.   // Affichage de la liste list_f
  95.   for(i=0;i<taille;i++)
  96.     {
  97.       cout << tab1[i] << endl;
  98.     }
  99. }


 
Je sais qu'il y a qqs problèmes de syntaxes (notamment des const qui manquent ...) mais ça doit fonctionner.
PS: Si tu as Visual C++ 6.0 comme moi, inutile d'essayer, ça ne fonctionnera pas. Même bien écrit, un tri de list avec un foncteur donne un tri faux ! Par contre, sous gcc ce programme a l'air de marcher.

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed