DAA - Schnelle Sortierung

Es wird nach dem Prinzip des Teilens und Eroberens verwendet. Die schnelle Sortierung ist in vielen Situationen ein Algorithmus der Wahl, da die Implementierung nicht schwierig ist. Es ist eine gute Allzweck-Sorte und verbraucht während der Ausführung relativ weniger Ressourcen.

Vorteile

• Es ist vorhanden, da nur ein kleiner Hilfsstapel verwendet wird.

• Es erfordert nur n (log n) Zeit zu sortieren n Artikel.

• Es hat eine extrem kurze innere Schleife.

• Dieser Algorithmus wurde einer gründlichen mathematischen Analyse unterzogen, wobei eine sehr genaue Aussage über Leistungsprobleme getroffen werden kann.

Nachteile

• Es ist rekursiv. Insbesondere wenn keine Rekursion verfügbar ist, ist die Implementierung äußerst kompliziert.

• Im schlimmsten Fall ist eine quadratische Zeit (dh n2) erforderlich.

• Es ist fragil, dh ein einfacher Fehler in der Implementierung kann unbemerkt bleiben und zu einer schlechten Leistung führen.

Die schnelle Sortierung funktioniert durch Partitionieren eines bestimmten Arrays A[p ... r] in zwei nicht leere Sub-Array A[p ... q] und A[q+1 ... r] so dass jeder Schlüssel in A[p ... q] ist kleiner oder gleich jedem Schlüssel in A[q+1 ... r].

Anschließend werden die beiden Unterarrays durch rekursive Aufrufe der Schnellsortierung sortiert. Die genaue Position der Partition hängt vom angegebenen Array und Index abq wird als Teil der Partitionierungsprozedur berechnet.

Algorithm: Quick-Sort (A, p, r) 
if p < r then 
   q Partition (A, p, r) 
   Quick-Sort (A, p, q) 
   Quick-Sort (A, q + r, r)

Beachten Sie, dass zum Sortieren des gesamten Arrays der erste Aufruf erfolgen sollte Quick-Sort (A, 1, length[A])

In einem ersten Schritt wählt Quick Sort eines der Elemente im Array aus, die als Pivot sortiert werden sollen. Dann wird das Array auf beiden Seiten des Pivots partitioniert. Elemente, die kleiner oder gleich dem Drehpunkt sind, bewegen sich nach links, während sich die Elemente, die größer oder gleich dem Drehpunkt sind, nach rechts bewegen.

Partitionieren des Arrays

Durch das Partitionierungsverfahren werden die Unterarrays an Ort und Stelle neu angeordnet.

Function: Partition (A, p, r) 
x ← A[p] 
i ← p-1 
j ← r+1 
while TRUE do 
   Repeat j ← j - 1 
   until A[j] ≤ x  
   Repeat i← i+1 
   until A[i] ≥ x  
   if i < j then  
      exchange A[i] ↔ A[j] 
   else  
      return j

Analyse

Die Worst-Case-Komplexität des Quick-Sort-Algorithmus ist O(n²). Mit dieser Technik erhalten wir jedoch im Durchschnitt die Ausgabe inO(n log n) Zeit.