Discussion :

[space-cowboy]

slt
j'ai un programme a faire , il s'agit de comparaison entre trois sorte d'algorithme de tri (a bulle-par selection-par insertion).
en fait la comparaison est au terme du "nombre d'affectation" et et de "comaprison" contenu dans chaque algorithme.

je sais pas comment faire enter cette comparaison dans le programme.
si quelq'1 peut m'expliquer comment faire!!

ce que je vois c qu'il faut entrer un compteur chaque fois que l'on rencontre une affectation ou une comparaison ?

[Gruik]

Salut,

ce que je vois c qu'il faut entrer un compteur chaque fois que l'on rencontre une affectation ou une comparaison ?

Oui, je crois bien que c'est ça

[archer]

Salut
je crois que c'est une bonne idée:
-un compteur pour l'affectation si la condition qui mène au changement de place est verifiée
-un compteur pour la comparaison qui va s'incrémenter pour toutes les itérations
je suis impassion de savoir qui va l'emporter

[Sve@r]

je suis impassion de savoir qui va l'emporter

Ouaip, moi aussi je suis impatient de savoir qui va l'emporter sauf qu'on ne le saura jamais car les algorithmes de tri dépendent de la façon dont les données arrivent dans l'algo. Si par hasard les données sont déjà triées ben certains algo généralement très rapides tombent en perfo de façon dramatique, si les données sont triées de façon inverse ben ce sont d'autres algo qui descendent, Par exemple le quicksort qui est considéré comme hyper rapide chute lamentablement si les données qu'on lui donne sont déjà triées à l'envers etc etc...

Tout ce qu'on peut dire, c'est que "généralement il semble que certains algo soient plus rapide que certains autres"...

[DaZumba]

Ouaip, moi aussi je suis impatient de savoir qui va l'emporter sauf qu'on ne le saura jamais car les algorithmes de tri dépendent de la façon dont les données arrivent dans l'algo.

... et du nombre de donnees a trier. Mais l'idee est certainement de faire un grand nombre de tris sur des ensembles de donnees aleatoires. De plus, on peut deja se douter des resultats: le tri a bulle va etre lent et inefficace (c'est connu), et le tri par insertion devrait theoriquement etre plus efficace que le tri par selection.

[pseudocode]

et le meilleur en moyenne sera surement le RandQuickSort.

[Transgarp]

J'ai optimisé le QuickSort de G.H. Gonnet pour justement le rendre plus rapide en cas de matrice source en ordre descendant et le rendre plus rapide en tout temps.

Ne regardez pas trop la forme, mais regardez les résultats que vous aurez en l'adoptant dans vos programmes.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
Program X;
Var
  AA                      : Array[0..2000] of String[20];
 
Procedure QuickSort2(L,R : Integer); { Version Transgarp                     }
Var
  I,J,V : Integer; X,Y : String[20];
Begin
  I:=L; J:=R;
  X:=AA[(L+R) div 2];
  Repeat
    While AA[I]<X do I:=I+1;
    While X<AA[J] do J:=J-1;
    If I<=J then
    Begin
      If I<J then Begin Y:=AA[I]; AA[I]:=AA[J]; AA[J]:=Y; End;
      I:=I+1; J:=J-1;
    End;
  Until I>J;
  If L<J then QuickSort2(L,J);
  If I<R then QuickSort2(I,R);
End;
 
Begin
End.

[pseudocode]

J'ai optimisé le QuickSort de G.H. Gonnet pour justement le rendre plus rapide en cas de matrice source en ordre descendant et le rendre plus rapide en tout temps.

Meme dans le cas d'une liste déja triée ?

[benDelphic]

Ouaip, moi aussi je suis impatient de savoir qui va l'emporter sauf qu'on ne le saura jamais car les algorithmes de tri dépendent de la façon dont les données arrivent dans l'algo. Si par hasard les données sont déjà triées ben certains algo généralement très rapides tombent en perfo de façon dramatique, si les données sont triées de façon inverse ben ce sont d'autres algo qui descendent, Par exemple le quicksort qui est considéré comme hyper rapide chute lamentablement si les données qu'on lui donne sont déjà triées à l'envers etc etc...

Tout ce qu'on peut dire, c'est que "généralement il semble que certains algo soient plus rapide que certains autres"...

eh ben la c'est sur le bubble sort aura les plus mauvais résultats...
et puis on compare toujours par rapport à la taille des données suivant un codage raisonnable .