QuickSort

Laufzeit

best-case    : log n

average-case : log n

worst-case   : n²  

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