Méthode de tri

Méthode de tri - C++ - Programmation

Marsh Posté le 09-09-2006 à 17:53:52    

Bonjour !
 
   En ce moment je suis en train de m'amuser a trier des entiers contenu dans un tableau. je sais il y a la STL qui fait ça super bien, rapide et tout... Mais bon aujourd'hui je réinvente la roue :D. J'ai créé mon petit algorithme... bon je sais il est sûrement pas efficace (une fois qu'il marchera j'irais voir Google pour en trouver des meilleurs...)
 
voilà :
 

Code :
  1. #include <iostream>
  3. int main(int argc, char **argv)
  4. {
  5. int tab[] = {1, 6, 4, 3, 2, 8, 10, 9, 5, 12};
  6. int index=0, min;
  8. for(int i = 0 ; i < 10 ; i++)
  9. {
  10.  min = tab[i];
  11.  for(int n = i ; n < 10 ; n++)
  12.   if(min > tab[n])
  13.   {
  14.    index = n;
  15.    min = tab[n];
  16.   }
  18.   std::cout<<"Le min c'est : "<<min<<"---";
  19.   for(int n = i ; n < 10 ; n++)
  20.    std::cout<<tab[n]<<" ";
  21.   std::cout<<std::endl;
  23.   int temp = tab[index];
  24.   tab[index] = tab[i];
  25.   tab[i] = temp;
  26. }
  27. for(int i = 0 ; i < 10 ; i++)
  28.  std::cout<<tab[i]<<" ";
  30. std::cout<<std::endl;
  31.     return 0;
  32. }


 
Bon le soucis c'est qu'a la sortie il me sort ça :  

Citation :


Le min c'est : 1---1 6 4 3 2 8 10 9 5 12
Le min c'est : 2---6 4 3 2 8 10 9 5 12
Le min c'est : 3---6 4 3 8 10 9 5 12
Le min c'est : 4---6 4 8 10 9 5 12
Le min c'est : 5---6 8 10 9 5 12
Le min c'est : 6---6 8 10 9 12
Le min c'est : 8---8 10 9 12
Le min c'est : 9---10 9 12
Le min c'est : 9---9 12
Le min c'est : 12---12
 
