[Delphi]Exemple de tri QuickSort

Bonjour,

Je vous propose un nouvel élément à utiliser : [Delphi]Exemple de tri QuickSort

Implémentation de la méthode du tri rapide.



NOTES : Le programme d'exemple montre la différence de vitesse entre le 'tri à bulles' et le 'tri rapide'. Dans le cas de tableau de faible taille ( quelques centaines d'éléments ), le tri à bulles est bien suffisant, mais dans le cas de tableau très importants le 'tri rapide' doit être utilisé.

Le tri est ici appliqué à des tableaux d'entiers, mais il est facile de l'adapter à d'autres types.



Qu'en pensez-vous ?

Salut

J'ai pas regardé le code car pas de besoin actuellement dans ce sens.
Dans le passé, pour me dépanner avec D7 quand j'en ai eu besoin, j'ai repris et adapté le code de TList.Sort, ça rend bien service.

Tout ça pour dire que des fois dans la VCL, il y a de petites pépites. Ca vaut le coup d'explorer la VCL.

Dans ton bestiaire de routines concernant le tri, on peut également signaler l’existence d’autres méthodes :

Par Insertion.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

procedure OrderByInsertion(var Tab: Array of Integer); var i, j, value : integer; begin for i := Low(Tab)+1 to High(Tab) do begin value := Tab[i]; j := i; while Tab[j-1] > value do begin Tab[j] := Tab[j-1]; j := j - 1 ; end; Tab[j] := value; end end;

---

Par sélection.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

procedure OrderBySelection(var Tab: Array of Integer); var i, j, k, l : integer; begin for i := Low(Tab) to High(Tab)-1 do begin l := i; for j := i+1 to High(Tab) do if Tab[j] < Tab[l] then l := j; k := Tab[l]; Tab[l] := Tab[i]; Tab[i] := k; end; end;

---

......

Pour les trois méthodes (« à bulles », « sélection » et « insertion ») la complexité en nombre de comparaisons est de O(n²).
La complexité en nombre d’échanges (pour « sélection ») est O(n²) au pire (autant d’échanges que de comparaisons) mais O(n) en général (en fait O(3n) car on a 3 échanges).

Pour « insertion », la complexité en nombre de transferts est de O(n²).

En terme de complexité, le meilleur de ces quatre algorithmes (à condition d’avoir un nombre conséquent de données à trier) est sans conteste « rapide », bien que dans le pire des cas la complexité moyenne est O(n²) (le pivot est chaque fois la plus grande valeur), au mieux nous avons O(n.log(n)) [Robert Sedgewick Algorithms 2d ed, Addison-Wesley Professional, 1988]

On peut encore citer le tri par fusion O(n²), et la méthode tri par arbre ou par tas avec au meilleur une complexité de O(n.log(n)).


(Il faudrait que je remette la main sur ces algo, j’avais fait un papier la dessus il y a quelques années).

[EDIT]
Merci Eric, post modifié ;)
[/EDIT]

@Pascal : tu as écris deux fois le même algorithme, à 00h06, ça sent la fatigue :P

J'ai aussi le Sedgewick, bon bouquin quoique les algorithmes ne soient pas tous complets. Je voulais dire que l'on peut trouver des choses très intéressantes dans les sources de la VCL (merci Borland de les avoir laisser à disposition des développeurs) et les reprendre pour ses propres besoins, cela limite l'effort de mise au point car traduire un algorithme d'un langage à un autre n'est pas toujours chose aisée.
Il est dommage que les types génériques ne soient pas mis à contribution plus souvent pour décrire ce type d'algorithme.

Bonjour,

On oublie souvent le Tri par casiers (bucket sort) qui est pourtant plus rapide que le QuickSort lorsque les conditions optimales sont réunies pour qu'il soit utilisable c'est à dire :
- lorsque les valeurs à trier sont faibles et de même signe (comme par exemple des valeurs du type byte lors d'un tri pour un filtre médian en traitement d'image),
- ou lorsque les valeurs à trier sont de même signe et que la mémoire vive disponible à l'instant du tri est suffisante,
- et que les valeurs à trier sont très nombreuses.

Principe du tri par casiers : Un tableau trié n'est rien d'autre que la restitution, dans l'ordre d'apparition des occurrences des valeurs, du tableau non trié :
Exemple de table à trier : 34, 55, 88, 55, 99, 55
- Dimensionnement d'une table de comptage 'nbOcc' des occurences : Ici Maxi des valeurs = 99 et Mini = 34 donc SetLength(nbOcc,99-34+1)
- Comptages : nbOcc(34)=1, nbOcc(55)=3, nbOcc(88)=1, nbOcc(99)=1
- Restitution : 1 fois 34 suivi de 3 fois 55 suivi de 1 fois 88 suivi de 1 fois 99
ce qui donne 34, 55, 55, 55, 88, 99 = tableau trié en seulement trois temps.

Pour les curieux, voici une appli qui permet d'explorer les possibilités du tri-casiers :

A+. :D

Si, si, c'est connu mais c'est assez rarement utilisable. Mon prof de programmation appelait le tri basique. Ce doit être le seul cas d'algorithme de tri linéaire.

Re-salut,

Citation:

---

