Startseite
Informatik
Algorithmen
Sortieren
BucketSort
RadixSort
QuickSort
DRUCK
2004
2005
2006
2007
2008
2009
Zufallsvariante
3-Median-Variante
IntroSort
MergeSort
HeapSort
BubbleSort
SelectionSort
InsertionSort
SlowSort
BogoSort
Komprimieren
Suchen
Primzahltest
Datenstrukturen
Software-Engineering
Programmiersprachen
Künstliche Intelligenz
Schach
Privates
Inhalt
Zufallsvariante
Der Worst Case des QuickSort taucht nur noch in den seltensten Fällen auf!
Der Worst Case des QuickSort taucht nur noch in den seltensten Fällen auf!
Einführung
Theorie der Zufallsvariante des QuickSort
Definition
Die
Zufallsvariante des QuickSort
verbessert den herkömmlichen QuickSort alleinig durch die zufällige Wahl des Pivot-Elements.
Das Pivot-Element wird rein zufällig bestimmt!
// Ein beliebiges Element aus dem zu sortierenden Bereich
Pivot := A[LoIndex + Random(HiIndex - LoIndex)];
„Der Effekt dieser Änderung von QuickSort ist drastisch.
Es gibt keine
schlechten
Eingabefolgen mehr!
Das auf diese Weise
randomisierte
(zufällig gemachte)
QuickSort
behandelt alle Eingabefolgen
(annähernd)
gleich.
Selbstverständlich kann man auch so nicht vermeiden, dass ein schlechtester Fall auftritt,
indem das Verfahren quadratische Schrittzahl benötigt.
Man kann aber leicht zeigen, dass der Erwartungswert für die zum Sortieren einer beliebigen,
aber festen Eingabefolge mit randomisiertem QuickSort erforderliche Anzahl von Schlüsselvergleichen gleich
O(N log N)
ist”,
heißt es in
[ALGODAT].
Beispielsweise wirken sich vorsortierte Listen nicht schlechter als unsortierte Listen auf die Laufzeit aus.
Beispielsweise wirken sich vorsortierte Listen nicht schlechter als unsortierte Listen auf die Laufzeit aus.
Implementierung
Implementierung der Zufallsvariante des QuickSort
Folgende Delphi-Implementierung verändert den herkömmlichen QuickSort derart,
dass jedes Mal beim Bestimmen des Pivot-Elements ein zufälliges Element aus der zu sortierenden
(Teil-)
Liste gewählt wird.
Zufallsvariante des QuickSort mit Delphi
unit URandomQuickSort;
interface
procedure RandomQuickSort(var A: array of Integer);
implementation
procedure RandomQuickSort(var A: array of Integer);
procedure RQSort(LoIndex, HiIndex: Integer);
var
Lo, Hi: Integer;
Pivot: Integer;
Swap: Integer;
begin
{ Zufallsstrategie:
Sei das Pivot-Element stets ein zufällig
gewähltes Element der Liste }
Pivot := A[LoIndex + Random(HiIndex - LoIndex)];
{ 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 RQSort(LoIndex, Hi);
if Lo < HiIndex then RQSort(Lo, HiIndex);
end;
begin
RQSort(Low(A), High(A));
end;
initialization
Randomize;
end.
Folgende Java-Implementierung verändert den herkömmlichen QuickSort überhaupt nicht!
Bei Erhalt der zu sortierenden Liste werden zunächst die drinliegenden Elemente mittels shuffle vermischt. Nachdem nun die Elemente richtig durchgeschüttelt sind, wird der herkömmliche QuickSort darauf angewendet.
Dabei sei bemerkt, dass die durchschnittliche Zeit-Komplexität O(n log n) trotz der zusätzlichen shuffle-Funktion erhalten bleibt.
Die shuffle-Methode swapped (hier) alle Elemente der Liste mit der Komplexität O(n) durch, wobei der QuickSort bekannter Weise die durchschnittliche Komplexität O(n log n) hat. Der Schnitt dieser Laufzeit-Abschätzungen beträgt also immer noch O(n log n).
Eine bessere Effizienz verspricht jedoch die obige Realisierung mit Delphi, auch wenn shuffle aus irgendeinem Grunde optimiert werden sollte :-)
Bei Erhalt der zu sortierenden Liste werden zunächst die drinliegenden Elemente mittels shuffle vermischt. Nachdem nun die Elemente richtig durchgeschüttelt sind, wird der herkömmliche QuickSort darauf angewendet.
Dabei sei bemerkt, dass die durchschnittliche Zeit-Komplexität O(n log n) trotz der zusätzlichen shuffle-Funktion erhalten bleibt.
Die shuffle-Methode swapped (hier) alle Elemente der Liste mit der Komplexität O(n) durch, wobei der QuickSort bekannter Weise die durchschnittliche Komplexität O(n log n) hat. Der Schnitt dieser Laufzeit-Abschätzungen beträgt also immer noch O(n log n).
Eine bessere Effizienz verspricht jedoch die obige Realisierung mit Delphi, auch wenn shuffle aus irgendeinem Grunde optimiert werden sollte :-)
Zufallsvariante des QuickSort mit Java
import java.util.Random;
public class IntSorter {
/**
* Würfle erst die Elemente durcheinander und
* wende dann den Standard-Quicksort an.
*/
public static void randomizedQuicksort(int[] values) {
if (values != null) {
shuffle(values);
quicksort(values, 0, values.length - 1);
}
}
/**
* Würfle die Elemente durcheinander z.B. so:
*/
private static void shuffle(int[] values) {
Random random = new Random();
for (int i = 0; i < values.length; i++) {
// k ist irgendein gültiger Index des Arrays
int k = random.nextInt(values.length);
int swp = values[k];
values[k] = values[i];
values[i] = swp;
}
}
/**
* Ein ganz normaler QuickSort! (Standard)
* Beispielsweise sehr langsam bei vorsortierten Listen: O(n*n).
*/
private static void quicksort(int[] values, int left, int right) {
// Sei das Pivot-Element stets das rechte Grenzelement!
int pivot = values[right];
int l = left;
int r = right;
do {
while (values[l] < pivot) l++;
while (values[r] > pivot) r--;
if (l <= r) {
int swap = values[l];
values[l++] = values[r];
values[r--] = swap;
}
} while (l <= r);
if (left < r) quicksort(values, left, r);
if (l < right) quicksort(values, l, right);
}
}
Es bleibt nun Ihrem Ehrgeiz überlassen, die
Java-Methode
shuffle
in seinem Laufzeitverhalten zu verbessern;
das Mischergebnis darf aber nicht stark darunter leiden.
Quellenangabe
-
[ALGODAT]