QuickSort: Unterschied zwischen den Versionen
Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springen (Die Seite wurde neu angelegt: ===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 )==== ...) |
|||
| (4 dazwischenliegende Versionen von einem anderen Benutzer werden nicht angezeigt) | |||
| 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=== | ||
| + | best-case : log n | ||
| + | average-case : log n | ||
| + | worst-case : n² bzw. log n (Random-QuickSort) | ||
| + | stabil : nein | ||
| + | |||
===Psydocode:=== | ===Psydocode:=== | ||
====QuickSort(H,l,r)==== | ====QuickSort(H,l,r)==== | ||
| − | if l < r then m:= Partition( H,l,r ) | + | <b>if</b> l < r <b>then</b> m:= <b>Partition(</b> H,l,r <b>)</b> |
| − | QuickSort( H , l , m-1 ) | + | <b>QuickSort(</b> H , l , m-1 <b>)</b> |
| − | QuickSort( H , m-1 , r ) | + | <b>QuickSort(</b> H , m-1 , r <b>)</b> |
====Partition( H,l,r )==== | ====Partition( H,l,r )==== | ||
i = l - 1 | i = l - 1 | ||
| − | for j := 1 to r-1 do | + | <b>for</b> j := 1 <b>to</b> r-1 <b>do</b> |
| − | if H[j] <= H[r] then | + | <b>if</b> H[j] <= H[r] <b>then</b> |
i = i + 1 | i = i + 1 | ||
| − | if i < j then | + | <b>if</b> i < j <b>then</b> |
| − | change( H[i] , H[j] ) | + | <b>change(</b> H[i] , H[j] <b>)</b> |
| − | if i+1 < r then | + | <b>if</b> i+1 < r <b>then</b> |
| − | change( H[i+1] , H[r] ) | + | <b>change(</b> H[i+1] , H[r] <b>)</b> |
| − | return i+1 | + | <b>return</b> i+1 |
| − | [[Kategorie: | + | [[Kategorie:Algorithmentheorie]] |
Aktuelle Version vom 23. September 2008, 01:16 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.
Inhaltsverzeichnis
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
