Datenstruktur und Algorithmen - Schnelle Sortierung

Die schnelle Sortierung ist ein hocheffizienter Sortieralgorithmus und basiert auf der Partitionierung von Datenarrays in kleinere Arrays. Ein großes Array wird in zwei Arrays aufgeteilt, von denen eines Werte enthält, die kleiner als der angegebene Wert sind, z. B. Pivot, basierend auf dem die Partition erstellt wird, und ein anderes Array Werte enthält, die größer als der Pivot-Wert sind.

Quicksort partitioniert ein Array und ruft sich dann zweimal rekursiv auf, um die beiden resultierenden Subarrays zu sortieren. Dieser Algorithmus ist für große Datenmengen sehr effizient, da seine durchschnittliche und die Worst-Case-Komplexität O (n ² ) betragen.

Partition in Quick Sort

Die folgende animierte Darstellung erklärt, wie Sie den Pivot-Wert in einem Array finden.

Der Pivot-Wert teilt die Liste in zwei Teile. Und rekursiv finden wir den Drehpunkt für jede Unterliste, bis alle Listen nur noch ein Element enthalten.

Schneller Sortier-Pivot-Algorithmus

Basierend auf unserem Verständnis der Partitionierung in schneller Sortierung werden wir nun versuchen, einen Algorithmus dafür zu schreiben, der wie folgt lautet.

Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot

Quick Sort Pivot Pseudocode

Der Pseudocode für den obigen Algorithmus kann abgeleitet werden als -

function partitionFunc(left, right, pivot)
   leftPointer = left
   rightPointer = right - 1

   while True do
      while A[++leftPointer] < pivot do
         //do-nothing            
      end while
		
      while rightPointer > 0 && A[--rightPointer] > pivot do
         //do-nothing         
      end while
		
      if leftPointer >= rightPointer
         break
      else                
         swap leftPointer,rightPointer
      end if
		
   end while 
	
   swap leftPointer,right
   return leftPointer
	
end function

Schneller Sortieralgorithmus

Wenn wir den Pivot-Algorithmus rekursiv verwenden, erhalten wir kleinere mögliche Partitionen. Jede Partition wird dann zur schnellen Sortierung verarbeitet. Wir definieren den rekursiven Algorithmus für Quicksort wie folgt:

Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively

Pseudocode schnell sortieren

Weitere Informationen finden Sie im Pseudocode für den schnellen Sortieralgorithmus.

procedure quickSort(left, right)

   if right-left <= 0
      return
   else     
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition+1,right)    
   end if		
   
end procedure

Klicken Sie hier , um Informationen zur schnellen Implementierung der Sortierung in der Programmiersprache C zu erhalten .