Computerwissenschaften

Implementierung 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 mithilfe einer Divide and Conquer-Strategie , um eine Liste in zwei Unterlisten zu unterteilen.

 

QuickSort-Algorithmus

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

Hier ist der in Delphi implementierte QuickSort-Algorithmus:


 Prozedur QuickSort ( var A: Array von Integer; iLo, iHi: Integer); 
 var
Lo, Hi, Pivot, T: Ganzzahl; 
begin 
   Lo:=iLo; 
   Hi:=iHi; 
   Pivot:=A [(Lo + Hi) div 2]; 
   wiederholen, 
 während A [Lo] do Inc (Lo); 
 während A [Hi]> Pivot do Dec (Hi); 
 wenn Lo <= Hi, dann 
 beginne
T:=A [Lo]; 
   A [Lo]:=A [Hi]; 
   A [Hi]:=T; 
   Inc (Lo); 
   Dec (Hi); 
 Ende ; 
   bis Lo> Hi; 
   wenn Hi> iLo dann QuickSort (A, iLo, Hi); 
   wenn Lo <iHi, dann QuickSort (A, Lo, iHi); 
 Ende ;

Verwendung:


 var
intArray: Array von Ganzzahlen; 
 begin
SetLength (intArray, 10); 
 
   // Werte zu intArray hinzufügen
intArray [0]:=2007; 
   ... 
   intArray [9]:=1973; 
 
   // sortiere
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 mit dem Namen „thrddemo“ im Ordner „Threads“ enthalten, das zwei zusätzliche Sortieralgorithmen enthält: Blasensortierung und Auswahlsortierung.

Similar Posts

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.