Startseite
Informatik
Algorithmen
Sortieren
BucketSort
RadixSort
QuickSort
Zufallsvariante
DRUCK
2004
2005
2006
2007
2008
2009
3-Median-Variante
IntroSort
MergeSort
HeapSort
BubbleSort
SelectionSort
InsertionSort
SlowSort
BogoSort
Komprimieren
Suchen
Primzahltest
Datenstrukturen
Software-Engineering
Programmiersprachen
Künstliche Intelligenz
Schach
Privates
Inhalt
3-Median-Variante
Der Worst Case des QuickSort taucht so gut wie nie auf!
Der Worst Case des QuickSort taucht so gut wie nie auf!
Einführung
Theorie: QuickSort
Definition
„Im Falle der
3-Median-Strategie
wird als Pivot-Element der Median
(d. h. das mittlere)
von drei Elementen im aufzuteilenden Bereich gewählt.
Wählt man die drei Elemente vom linken und rechten Ende und aus der Mitte, so besteht eine gute Chance dafür,
dass das mittlere dieser drei Elemente eine Aufteilung in annähernd gleiche Teile liefert”,
heißt es in
[ALGODAT].
Desweiteren schlägt [ALGODAT]vor:
„Um das Mittlere von drei Elementen
a, b, c
zu bestimmen, die nicht paarweise verschieden sein müssen, kann man wie folgt vorgehen.”
Desweiteren schlägt [ALGODAT]
vor:
„Um das Mittlere von drei Elementen
a, b, c
zu bestimmen, die nicht paarweise verschieden sein müssen, kann man wie folgt vorgehen.”
Bestimme Median von a, b und c!
if a > b then vertausche(a, b);
{ a = min(a, b) }
if a > c then vertausche(a, c);
{ a = min(a, b, c) }
if b > c then vertausche(b, c);
{ a, b, c sind jetzt aufsteigend sortiert; also ist b das mittlere
der drei Elemente a, b, c }
Komplexität
Zur Bestimmung des Medians aus drei Elementen benötigt man stets konstante Zeit, also
O(1).
Um diese drei Elemente aus einem
Array
auszulesen, benötigt man ebenfalls nur konstante Zeit,
deshalb bleibt bei dieser Variante des QuickSort die
durchschnittliche
Laufzeit-Komplexität
O(n log n)
erhalten.
Aber selbst hier kann der worst case nicht ausgeschlossen werden. Man stelle sich nur vor, dass zur Medianbestimmung unter den drei gewählten Elementen stets zwei gleichwertige Elemente wären. Der Median wäre dann ein Element von den beiden gleichwertigen Elementen, welches dann schlechtestenfalls stets ein Extremum der jeweiligen Teilliste sein könnte.
Um den besagten worst case noch unwahrscheinlicher zu gestalten, könnte man sich Gedanken zu einem 5-Median-QuickSort in Kombination mit der Zufallsvariante machen, oder man lässt es gleich bleiben :-)
Aber selbst hier kann der worst case nicht ausgeschlossen werden. Man stelle sich nur vor, dass zur Medianbestimmung unter den drei gewählten Elementen stets zwei gleichwertige Elemente wären. Der Median wäre dann ein Element von den beiden gleichwertigen Elementen, welches dann schlechtestenfalls stets ein Extremum der jeweiligen Teilliste sein könnte.
Um den besagten worst case noch unwahrscheinlicher zu gestalten, könnte man sich Gedanken zu einem 5-Median-QuickSort in Kombination mit der Zufallsvariante machen, oder man lässt es gleich bleiben :-)
Implementierung
Implementierung der Zufallsvariante des QuickSort
3-Median-Variante des QuickSort mit Delphi
unit UMedian3QuickSort;
interface
procedure Median3QuickSort(var A: array of Integer);
implementation
uses
Math; // wegen Nutzung der Min-Max-Funktionen
procedure Median3QuickSort(var A: array of Integer);
procedure M3QSort(LoIndex, HiIndex: Integer);
var
Lo, Hi: Integer;
Left, Middle, Right, Median: Integer;
Pivot: Integer;
Swap: Integer;
begin
{ 3-Median-Strategie:
Sei das Pivot-Element stets
der Median von Links-Mitte-Rechts! }
// Die drei Elemente der zu sortierenden Liste
Left := A[LoIndex];
Middle := A[(LoIndex + HiIndex) div 2];
Right := A[HiIndex];
// Bestimme den Median
Median := Middle;
if Middle = MinIntValue([Left, Middle, Right])
then Median := Min(Left, Right);
if Middle = MaxIntValue([Left, Middle, Right])
then Median := Max(Left, Right);
Pivot := Median;
{ Der Rest wie gehabt! }
Lo := LoIndex;
Hi := HiIndex;
repeat
while A[Lo] < Pivot do Inc(Lo);
while A[Hi] > Pivot do Dec(Hi);
if Lo <= Hi then
begin
Swap := A[Lo];
A[Lo] := A[Hi];
A[Hi] := Swap;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if LoIndex < Hi then M3QSort(LoIndex, Hi);
if Lo < HiIndex then M3QSort(Lo, HiIndex);
end;
begin
M3QSort(Low(A), High(A));
end;
end.
Quellenangabe
-
[ALGODAT]