Smoothsort (Methode) ist ein Vergleich-basierter Sortieren-Algorithmus. Es ist eine Schwankung von heapsort, der von Edsger Dijkstra 1981 entwickelt ist. Wie heapsort ist smoothsort's ober gebunden O (n loggen n). Der Vorteil von smoothsort besteht darin, dass er näher an O (n) Zeit kommt, wenn der Eingang bereits zu einem gewissen Grad sortiert wird, wohingegen heapsort Durchschnitte O (n loggen n), unabhängig von der Initiale sortierter Staat.

Übersicht

Wie heapsort baut smoothsort eine implizite Haufen-Datenstruktur in der Reihe auf, die zu sortieren ist, sortiert dann die Reihe durch das dauernde Extrahieren des maximalen Elements aus diesem Haufen. Verschieden von heapsort verwendet smoothsort keinen binären Haufen, aber eher einen kundenspezifischen Haufen, der auf den Zahlen von Leonardo L (n) gestützt ist. Die Haufen-Struktur besteht aus einer Reihe von Haufen, von denen die Größen alle Zahlen von Leonardo sind, und dessen Wurzeln in aufsteigender Reihenfolge versorgt werden. Der Vorteil dieses kundenspezifischen Haufens über binäre Haufen besteht darin, dass, wenn die Folge bereits sortiert wird, es Zeit in Anspruch nimmt, um den Haufen, folglich die bessere Durchlaufzeit zu bauen und zu dekonstruieren.

Das Zerbrechen des Eingangs in eine Folge von Haufen ist einfach - die leftmost Knoten der Reihe werden in den größten Haufen möglich gemacht, und der Rest wird ebenfalls zerteilt. Es kann dass bewiesen werden:

• Jede Reihe jeder Länge kann in Abteilungen der Größe L (x) so zerteilt werden.
• Keine zwei Haufen werden dieselbe Größe haben. Die Schnur wird deshalb eine Reihe von Haufen sein, die ausschließlich in der Größe hinuntersteigen.
• Keine zwei Haufen werden Größen haben, die Konsekutivzahlen von Leonardo abgesehen von vielleicht den endgültigen zwei sind.

Jeder Haufen, eine Größe von L (x) habend, wird vom linken bis Recht als ein Subhaufen der Größe L (x-1), ein Subhaufen der Größe L (x-2) und ein Wurzelknoten, mit Ausnahme von Haufen mit einer Größe von L (1) und L (0) strukturiert, die Singleton-Knoten sind. Jeder Haufen erhält das Haufen-Eigentum aufrecht, dass ein Wurzelknoten immer mindestens so groß ist wie die Wurzelknoten seiner Kinderhaufen (und deshalb mindestens so groß wie alle Knoten in seinen Kinderhaufen), und die Reihe von Haufen als Ganzes das Schnur-Eigentum aufrechterhält, dass der Wurzelknoten jedes Haufens mindestens so groß ist wie der Wurzelknoten des Haufens nach links.

Die Folge davon ist, dass der niedrigstwertige Knoten in der Schnur immer von den Knoten am größten sein wird, und, wichtig, eine Reihe, die bereits sortiert wird, keine Neuordnung braucht, die in eine gültige Reihe von Haufen zu machen ist. Das ist die Quelle der anpassungsfähigen Qualitäten des Algorithmus.

Der Algorithmus ist einfach. Wir fangen an, indem wir unsere unsortierte Reihe in einen einzelnen Haufen eines Elements zerteilen, das von einem unsortierten Teil gefolgt ist. Eine Ein-Element-Reihe ist trivial eine gültige Folge von Haufen. Diese Folge wird dann durch das Hinzufügen eines Elements auf einmal nach rechts, das Durchführen des Tausches angebaut, um das Folge-Eigentum und das Haufen-Eigentum zu behalten, bis es die komplette ursprüngliche Reihe füllt.

Von diesem Punkt auf wird das niedrigstwertige Element der Folge von Haufen das größte Element in einigen der Haufen sein, und wird deshalb in seiner richtigen, endgültigen Position sein. Wir nehmen dann ab die Reihen von Haufen treten zu einem einzelnen Haufen eines Elements durch das Entfernen des niedrigstwertigen Knotens zurück (der im Platz bleibt), und leistende Neuordnungen, um die Haufen-Bedingung wieder herzustellen. Wenn wir sind, treten zu einem einzelnen Haufen eines Elements zurück, die Reihe wird sortiert.

Operationen

Wenn sie

(im Augenblick) die Optimierungen von Dijkstra ignorieren, sind zwei Operationen notwendig - vergrößern die Schnur durch das Hinzufügen eines Elements nach rechts, und vermindern die Schnur durch das Entfernen des Rechts der grösste Teil des Elements (die Wurzel des letzten Haufens), die Bewahrung des Haufens und spannen Bedingungen.

Bauen Sie die Schnur an, indem Sie ein Element nach rechts hinzufügen

