QuickSort

QuickSort geht nach dem Prinzip "teile und hersche" (engl. "Divide and Conquer") vor. In jedem Schritt wird ein Pivotelement gewählt und die kleineren Elemente auf die eine Seite bzw alle größeren Elemente auf die andere Seite verschoben. Das Pivotelement befindet sich nun schon einmal an der richtigen Stelle. Jetzt wird dieses Vorgehen rekursiv oder iterativ für beide Seiten solange wiederholt, bis es nur noch ein-elementige Listen sind und nun werden alle Elemente die sich nun schon an den richtigen Stellen befinden zu einer sortierten Liste wieder zusammengefügt. QuickSort ist nicht stabil, was bedeutet, daß die relative Reihenfolge der zu sortierenden Elemente nicht eingehalten wird.

Laufzeit

best-case    : log n

average-case : log n

worst-case   : n²  bzw. log n (Random-QuickSort) 

stabil       : nein

Psydocode:

QuickSort(H,l,r)

if l < r then m:= Partition( H,l,r )
  QuickSort( H , l , m-1 )
  QuickSort( H , m-1 , r ) 

Partition( H,l,r )

i = l - 1
for j := 1 to r-1 do
  if H[j] <= H[r] then 
     i = i + 1
     if i < j then
       change( H[i] , H[j] )
if i+1 < r then
  change( H[i+1] , H[r] )
return i+1