Fused | Bonjeoir !
Mon algo de tri par tas ne fonctionne pas à 100%: le début du tas n'est pas bien trié et je ne comprends toujours pas pourquoi après y avoir passé 2h dessus ! La fonction "échanger" échange les 2 éléments dans le tableau tas.
Le code n'est pas commenté mais il n'est pas long, et pas dur je pense (je débute là dedans).
Code :
- void tri_tas(int tas[], int debut, int fin)
- {
- int i;
- int taille = fin;
- for(i=taille/2; i>0; i--)
- {
- arranger(tas, i, taille);
- }
- echanger(tas, taille, 1);
- taille--;
- i=1;
- while(i<=taille/2)
- {
- arranger(tas, i, taille);
- echanger(tas, taille, 1);
- taille--;
- }
- }
- void arranger(int tas[], int i, int taille)
- {
- int j=2*i;
- while(j<=taille)
- {
- if(j+1<taille && tas[j] < tas[j+1])
- {
- j++;
- }
- if(tas[i] < tas[j])
- {
- echanger(tas, j, i);
- }
- i=j;
- j*=2;
- }
- }
|
Exemple d'execution avec un tableau aléatoire de 20 éléments en entrée (le bon tri est le premier) :
Code :
- Le tableau trié par le tri rapide est :
- 0 , 2 , 2 , 3 , 4 , 6 , 6 , 7 , 9 , 9 , 11 , 13 , 13 , 14 , 15 , 15 , 18 , 18 , 18 , 19
- Le tableau trié par le tri par tas est :
- 6 , 0 , 0 , 0 , 2 , 2 , 3 , 4 , 6 , 7 , 9 , 9 , 11 , 13 , 13 , 14 , 15 , 15 , 18 , 18
|
Le 19 est parti je ne sais pas où et j'ai des 0 qui apparaissent...
Des idées ?
Au passage, si vous avez des remarques sur la façons de programmer ça, je suis preneur, je début en C++.
Merci d'avance ! Message édité par Fused le 12-12-2007 à 23:00:15
|