1 2 3 4 5 6 8 10 12 9


 
comme on peut le voir il y a un souci sur les trois dernières lignes (avec l'histoire du 9). Est-ce que vous voyez le problème, je suis sûr que ça doit être bête mais je vois pas...
 
Merci
 
[edit] j'ai trouvé le nom de ma méthode : tri par sélection...


Message édité par Amonchakai le 09-09-2006 à 18:48:34
Reply

Marsh Posté le 09-09-2006 à 17:53:52   

Reply

Marsh Posté le 09-09-2006 à 20:24:40    

Andouille!!!
ligne 6: tu initialise <<min>> mais pas <<index>>
(or il se trouve qu'à un moment donné pour min=6 c'est à la fois le minimum et le premier élément du sous-tableau non trié, et qu'<<index>> est celui de l'élément précédamment minimum)

Message cité 2 fois
Message édité par nargy le 09-09-2006 à 20:27:09
Reply

Marsh Posté le 09-09-2006 à 20:38:59    

nargy a écrit :

Andouille!!!
ligne 6: tu initialise <<min>> mais pas <<index>>
(or il se trouve qu'à un moment donné pour min=6 c'est à la fois le minimum et le premier élément du sous-tableau non trié, et qu'<<index>> est celui de l'élément précédamment minimum)


 
pardon... pardon... je vais de ce pas m'autoflageller, je recommencerais pas promis...
 
 
Merci :D

Reply

Marsh Posté le 10-09-2006 à 12:43:06    

nargy a écrit :

Andouille!!!
ligne 6: tu initialise <<min>> mais pas <<index>>


[:rofl]


Message édité par Sve@r le 10-09-2006 à 12:43:22

---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 10-09-2006 à 14:03:00    

Les compilos ne détectent pas les variables non initialisées ?

Reply

Marsh Posté le 10-09-2006 à 14:41:40    

Il s'agit sur certains compilos d'une option facultative.

Reply

Marsh Posté le 10-09-2006 à 15:19:53    

Surtout que la il y avait aucunne chance qu'il prévienne puisque index avait été initialisé ligne 6 au moment de sa déclaration et qu'il fallait que je l'initialise a la valeur de i dans le premier for() a la ligne 10...

Reply

Marsh Posté le 10-09-2006 à 17:22:34    

:??:

Reply

Marsh Posté le 10-09-2006 à 17:58:07    

Bonjour !
 
   Me revoila avec un nouvel algorithme de tri... Après le tri par sélection, le tri par insertion, le tri a bulle voici le tri par fusion !
   Bon je tient tout d'abord a prévenir mon algo marche :) mais j'aimerais bien avoir votre avis sur ce que j'ai écrit (en fait pour savoir si il pue pas trop :D) par ce que des quatres c'est celui qui est le plus volumineux donc j'aimerais savoir si j'ai pas compliqué le problème...
 
Voilà

Code :
  1. #include<iostream>
  3. void triFusion(int* tab, int length);
  5. int main(int argc, char** argv)
  6. {
  7. int tab[] = {1, 8, 5, 3, 9, 2, 6, 4, 7, 0};
  9. triFusion(tab, sizeof(tab)/4);
  11. for(int i = 0 ; i < 10 ; i++)
  12.  std::cout<<tab[i]<<" ";
  13. std::cout<<std::endl;
  14. }
  16. void triFusion(int* tab, int length)
  17. {
  18. if(length == 1)  //cas trivial
  19.  return;
  21. int *ssTab1, *ssTab2;
  22. int taille1, taille2;
  24. // allocation de mem pour les ssTabs  
  25. if(length%2 == 0)
  26.  taille1 = taille2 = length/2;
  27. else
  28. {
  29.  taille1 = length/2;
  30.  taille2 = length/2+1;
  31. }
  32. ssTab1 = new int[taille1];
  33. ssTab2 = new int[taille2];
  35. //remplissage des ssTabs
  36. for(int i = 0 ; i < length/2 ; i++)
  37. {
  38.  ssTab1[i] = tab[i];
  39.  ssTab2[i] = tab[i+length/2];
  40. }
  41. if(length%2 == 1)
  42.  ssTab2[length/2] = tab[length-1];
  44. //Tri des ssTabs
  45. triFusion(ssTab1, taille1);
  46. triFusion(ssTab2, taille2);
  48. //regroupement des ssTabs
  49. int index1 = 0, index2 = 0;
  51. for(int i = 0 ; i < length ; i++)
  52. {
  53.  if(index1 == taille1)
  54.  {
  55.   tab[i] = ssTab2[index2];
  56.   index2++;
  57.   continue;
  58.  }
  60.  if(index2 == taille2)
  61.  {
  62.   tab[i] = ssTab1[index1];
  63.   index1++;
  64.   continue;
  65.  }
  67.  if(ssTab1[index1] <= ssTab2[index2])
  68.  {
  69.   tab[i] = ssTab1[index1];
  70.   index1++;
  71.  }
  72.  else
  73.  {
  74.   tab[i] = ssTab2[index2];
  75.   index2++;
  76.  }
  77. }
  79. delete[] ssTab1;
  80. delete[] ssTab2;
  81. }


 
dans le genre des truc qui pue il y a ma partie regroupement des tableaux que je trouve pas belle... mais j'ai pas trouvé mieux...
 
Merci de me donner votre avis :)


Message édité par Amonchakai le 10-09-2006 à 18:04:24
Reply

Marsh Posté le 10-09-2006 à 18:12:00    

au moins il ya des commentaires :p
lignes 53-65: il me semble que tu peux les mettre après la boucle.

Reply

Marsh Posté le 10-09-2006 à 18:12:00   

Reply

Marsh Posté le 10-09-2006 à 18:20:37    

tu veut dire de mettre ça:

Code :
  1. if(index1 == taille1)
  2. {
  3. tab[i] = ssTab2[index2];
  4. index2++;
  5. continue;
  6. }
  8. if(index2 == taille2)
  9. {
  10. tab[i] = ssTab1[index1];
  11. index1++;
  12. continue;
  13. }


 
après ça :  

Code :
  1. if(ssTab1[index1] <= ssTab2[index2])
  2. {
  3. tab[i] = ssTab1[index1];
  4. index1++;
  5. }
  6. else
  7. {
  8. tab[i] = ssTab2[index2];
  9. index2++;
  10. }


