Implémentation de l'algorithme de tri QuickSort dans Delphi

L'un des problèmes courants en programmation est de trier un tableau de valeurs dans un ordre (croissant ou décroissant).

Bien qu'il existe de nombreux algorithmes de tri "standard", QuickSort est l'un des plus rapides. Quicksort trie en utilisant un diviser pour mieux régner diviser une liste en deux sous-listes.

Algorithme QuickSort

Le concept de base consiste à choisir l'un des éléments du tableau, appelé pivot. Autour du pivot, d'autres éléments seront réorganisés. Tout ce qui est inférieur au pivot est déplacé à gauche du pivot - dans la partition de gauche. Tout ce qui dépasse le pivot va dans la partition de droite. À ce stade, chaque partition est récursive "tri rapide".

Voici l'algorithme QuickSort implémenté dans Delphi:

 procédure Tri rapide(var UNE: tableau de Entier; iLo, iHi: Entier);
var
  Lo, Hi, Pivot, T: Entier;
commencer
  Lo: = iLo;
  Salut: = iHi;
  Pivot: = A [(Lo + Hi) div 2];
  répéter
    tandis que A [Lo] < Pivot faire Inc (Lo);
    tandis que A [Salut]> Pivot faire Dec (Salut);
    si Lo <= Hi ensuite
    commencer
      T: = A [Lo];
      A [Lo]: = A [Hi];
      A [Salut]: = T;
      Inc (Lo);
      Dec (Salut);
    fin;
  jusqu'à Lo> Salut;
  si Salut> iLo ensuite QuickSort (A, iLo, Salut);
  si Lo < iHi ensuite QuickSort (A, Lo, iHi);
fin;

Usage:

 var
  intArray: tableau de entier;
commencer
  SetLength (intArray, 10);
  // Ajouter des valeurs à intArray
  intArray [0]: = 2007;
  …
  intArray [9]: = 1973;
  //Trier
  QuickSort (intArray, Low (intArray), High (intArray));

Remarque: en pratique, le QuickSort devient très lent lorsque le tableau qui lui est passé est déjà près d'être trié.

Il existe un programme de démonstration fourni avec Delphi, appelé "thrddemo" dans le dossier "Threads", qui présente deux algorithmes de tri supplémentaires: le tri à bulles et le tri à sélection.