QuickSort: Unterschied zwischen den Versionen

Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springen
Zeile 1: Zeile 1:
 +
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===
 
===Laufzeit===
 
  best-case    : log n<br/>
 
  best-case    : log n<br/>
 
  average-case : log n<br/>
 
  average-case : log n<br/>
  worst-case  : n²  <br/>
+
  worst-case  : n²  bzw. log n (Random-QuickSort) <br/>
 
  stabil      : nein
 
  stabil      : nein
  

Version vom 21. September 2008, 17:34 Uhr

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