• Wenn die letzten zwei Haufen der Größe L (x+1) und L (x) sind (d. h.: Leonardo Konsekutivzahlen), das neue Element wird der Wurzelknoten eines größeren Haufens der Größe L (x+2). Dieser Haufen wird das Haufen-Eigentum nicht notwendigerweise haben.
• Wenn die letzten zwei Haufen der Schnur nicht Konsekutivzahlen von Leonardo sind, dann wird das niedrigstwertige Element ein neuer Haufen der Größe 1. Dieser 1 wird genommen, um L (1) zu sein, wenn der niedrigstwertige Haufen bereits Größe L (1) nicht hat, in welchem Fall der neue Ein-Element-Haufen genommen wird, um der Größe L (0) zu sein.

Danach müssen der Haufen und die Schnur-Eigenschaften wieder hergestellt werden, der gewöhnlich über eine Variante der Einfügungssorte getan wird. Das wird wie folgt getan:

1. Der niedrigstwertige Haufen (derjenige, der gerade geschaffen worden ist) wird der "aktuelle" Haufen
2. Während es einen Haufen links vom aktuellen Haufen gibt und seine Wurzel größer ist, als die aktuelle Wurzel und beide seines Kinderhaufens einwurzeln lassen
3. * tauschen Dann die neue Wurzel mit der Wurzel auf dem Haufen nach links (das wird das Haufen-Eigentum des aktuellen Haufens nicht stören). Dieser Haufen wird dann der aktuelle Haufen.
4. Führen Sie eine "Filter"-Operation auf dem aktuellen Haufen durch, um das Haufen-Eigentum zu gründen:
5. *While der aktuelle Haufen hat eine Größe, die größer ist als 1 und jeder Kinderhaufen des aktuellen Haufens, hat einen Wurzelknoten, der größer ist als die Wurzel des aktuellen Haufens
6. ** Tauschen Sie die größere Kinderwurzel mit der aktuellen Wurzel. Dieser Kinderhaufen wird der aktuelle Haufen.

Die Filteroperation wird durch den Gebrauch von Zahlen von Leonardo außerordentlich vereinfacht, weil ein Haufen immer entweder ein einzelner Knoten sein wird, oder zwei Kinder haben wird. Man braucht die Bedingung von einem der Kinderhaufen nicht zu führen, die nicht da sind.

Optimierung

• Wenn der neue Haufen dabei ist, ein Teil eines größeren Haufens zu werden, als wir getan werden, dann machen Sie sich nicht die Mühe, das Schnur-Eigentum einzusetzen: Es muss nur getan werden, als ein Haufen seine Endgröße erreicht hat.
• Um das zu tun, schauen Sie darauf, wie viele Elemente nach dem neuen Haufen der Größe L (x) verlassen werden. Wenn es mehr gibt als L (x-1) +1, dann ist dieser neue Haufen dabei, verschmolzen zu werden.
• Erhalten Sie das Haufen-Eigentum des niedrigstwertigen Haufens nicht aufrecht. Wenn dieser Haufen einer der Endhaufen der Schnur wird, dann wird das Aufrechterhalten des Schnur-Eigentums das Haufen-Eigentum wieder herstellen. Natürlich, wann auch immer ein neuer Haufen dann geschaffen wird, ist der niedrigstwertige Haufen nicht mehr das niedrigstwertige, und das Haufen-Eigentum muss wieder hergestellt werden.

Lassen Sie die Schnur zusammenschrumpfen, indem Sie das niedrigstwertige Element entfernen

Wenn der niedrigstwertige Haufen eine Größe 1 hat (d. h., L (1) oder L (0)), dann muss nichts getan werden. Entfernen Sie einfach diesen niedrigstwertigen Haufen.

Wenn der niedrigstwertige Haufen keine Größe 1 hat, dann die Wurzel entfernt, die zwei Subhaufen als Mitglieder der Schnur ausstellend. Stellen Sie das Schnur-Eigentum zuerst auf dem linken und dann auf dem richtigen wieder her.

Optimierung

Wenn

• wir das Schnur-Eigentum wieder herstellen, brauchen wir nicht die Wurzel des Haufens nach links mit den zwei Kinderknoten der Haufen zu vergleichen, die gerade ausgestellt worden sind, weil wir wissen, dass diese kürzlich ausgestellten Haufen das Haufen-Eigentum haben. Vergleichen Sie es gerade mit der Wurzel.

Speichergebrauch

Der smoothsort Algorithmus muss im Stande sein, im Gedächtnis die Größen von allen Haufen in der Schnur zu halten. Da alle diese Werte verschieden sind, wird das gewöhnlich mit wenig Vektoren getan. Außerdem, da es am grössten Teil von O gibt (loggen n), Zahlen in der Folge, können diese Bit in O (1) Maschinenwörter verschlüsselt werden, ein transdichotomous Maschinenmodell annehmend.

Javanische Durchführung

