Implementazione dell'algoritmo di ordinamento QuickSort in Delphi

Uno dei problemi più comuni nella programmazione è ordinare un array di valori in un certo ordine (crescente o decrescente).

Mentre ci sono molti algoritmi di ordinamento "standard", QuickSort è uno dei più veloci. Quicksort ordina usando a dividere e conquistare la strategia per dividere un elenco in due sotto-elenchi.

Algoritmo QuickSort

Il concetto di base è scegliere uno degli elementi dell'array, chiamato a perno. Intorno al perno, altri elementi verranno riorganizzati. Tutto a meno del perno viene spostato a sinistra del perno - nella partizione sinistra. Tutto ciò che è più grande del perno va nella partizione giusta. A questo punto, ogni partizione è "ordinata rapidamente" ricorsiva.

Ecco l'algoritmo QuickSort implementato in Delphi:

 procedura QuickSort (var UN: matrice di Numero intero; iLo, iHi: intero);
var
  Lo, Ciao, Pivot, T: intero;
inizio
  Lo: = iLo;
  Ciao: = iHi;
  Pivot: = A [(Lo + Hi) div 2];
  ripetere
    mentre A [Lo] < Pivot fare Inc (Lo);
    mentre A [Ciao]> Pivot fare Dec (Ciao);
    Se Lo <= Hi poi
    inizio
      T: = A [Lo];
      A [Lo]: = A [Hi];
      A [Ciao]: = T;
      Inc (Lo);
      Dec (Ciao);
    fine;
  fino a Lo> Ciao;
  Se Ciao> iLo poi QuickSort (A, iLo, Hi);
  Se Lo < iHi poi QuickSort (A, Lo, iHi);
fine;

Uso:

 var
  intArray: matrice di numero intero;
inizio
  SetLength (intArray, 10);
  // Aggiungi valori a intArray
  intArray [0]: = 2007;
  ...
  intArray [9]: = 1973;
  //ordinare
  QuickSort (intArray, Low (intArray), High (intArray));

Nota: in pratica, QuickSort diventa molto lento quando l'array passato ad esso è già vicino all'ordinamento.

Esiste un programma demo fornito con Delphi, chiamato "thrddemo" nella cartella "Threads" che mostra altri due algoritmi di ordinamento: Bubble sort e Selection Sort.