 | IntroSortDer IntroSort ist ein QuickSort, der in entarteten Fällen auf andere schnelle Sortierverfahren zurückgreift.
Definition
IntroSort ist eine Variante von QuickSort, welche in für den reinen QuickSort ungünstigen Fällen auf andere, eher weniger effiziente Sortierverfahren (MergeSort oder HeapSort) zurückgreift, um im schlechtesten Fall (worst case) eine Laufzeitkomplexität von O(n log n) garantieren zu können.
Einleitend bei jedem Rekursionsschritt des QuickSort wird anhand einer Bewertungsfunktion entschieden, ob ein anderes Sortierverfahren die Sortierung aktueller (Teil−) Liste übernehmen soll.
Mit IntroSort möchte man die unübertroffene Effizienz des QuickSort soweit wie möglich auskosten.
|
Komplexität
Dieses Sortierverfahren garantiert eine Laufzeitkomplexität von O(n log n) natürlich nur dann, wenn das Behelfssortierverfahren, auf welches gegebenenfalls umgeleitet wird, ebenfalls die Laufzeitkomplexität von O(n log n) garantiert. Beispielsweise käme der BubbleSort mit der Laufzeitabschätzung O(n * n) hierbei nicht in Frage.
|
Folgende Implementierung demonstriert einen IntroSort, der sich nötigenfalls mittels HeapSort behilft. Die Bewertungsfunktion UseQuickSort ist der 3−Median−Methode sehr ähnlich, siehe 3−Median−Variante.
Das Herz des vorliegenden IntroSort ist die lokale Prozedur ISort.
|
Implementierung mit Delphi
unit UIntroSort;
interface
procedure IntroSort(var A: array of Integer);
implementation
procedure IntroSort(var A: array of Integer);
(* "ISort" und "IQuickSort" sind in ihrer Rekursion verschränkt,
damit bei jedem Rekursionsaufruf anhand der Bewertungsfunktion
"UseQuickSort" entschieden werden kann, welches Sortierverfahren
zur jeweiligen Teilliste angewendet werden soll.
Aufgrund der verschränkten Rekursion muss zumindest eine
der beiden genannten Funktionen als forward deklariert werden. *)
procedure ISort(LoIndex, HiIndex: Integer); forward;
(* "HeapSort" als Alternative nur für den Notfall! *)
procedure HeapSort(LoIndex, HiIndex: Integer);
procedure SiftDown(Current, MaxIndex: Integer);
var
Left, Right, Largest, Swp: Integer;
begin
Left := LoIndex + (2 * (Current - LoIndex)) + 1;
Right := LoIndex + (2 * (Current - LoIndex)) + 2;
Largest := Current;
if (Left <= MaxIndex) and (A[Left] > A[Largest]) then Largest := Left;
if (Right <= MaxIndex) and (A[Right] > A[Largest]) then Largest := Right;
if (Largest <> Current) then
begin
Swp := A[Current];
A[Current] := A[Largest];
A[Largest] := Swp;
SiftDown(Largest, MaxIndex);
end;
end;
var Swp, i: Integer;
begin
for i := ((LoIndex + HiIndex + 1) div 2) - 1 downto LoIndex do
SiftDown(i, HiIndex);
for i := HiIndex downto LoIndex + 1 do
begin
Swp := A[i];
A[i] := A[LoIndex];
A[LoIndex] := Swp;
SiftDown(LoIndex, i - 1);
end;
end; // HeapSort
(* "IQuickSort" (indirekt rekursiv) ist ein modifizierter QuickSort. *)
procedure IQuickSort(LoIndex, HiIndex: Integer);
var Lo, Hi, Pivot, Swap: Integer;
begin
Lo := LoIndex;
Hi := HiIndex;
Pivot := A[Lo];
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 ISort(LoIndex, Hi); // keine direkte Rekursion!
if Lo < HiIndex then ISort(Lo, HiIndex); // keine direkte Rekursion!
end; // IQuickSort
(* "UseQuickSort" ist eine heuristische Bewertungsfunktion,
die den WorstCase O(n*n) ausschliessen muss
und selbst nur konstante Zeit O(1) benötigen darf.
Welcher Bewertungsstrategie sonst noch gefolgt werden soll,
bleibt noch offen,
sollte aber im Sinne der Gesamteffizienz des "IntroSort" erörtert werden!
Hier ganz simple:
Wenn nun Middle nicht der tatsächliche Median bzgl. der Grenzelemente
der jeweiligen Teilliste ist, dann darf der QuickSort angewendet werden. *)
function UseQuickSort(LoIndex, HiIndex: Integer): Boolean;
var Middle: Integer;
begin
Middle := A[(LoIndex + HiIndex) div 2];
Result := not (((A[LoIndex] < Middle) and (Middle < A[HiIndex]))
or ((A[HiIndex] < Middle) and (Middle < A[LoIndex])));
end;
(* Mit "ISort" wird in jedem Rekursionsschritt entschieden,
ob nun der QuickSort oder der HeapSort angewendet werden soll. *)
procedure ISort(LoIndex, HiIndex: Integer);
begin
if UseQuickSort(LoIndex, HiIndex)
then IQuickSort(LoIndex, HiIndex)
else HeapSort(LoIndex, HiIndex); // bzw. MergeSort(LoIndex, HiIndex)
end;
begin
ISort(Low(A), High(A)); // Der Anstoß, kick off!
end;
end. | |
Heute schon gerendert? | |
| Seiten - Informationen
Diese Seite ist Bestandteil der Domäne „www.stefan−baur.de” und heißt IntroSort. Die letzte Änderung erfuhr diese Seite am Sonntag, den 15. März 2009 von Stefan K. Baur. Zuletzt wurde sie von Ihnen am Mittwoch, den 8. September 2010 um 3:39 Uhr im Internet besucht. Sie gelangen zur vorliegenden Seite, wenn Sie ausgehend von der Startseite über dem Hauptmenü wie folgt navigieren:
Wenn Sie die vorliegende Seite ausdrucken möchten, nutzen Sie dazu die Printversion.
|
- QuickSort
Einer der schnellsten Sortieralgorithmen, welcher auf Vergleichen beruht, ist der QuickSort! - HeapSort
Ein relevanter Sortieralgorithmus, welcher die Datenstruktur Heap benutzt, ist der HeapSort!
|
Das aktuelle Design trägt den Namen „Design 2006”.
Falls Ihnen jedoch das aktuelle Design nicht zusagen sollte, so stehen Ihnen noch andere, alternative Designs zur Verfügung: |
Copyright (c) 2004-2010 Stefan K. Baur | |