???
mais je risque de sortir de mes tableaux non ? c'etait justement pour ça que j'avais mis mes premiers test...
 
Et Merci de me donner ton avis :)
 
ps : au sujet des comentaires c'est vrai que j'ai fait un effort pour forcer a en mettre :D

Reply

Marsh Posté le 10-09-2006 à 18:40:36    

Bon... En étudiant ton code, je me rends compte que j'ai sûrement dit une connerie.
Je me basais sur le fait que taille2-taille1<=1 et sur les lignes 56 et 63, qui malheureusement sont fausses.
J'explique:
tu teste index1==taille1, et si ce test est vrai tu incrémente index1. Or, index1 cette fois dépasse taille1 donc au prochain tour de boucle taille1!=index1. Celà ne pose pas de problème dans ton exemple (?), mais si par exemple tous les éléments du sstab1 sont inférieurs à ceux de sstab2, tu va épuiser les éléments de sstab1 avant ceux de sstab2, et faire déborder index1.
Idem pour taille2 et index2.

Message cité 1 fois
Reply

Marsh Posté le 10-09-2006 à 18:43:37    

Tu devrais essayer de faire tourner le programme avec un tableau de taille impaire pour voir s'il y d'autres bugs. (a priori non, mais ça peut servir de tester)
 
Edit: Perso je protègerais le if de la ligne 67 avec un test index1<taille1 et index2<taille2, pour faire trois cas: index1 épuisé, index2 épuisé, aucun des deux épuisés. Si l'un des deux est épuisé tu peut te contenter de recopier le reste de l'autre sous-tableau avec un memcpy.


Message édité par nargy le 10-09-2006 à 18:48:23
Reply

Marsh Posté le 10-09-2006 à 18:52:29    

nargy a écrit :

Bon... En étudiant ton code, je me rends compte que j'ai sûrement dit une connerie.
Je me basais sur le fait que taille2-taille1<=1 et sur les lignes 56 et 63, qui malheureusement sont fausses.
J'explique:
tu teste index1==taille1, et si ce test est vrai tu incrémente index1. Or, index1 cette fois dépasse taille1 donc au prochain tour de boucle taille1!=index1. Celà ne pose pas de problème dans ton exemple (?), mais si par exemple tous les éléments du sstab1 sont inférieurs à ceux de sstab2, tu va épuiser les éléments de sstab1 avant ceux de sstab2, et faire déborder index1.
Idem pour taille2 et index2.


 
Oui, c'est justement l'objectif de mes deux premiers test dans ma boucle for()... Mais je croit que tu as pas bien vu ce que j'ai fait car quand j'ai index1==taille1 ce n'est plus index1 que j'incrémente mais index2... Ayant mis tous les éléments de ssTab1 je met maintenant tous ceux de ssTab2.
 
Sinon on a bien toujours taille2-taille1<=1

Reply

Marsh Posté le 10-09-2006 à 18:54:18    

Ha oui exact, j'ai mal lu... ma suggestion d'utiliser memcpy reste valable.

Reply

Marsh Posté le 10-09-2006 à 18:56:13    

j'avais pas vu memcpy()... Ok je vais mettre ça

Reply

Marsh Posté le 10-09-2006 à 19:11:26    

Heu il y a un soucis avec memcpy()... car quand je regarde ce qu'ils disent là :
http://www.linux-kheops.com/doc/ma [...] html#sect0
 
Je vais avoir mon tableau tab qui va être écrasé au lieu d'être complété non ?
Et puis pour copier la fin de ssTab1 (respectivement ssTab2) il va falloir que je crée un autre tableau, car memcpy() copie n octets a partir du début de la zone mémoire pointé par ssTab1 non ?

Reply

Marsh Posté le 10-09-2006 à 20:21:06    

arithmétique de pointeurs...

Code :
  1. // copier à partir de debut_source jusqu'à fin_source vers debut_dest:
  2. memcpy(dest+debut_dest, source+debut_source, fin_source-debut_source*sizeof(int));


Message cité 1 fois
Reply

Marsh Posté le 10-09-2006 à 20:26:53    

nargy a écrit :

arithmétique de pointeurs...

Code :
  1. // copier à partir de debut_source jusqu'à fin_source vers debut_dest:
  2. memcpy(dest+debut_dest, source+debut_source, fin_source-debut_source*sizeof(int));



 