Dieser Code verwendet lo und hallo als die Grenzen der Reihe einschließlich. Bemerken Sie, dass das nicht die übliche Tagung ist. Bemerken Sie weiter, dass diese Durchführung etwas rissig gemacht wird: Der bitmap p hält nur 32 Bit und beschränkt deshalb die maximale Zahl von Haufen in der kompletten Schnur zu 32 (das nicht Zählen des niedrigstwertigen Haufens der Größe-LP [0]), der schließlich überfließen wird, wenn Sie versuchen, eine Reihe mehr zu sortieren, als LP [32] +1 = 7049156 Elemente. Das kann durch das Verwenden eines langen-bitmap gelöst werden, der breit genug ist, um ein einzelnes Bit für jede Leonardo-Zahl zu halten, die als ein Reihe-Index in Java verwendet werden konnte, das genau ein mehr ist als der Index des größten solche Zahl (d. h. der größte, der die unterzeichnete ganze Zahl von 32 Bit einbaut, wie sich über LP geäußert hat) und deshalb der Länge der LP gleich ist, die 43 ist.

//indem wir diese Konstanten behalten, können wir das ermüdende Geschäft vermeiden

//des Nachgehens des b und c von Dijkstra. Anstatt zu behalten

//b und c, ich werde einen Index in diese Reihe behalten.

statische int End-LP [] = {1, 1, 3, 5, 9, 15, 25, 41, 67, 109,

177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,

35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457,

1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703,

48315633, 78176337, 126491971, 204668309, 331160281, 535828591,

866988873//ist die folgende Zahl> 31 Bit.

};

statisches Publikum

interne Nummer lo, interne Nummer hallo) {\

int Kopf = lo;//der Ausgleich des ersten Elements des Präfixes in die M

//Diese Variablen brauchen ein bisschen Erklären. Wenn unsere Reihe von Haufen

//ist der Länge 38, dann werden die Haufen der Größe 25+9+3+1 sein, die sind

//Leonardo Nummern 6, 4, 2, 1.

//Das in eine Binärzahl verwandelnd, bekommen wir b01010110 = 0x56. Wir vertreten

//diese Zahl als ein Paar von Zahlen durch die Recht-Verschiebung alle Nullen und

//Speicherung des mantissa und der Hochzahl als "p" und "pshift".

//Das ist handlich, weil die Hochzahl der Index in L [] das Geben des ist

//die Größe des niedrigstwertigen Haufens, und weil wir sofort wenn herausfinden können

//die niedrigstwertigen zwei Haufen sind Konsekutivzahlen von Leonardo durch die Überprüfung

//(p&3) == 3

interne Nummer p = 1;//der bitmap der aktuellen Standardverkettung>> pshift

interne Nummer pshift = 1;

während (Kopf

pshift + = 2;

} sonst {\

//das Hinzufügen eines neuen Blocks der Länge 1

wenn (LP [pshift - 1]> = hallo - Kopf) {\

//dieser Block ist seine Endgröße.

trinkle (M, p, pshift, Kopf, falsch);

} sonst {\

//dieser Block wird verschmolzen. Machen Sie es gerade vertrauensvoll.

durchrieseln Sie (M, pshift, Kopf);

}\

wenn (pshift == 1) {\

//LP [1] wird verwendet, so fügen wir Gebrauch-LP [0] hinzu

p

pshift + = Spur;

} sonst {\

p

trinkle (M, p, pshift, Kopf - 1, wahr);

}\

Kopf-;

}\

}\

privat statisch

int Kopf) {\

//wir verwenden die Verbesserungen von Floyd zum heapsort nicht, durchrieseln weil wir

//tun nicht, was heapsort - immer bewegende Knoten von der Nähe tut

//der Boden des Baums zur Wurzel.

C val = M [Kopf];

während (pshift> 1) {\

interne Nummer rt = Kopf - 1;

interne Nummer lf = Kopf - 1 - LP [pshift - 2];

wenn (val.compareTo (M [lf])> = 0 && val.compareTo (M [rt])> = 0)

Brechung;

wenn (M [lf].compareTo (M [rt])> = 0) {\

M [Kopf] = M [lf];

gehen Sie = lf;

pshift - = 1;

} sonst {\

M [Kopf] = M [rt];

gehen Sie = rt;

pshift - = 2;

}\ }\

M [Kopf] = val;

}\ privat statisch

interne Nummer pshift, int Kopf, boolean isTrusty) {\

C val = M [Kopf];

während (p! = 1) {\

int Stiefsohn = Kopf - LP [pshift];

wenn (M [Stiefsohn].compareTo (val)

interne Nummer rt = Kopf - 1;

interne Nummer lf = Kopf - 1 - LP [pshift - 2];

wenn (M [rt].compareTo (M [Stiefsohn])> = 0

|| M [lf].compareTo (M [Stiefsohn])> = 0)

Brechung;

}\

M [Kopf] = M [Stiefsohn];

gehen Sie = Stiefsohn;

int Spur = Integer.numberOfTrailingZeros (p & ~1);

p>>> = Spur;

pshift + = Spur;

isTrusty = falsch;

}\

wenn (! isTrusty) {\

M [Kopf] = val;

durchrieseln Sie (M, pshift, Kopf);

}\ }\

</Quelle>

Referenzen

• Kommentierte Abschrift von EWD796a