E-ric : Si, si, c'est connu mais c'est assez rarement utilisable. Mon prof de programmation appelait le tri basique. Ce doit être le seul cas d'algorithme de tri linéaire.

---

... Exact, et on le nomme aussi "Tri postal", "Tri par comptage d'occurrences".

... Par contre je dirais plutôt que c'était assez rarement utilisable car de nos jours on dispose de barrettes de plusieurs Go, et que cela vaut donc le coup de le sortir des oubliettes.
Par exemple : le tri de valeurs du Type Word [0..65535] se réalise chez moi presque instantanément lors d'un tri de 200 000 000 valeurs : mon chrono avec GetTickCount m'affiche " mis : 0 ms" donc ça s'exécute en une fraction de milliseconde.
... mais pour en trier dix fois plus je n'ai plus assez de mem-vive-disponible sauf peut-être en fermant toutes les applis qui tournent en tâche de fond.

A+. :D

Citation:

---

Envoyé par Gilbert Geyer

Re-salut,


... Exact, et on le nomme aussi "Tri postal", "Tri par comptage d'occurrences".

... Par contre je dirais plutôt que c'était assez rarement utilisable car de nos jours on dispose de barrettes de plusieurs Go, et que cela vaut donc le coup de le sortir des oubliettes.
Par exemple : le tri de valeurs du Type Word [0..65535] se réalise chez moi presque instantanément lors d'un tri de 200 000 000 valeurs : mon chrono avec GetTickCount m'affiche " mis : 0 ms" donc ça s'exécute en une fraction de milliseconde.
... mais pour en trier dix fois plus je n'ai plus assez de mem-vive-disponible sauf peut-être en fermant toutes les applis qui tournent en tâche de fond.

A+. :D

---

Encore faut-il n'avoir que des entiers à trier...

Re-salut,

Citation:

---

E-ric : Encore faut-il n'avoir que des entiers à trier...

---

... pas si vite car pour trier :

A) par exemple des valeurs réelles en Euros il suffit de multiplier par 100 avant le tri et effectuer le tri sur des centimes donc des entiers puis rediviser par 100 en fin de tri,

B) des CHAINES de CARACTERES : Le principe du Tri_Casiers est aussi applicable au tri de chaînes de caractères (voir code de la Tri_Casiers_Str dans l'appli téléchargeable) avec les avantages suivants :
Comme la table des caractères ne comporte que 256 codes, la taille du tableau d'occurrences "nbOcc[valeur]" ne dépasse donc jamais 256 et ne risque donc plus d'être la cause d'une saturation de la mémoire disponible.
De plus, dès le tri sur le 1er caractère des chaînes on se retrouve avec au maximum 256 sous-listes (partitionnement) dont les chaînes commençent par un même caractère.
Et toute sous-liste qui à ce stade ne comporterait qu'une seule chaîne ou uniquement des doublons, triplons éventuels, etc se trouve d'entrée de jeu classée quelle que soit sa longueur
(donc inutile de boucler sur toute sa longueur).
Sinon, on trie chaque sous-liste sur le 2ième caractère et on isole dans une sous-liste les chaînes qui commencent par la même SubString,
... puis on trie cette dernière sous-liste sur le 3ième caractère et on isole comme déjà dit,
... et ainsi de suite jusqu'à la fin de chaque chaîne,
... mais on peut aussi se contenter de fixer la profondeur-max du tri aux N premiers caractères des chaînes : gain de speed variable supplémentaire (voir résultats logés dans le code de la
procedure TfrmTriK.bCreerListeChainesPuisTrierCasiersClick()),
... Et vérification faite lors de tests de tris de 1000000 chaînes de 250 caractères et profondeur-max de tri = 250 la profondeur réelle du tri n'a jamais dépassé 9.

Comparatif des performances du Tri_Casiers_Str par rapport à QuickSortRecursif :

B.1) Tri_Casiers_Str sur chaînes de 250 caractères et profondeur-max de tri = 250 :
- pour 500000 chaînes, mis : 951 ms
- pour 1000000 chaînes, mis : 2137 ms
- pour 2000000 chaînes, mis : 4477 ms

B.2) QuickSortRecursif sur chaînes de 250 caractères et profondeur de tri = 250 :
- pour 500000 chaînes, mis : 26037 ms soit 26037/951 = 27,3 fois plus lent qu'avec Tri_Casiers_Str
- pour 1000000 chaînes, mis : 60403 ms soit 60403/2137 = 28,2 fois plus lent qu'avec Tri_Casiers_Str
- pour 2000000 chaînes, mis : 141680 ms soit 141680/4477 = 31,6 fois plus lent qu'avec Tri_Casiers_Str

A+. :D

Les performances sont très intéressantes mais comme je voulais le dire, il faut pouvoir l'appliquer et il reste confiné à des cas particuliers quand même.

Re-salut,

Citation:

---

E-ric : Les performances sont très intéressantes mais comme je voulais le dire, il faut pouvoir l'appliquer et il reste confiné à des cas particuliers quand même.

---

Exact, mais quand on cherche des gains de vitesse et qu'on se trouve dans un de ces types de cas particulier autant en profiter.
... sans oublier que le cas du tri de chaînes bien que particulier se rencontre très fréquemment.
Mais bon si on n'a pas affaire à un ces cas particuliers on en revient au QuickSort de préférence non-récursif.

A+. :D