Adaptiver Sortieralgorithmus
Adaptive Sortieralgorithmen sind Sortieralgorithmen, deren Kontrollfluss von den Eingabedaten abhängt. Insbesondere sind adaptive Sortieralgorithmen von Interesse, die auf Eingaben, die bereits über eine gewisse Ordnung verfügen, geringere Laufzeiten erzielen, als auf Eingaben ohne Struktur. Viele der bekannten adaptiven Sortieralgorithmen sind durch die Abwandlung bereits bekannter Algorithmen entstanden.
Da es in der Praxis oft vorkommt, dass Eingaben bereits beinahe sortiert sind, ist man an Algorithmen interessiert, die in diesen Fällen besonders schnell arbeiten. Das Ziel dabei ist es, die untere Schranke für den Average Case bei vergleichsbasierten Sortieralgorithmen zu unterbieten.
Bei der Laufzeitanalyse der adaptiven Verfahren wird neben der Eingabegröße auch ein Maß für die bereits vorhandene Ordnung in der Eingabe einbezogen – im Gegensatz zu klassischen vergleichsbasierten Sortierverfahren, bei denen nur zwischen Best Case, Average Case und Worst Case unterschieden wird, das Verhalten der Algorithmen zwischen diesen Fällen aber nicht weiter untersucht wird.
Maße der Ordnung
[Bearbeiten | Quelltext bearbeiten]Damit die bereits vorhandene Ordnung in der Eingabe in die Analyse des Algorithmus einfließen kann, muss diese Ordnung gemessen werden. Dafür haben sich mehrere verschiedene Maße etabliert.
Ein häufig verwendetes Maß[1] ist die Anzahl der Fehlstände, also die Anzahl der Paare in falscher Ordnung, in der Eingabe :
- .
Weitere oft genutzte Maße[1] sind:
- die Anzahl von Serien aufeinanderfolgender, ansteigender Elemente, sogenannter „runs“:
- die Anzahl von Elementen, die mindestens entfernt werden müssen, um eine sortierte Folge zu erhalten:
- die minimale Anzahl von Vertauschungen je zweier Elemente, um die Eingabe zu sortieren:
Beispiele
[Bearbeiten | Quelltext bearbeiten]Eingabe | ||||
---|---|---|---|---|
0 | 1 | 0 | 0 | |
4 | 2 | 1 | 4 | |
6 | 4 | 3 | 2 | |
10 | 5 | 4 | 2 |
Verschiedene Maße führen nicht nur zu verschiedenen Werten, sondern auch zu unterschiedlichen Einschätzungen, welche Eingaben geordneter sind als andere.
Weitere Maße sind zum Beispiel zu finden in [2].
Übersicht
[Bearbeiten | Quelltext bearbeiten]Nicht bei allen der hier aufgeführten Algorithmen ist die Laufzeit als Funktion des Ordnungsmaßes angegeben. Allerdings hat man die Hoffnung, dass in Fällen von großer Ordnung in der Eingabe die Laufzeit dieser Algorithmen noch nahe am Best-Case ist.
Sortierverfahren | Laufzeit |
---|---|
A-Sort[3] | (optimal)[4][5] |
Adaptive Heap Sort | [6] |
AVL Sort | [7] |
Natural Mergesort | [8] |
Patience Sorting | Best-Case: , bei sortierter Eingabe. Average-Case [9] |
Randomisierter Quicksort | [10] |
Shellsort | Best-Case: , bei sortierter Eingabe. Average-Case nicht in .[11] |
Smoothsort | für sortierte Eingaben. Erreicht nicht.[12] Worst-Case: |
Splaysort | In Experimenten ab einer bestimmten Ordnung in der Eingabe schneller als Randomisierter Quicksort und AVL Sort.[13] |
Straight Insertionsort | [4] |
Timsort | .[14] Worst-Case: [15] |
A-Sort
[Bearbeiten | Quelltext bearbeiten]Verwendet AVL-Bäume, in denen die Elemente abgelegt, und in sortierter Reihenfolge entnommen werden.[16]
Adaptive Heap Sort
[Bearbeiten | Quelltext bearbeiten]Verwendet einen Kartesischen Baum, in den die Elemente eingefügt, und dann in sortierter Reihenfolge wieder entfernt werden.[6]
AVL Sort
[Bearbeiten | Quelltext bearbeiten]Natural Mergesort
[Bearbeiten | Quelltext bearbeiten]Natural Mergesort[8] verwendet als Ausgangspunkt für die merge-Operationen nicht einelementige Teilfolgen, sondern die in der Eingabe bereits vorhandenen Runs (siehe oben). Falls das größte Element der einen Teilfolge kleiner ist als das kleinste der zweiten Teilfolge, so kann die merge-Operation durch eine entsprechende Konkatenation der beiden Teilfolgen ersetzt werden.
Patience Sorting
[Bearbeiten | Quelltext bearbeiten]Patience Sorting[9] verläuft in zwei Phasen. In der ersten Phase werden Runs (siehe oben) erzeugt: jedes Element wird entweder dem Ende eines bereits angelegten Runs angefügt, oder, falls es keinen Run gibt, bei dem das möglich ist, bildet einen neuen Run. In der zweiten Phase wird ein k-Wege-Mischen auf die Runs angewendet, um eine sortierte Folge zu erhalten.
Beispiel:
Schritt | Eingabe | Runs |
---|---|---|
0 | ||
1 | ||
2 | ||
3 | ||
4 | ||
5 | ||
6 | ||
7 | ||
8 | ||
9 | ||
10 |
Randomisierter Quicksort
[Bearbeiten | Quelltext bearbeiten]Im randomisierten Quicksort Algorithmus wird das Pivot-Element zufällig gleichverteilt gewählt.
Shellsort
[Bearbeiten | Quelltext bearbeiten]Shellsort[11] teilt die Eingabe wiederholt in disjunkte Teilfolgen auf, deren Elemente in der Eingabe einen regelmäßigen Abstand haben, und sortiert diese Teilfolgen. Bei jeder Wiederholung wird der Abstand zwischen den Elementen verringert, die Teilfolgen werden damit länger, bis im letzten Schritt mit Abstand 1 die gesamten Daten sortiert werden. Basiert auf Insertionsort.
Smoothsort
[Bearbeiten | Quelltext bearbeiten]Benutzt Binärbäume[12].
Splaysort
[Bearbeiten | Quelltext bearbeiten]Benutzt Splay-Bäume[13].
Straight Insertion Sort
[Bearbeiten | Quelltext bearbeiten]Straight Insertion Sort ist eine Abwandlung von Insertionsort, siehe unten.
Timsort
[Bearbeiten | Quelltext bearbeiten]Timsort[15] basiert auf Natural Mergesort und Insertionsort.
Weitere Algorithmen mit adaptiven Eigenschaften
[Bearbeiten | Quelltext bearbeiten]Bubblesort, Combsort, Insertionsort.
Beispiel
[Bearbeiten | Quelltext bearbeiten]Straight Insertion Sort
[Bearbeiten | Quelltext bearbeiten]Straight Insertion Sort ist eine Abwandlung von Insertionsort. Der Unterschied zwischen Insertion Sort und Straight Insertion Sort ist, dass bei Insertion Sort die Reihenfolge, in der das bereits Sortierte Array durchlaufen wird, beliebig gewählt werden kann, während bei Straight Insertion Sort vom größten Index zum kleinsten gesucht werden muss. Im Fall einer fast sortierten Eingabe wird so die while-Schleife selten durchlaufen.
Straight Insertion Sort (Array X der Länge n)
for j:= 2 to n do
t := X[j]
i := j
while i > 1 & X[i - 1] > t do
X[i] := X[i - 1]
i := i - 1
end
X[i] := t
end
Die Laufzeit von Straight Insertion Sort ist in [4]. Damit hat Straight Insertion Sort auf einer bereits sortierten Eingabe die minimale Laufzeit ; um eine Liste auf Sortiertheit zu prüfen, muss jedes Element mindestens einmal betrachtet werden.
Ausblick: AdaSort
[Bearbeiten | Quelltext bearbeiten]Keiner der bekannten adaptiven Sortieralgorithmen ist in allen Fällen schneller als alle anderen. Die Laufzeit der Algorithmen hängt aufgrund ihrer Adaptivität stark von der Eingabe ab, und so ist in manchen Fällen der eine Algorithmus schneller, in anderen der andere. Welcher Algorithmus der schnellste für eine Eingabe ist, ist erst nach der Ausführung bekannt.
Es ist aber möglich die Laufzeiten vorab zu schätzen, und den Algorithmus auszuwählen mit der geringsten geschätzten Laufzeit, in der Hoffnung, dass dieser auch der tatsächlich schnellste Algorithmus für die Eingabe ist. Auf diese Weise kann aus den bekannten Algorithmen ein Algorithmus konstruiert werden, der für alle Eingaben, die zu einer guten Schätzung der Laufzeiten führen, so schnell sortiert, wie der jeweils schnellste Algorithmus, allerdings mit dem Zusatzaufwand für die Laufzeitschätzungen. Diese Schätzung kann mit Machine-Learning-Verfahren durchgeführt werden.
In [17] wurde das Machine-Learning-Verfahren so trainiert, dass es in Abhängigkeit von zwei Parametern, RUNS und n, einen Sortieralgorithmus auswählt. Dabei ist
- .
Nach erfolgtem Lernen der Entscheidungsgrenzen kann auf die Ausführung des Machine-Learning-Verfahrens für die Schätzung verzichtet werden, es genügt ein Entscheidungsbaum. Dieser komplexe Baum wurde noch weiter reduziert. Das Ergebnis von S. Majumdar, I. Jain und K. Kukreja sieht wie folgt aus:
AdaSort(Array X der Länge n)
if n <= 100
runs := computeRUNS(X)
if runs > 0.68799
ShellSort(X)
else if n <= 50 & runs > 0.44
parallelMergeSort(X, p)
else if n <= 50 & runs > 0.25388
MergeSort(X)
else
InsertionSort(X)
end
else if n <= 1000
QuickSort(X)
else if n <= 500000
ParallelMergeSort(X, p)
else
ParallelQuickSort(X, p)
end
Abschließende Experimente zeigen, dass AdaSort zuverlässig den schnellsten Algorithmus auswählt, und im Durchschnitt nur wenige Mikrosekunden langsamer ist als der jeweils schnellste Sortieralgorithmus. Diese Experimente waren allerdings an die Entscheidungsgrenzen für n im Algorithmus, also angepasst, und auf Eingaben fast ohne Ordnung mit eingeschränkt. Da das Machine-Learning-Verfahren ebenfalls nur für diese n Entscheidungsgrenzen gelernt hat, ist damit nicht klar, wie gut AdaSort im Vergleich zu anderen Algorithmen für beispielsweise ist, also Runs mit durchschnittlicher Länge von . Es ist zu vermuten, dass für allgemeine und größere Ordnung in den Eingaben andere Entscheidungsgrenzen für andere Algorithmen gefunden werden können, mit denen AdaSort in diesen Fällen auch eine bessere durchschnittliche Laufzeit erzielt.
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ a b O. Petersson, A. Moffat: A framework for adaptive sorting. 1992, S. 155+156.
- ↑ V. Estivill-Castro, D. Wood: A Survey of Adaptive Sorting Algorithms. 1992, I.2.
- ↑ K. Mehlhorn: Sorting Presorted Files. 1978, S. 11.
- ↑ a b c O. Petersson, A. Moffat: A framework for adaptive sorting. 1992, S. 165.
- ↑ G. Stolting, Chapman & Hall/CRC Computer and Information Science Series.Handbook of Data Structures and Applications, 2005, S. 11–8.
- ↑ a b S. Edelkamp, A. Elmasry, J. Katajainen.Two Constant-Factor-Optimal Realizations of Adaptive Heapsort, 2011, S. 3.
- ↑ a b A. Elmasry. Adaptive sorting with AVL trees., 2004, S. 309.
- ↑ a b Hans Werner Lang: Natural Mergesort. In: Hochschule Flensburg. 2001, abgerufen am 20. Juli 2019.
- ↑ a b Badrish Chandramouli, Jonathan Goldstein: Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. 2014, abgerufen am 30. Juli 2019 (englisch).
- ↑ G. Brodal, R. Fagerberg and G. Moruz. On the adaptiveness of quicksort., 2005, S. 3.
- ↑ a b C. Plaxton, B. Poonen, T. Suel, Improved Lower Bounds for Shellsort. 1992, S. 9.
- ↑ a b Smoothsort's behavior on presorted sequences. Abgerufen am 30. Juli 2019.
- ↑ a b A. Elmasry, A. Hammad. An Empirical Study for Inversions-Sensitive Sorting Algorithms., 2005, S. 597.
- ↑ N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. On the Worst-Case Complexity of TimSort., 2012, S. 4:8.
- ↑ a b N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. On the Worst-Case Complexity of TimSort., 2012, S. 4:4.
- ↑ K. Mehlhorn: Sorting Presorted Files. 1978, S. 14.
- ↑ S. Majumdar, I. Jain, K. Kukreja AdaSort: Adaptive Sorting using Machine Learning. 2016.