Ha bha je connais pas...  :??:  
Voilà un truc de base auquel je suis passé à côté...  
Bon, il va falloir que j'aprenne ça.
 
Merci

Reply

Marsh Posté le 10-09-2006 à 21:09:08    

Salut !
   Bon je viens de regarder l'arithmétique des pointeurs. Et je comprend pas bien ce que c'est que la différence de deux pointeurs. Car sur le site que j'ai trouvé ils disent ça :  
 

Citation :

Le type du résultat de la soustraction de deux pointeurs est très dépendant de la machine cible et du modèle mémoire du programme. En général, on ne pourra jamais supposer que la soustraction de deux pointeurs est un entier (que les chevronnés du C me pardonnent, mais c'est une erreur très grave). En effet, ce type peut être insuffisant pour stocker des adresses (une machine peut avoir des adresses sur 64 bits et des données sur 32 bits). Pour résoudre ce problème, le fichier d'en-tête stdlib.h contient la définition du type à utiliser pour la différence de deux pointeurs. Ce type est nommé ptrdiff_t.


 
bon quand il dit : "on ne pourra jamais supposer que la soustraction de deux pointeurs est un entier" en même temp ça me serait pas venu a l'idée... Et ensuite quand il dit "Ce type est nommé ptrdiff_t" c'est super mais c'est quoi ? un pointeur j'imagine mais sur quelle zone mémoire ?
 
Merci

Reply

Marsh Posté le 10-09-2006 à 21:28:42    

Te prends pas la tête.
Dans l'exemple que je t'ai donné, on ne stocke pas la différence des pointeurs, on la donne tel quel à memcpy.
Sur une machine avec des pointeurs 64bits, la différence de deux pointeurs est 64 bits, or pour pouvoir copier des zones mémoires memcpy doit donc utiliser une taille de 64bits. Sizeof() retourne lui aussi un entier 64bits.

Reply

Marsh Posté le 10-09-2006 à 21:52:46    

Ok, donc au final ça donne ça :  
 

Code :
  1. //regroupement des ssTabs
  2. int index1 = 0, index2 = 0;
  4. for(int i = 0 ; i < length ; i++)
  5. {
  6.  if(index1 == taille1)
  7.  {
  8.   memcpy(tab+i, ssTab2+index2, (taille2-index2)*sizeof(int));
  9.   break;
  10.  }
  12.  if(index2 == taille2)
  13.  {
  14.   memcpy(tab+i, ssTab1+index1, (taille1-index1)*sizeof(int));
  15.   break;
  16.  }
  18.  if(ssTab1[index1] <= ssTab2[index2])
  19.  {
  20.   tab[i] = ssTab1[index1];
  21.   index1++;
  22.  }
  23.  else
  24.  {
  25.   tab[i] = ssTab2[index2];
  26.   index2++;
  27.  }
  28. }
  29.     delete[] ssTab1;
  30.     delete[] ssTab2;
  31. }


 
Et ça marche impec...
 
Mais bon dans ce cas on a juste l'addition de pointeurs avec des entier... La Ok pas de problème, je comprend ce que ça fait. Mais la différence de deux pointeurs c'est la première fois que j'en endend parler. C'est pour ça que je voulais essayer de comprendre ce que cela pouvait bien donner... (et je note qu'ils ont parlé de différence mais pas d'addition...  :??: )
 
Bon en gros tu me conseille de faire l'impasse dessus, c'est pas important ?

Reply

Marsh Posté le 10-09-2006 à 22:06:15    

La différence entre deux pointeurs, est la différence entre deux positions en mémoire, c'est donc une longueur (intervalle de mémoire).
Le problème peut survenir quand la taille totale de mémoire est supérieure à celle d'un entier, dans ce cas si tu mets une différence entre deux pointeurs (la mesure d'un intervalle de mémoire a le même nombre de bits qu'un pointeur) dans un entier tu perds des bits. Comme quand tu essaye de faire tenir 64bits dans 32bits.
Ce n'est pas le cas avec le memcpy que tu as fait.

Reply

Marsh Posté le 10-09-2006 à 22:15:24    

D'accord, Merci beaucoup nargy :)

Reply

Marsh Posté le 10-09-2006 à 22:31:59    

A oui, j'oubliais, l'addition de pointeurs n'a pas de signification. Par contre une position + une longueur donne une nouvelle position.

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

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