Implementieren des QuickSort-Sortieralgorithmus in Delphi

Eines der häufigsten Probleme bei der Programmierung besteht darin, ein Array von Werten in einer bestimmten Reihenfolge (aufsteigend oder absteigend) zu sortieren..

Obwohl es viele "Standard" -Sortieralgorithmen gibt, ist QuickSort einer der schnellsten. Quicksort sortiert nach a Strategie teilen und erobern eine Liste in zwei Unterlisten aufteilen.

QuickSort-Algorithmus

Das Grundkonzept besteht darin, eines der Elemente im Array auszuwählen, das als a bezeichnet wird schwenken. Um den Drehpunkt herum werden andere Elemente neu angeordnet. Alles, was weniger als der Drehpunkt ist, wird vom Drehpunkt nach links bewegt - in die linke Partition. Alles, was größer als der Drehpunkt ist, geht in die rechte Partition. Zu diesem Zeitpunkt ist jede Partition rekursiv "schnell sortiert".

Hier ist der in Delphi implementierte QuickSort-Algorithmus:

 Verfahren Schnelle Sorte(var EIN: Anordnung von Ganze Zahl; iLo, iHi: Integer);
var
  Lo, Hi, Pivot, T: Integer;
Start
  Lo: = iLo;
  Hi: = iHi;
  Drehpunkt: = A [(Lo + Hi) div 2];
  wiederholen
    während A [Lo] < Pivot tun Inc (Lo);
    während A [Hi]> Pivot tun Dez (Hi);
    wenn Lo <= Hi dann
    Start
      T: = A [Lo];
      A [Lo]: = A [Hi];
      A [Hi]: = T;
      Inc (Lo);
      Dez (Hi);
    Ende;
  bis um Lo> Hi;
  wenn Hi> iLo dann QuickSort (A, iLo, Hi);
  wenn Lo < iHi dann QuickSort (A, Lo, iHi);
Ende;

Verwendung:

 var
  intArray: Anordnung von ganze Zahl;
Start
  SetLength (intArray, 10);
  // Werte zu intArray hinzufügen
  intArray [0]: = 2007;
  …
  intArray [9]: = 1973;
  //Sortieren
  QuickSort (intArray, Low (intArray), High (intArray));

Hinweis: In der Praxis wird der QuickSort sehr langsam, wenn das an ihn übergebene Array bereits kurz vor der Sortierung steht.

Im Lieferumfang von Delphi ist ein Demo-Programm namens "thrddemo" im Ordner "Threads" enthalten, das zwei zusätzliche Sortieralgorithmen enthält: Blasensortierung und Auswahlsortierung.