Discussion :

[khayyam90]

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 ?

[e-ric]

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.

[Pascal Jankowski]

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

Par Insertion.

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
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 :

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

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]

[e-ric]

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

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.

[Gilbert Geyer]

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+.

[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.