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 $O(n\log n)$ 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

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 $X=(x_{1},...,x_{n})$ :

\operatorname {Inv} (X)=|\left\{(i,j)\mid 1\leq i<j\leq n~{\text{und}}~x_{i}>x_{j}\right\}|

.

Weitere oft genutzte Maße[1] sind:

die Anzahl von Serien aufeinanderfolgender, ansteigender Elemente, sogenannter "runs":

\operatorname {Runs} (X)=|\{\,i\,\mid 1\leq i<n~{\text{und}}~x_{i}>x_{(}i+1)\}|+1

die Anzahl von Elementen, die mindestens entfernt werden müssen, um eine sortierte Folge zu erhalten:

\operatorname {Rem} (X)=n-\max\{\,k\,\mid X~{\text{hat eine sortierte Teilfolge der Länge}}~k\}

die minimale Anzahl von Vertauschungen je zweier Elemente, um die Eingabe zu sortieren: $\operatorname {Exc} (X)$

Beispiele

Eingabe $X$	$\operatorname {Inv} (X)$	$\operatorname {Runs} (X)$	$\operatorname {Rem} (X)$	$\operatorname {Exc} (X)$
$(1,2,3,4,5)$	0	1	0	0
$(2,3,4,5,1)$	4	2	1	4
$(4,3,2,1,5)$	6	4	3	2
$(5,4,3,2,1)$	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

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]	$O\left(n\log \left({\frac {\operatorname {Inv} (X)}{n}}\right)+n\right)$ (optimal)[4][5]
Adaptive Heap Sort	$O\left(n\log \left({\frac {\operatorname {Inv} (X)}{n}}\right)+n\right)$ [6]
AVL Sort	$O\left(n\log \left({\frac {\operatorname {Inv} (X)}{n}}\right)+n\right)$ [7]
Natural Mergesort	$\Theta (n\log(\operatorname {Runs} (X)))$ [8]
Patience Sorting	Best-Case: $O(n)$ , bei sortierter Eingabe. Average-Case $O(n\log n)$ [9]
Randomisierter Quicksort	$O\left(n\log \left({\frac {\operatorname {Inv} (X)}{n}}\right)+n\right)$ [10]
Shellsort	Best-Case: $O(n\log n)$ , bei sortierter Eingabe. Average-Case nicht in $O(n\log n)$ .[11]
Smoothsort	$O(n)$ für sortierte Eingaben. Erreicht $O\left(n\log \left({\frac {\operatorname {Inv} (X)}{n}}\right)+n\right)$ nicht.[12] Worst-Case: $O(n\log n)$
Splaysort	In Experimenten ab einer bestimmten Ordnung in der Eingabe schneller als Randomisierter Quicksort und AVL Sort.[13]
Straight Insertionsort	$\Theta (n+\operatorname {Inv} (X))$ [4]
Timsort	$O(n+n\log \operatorname {Runs} (X))$ .[14] Worst-Case: $O(n\log n)$ [15]

A-Sort

Verwendet AVL-Bäume, in denen die Elemente abgelegt, und in sortierter Reihenfolge entnommen werden.[16]

Adaptive Heap Sort

Verwendet einen Kartesischen Baum, in den die Elemente eingefügt, und dann in sortierter Reihenfolge wieder entfernt werden.[6]

AVL Sort

Verwendet AVL-Bäume[7].

Natural Mergesort

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

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 $X$	Runs
0	$(3,5,4,2,1,7,6,8,9,10)$	$\emptyset$
1	$(5,4,2,1,7,6,8,9,10)$	$(3)$
2	$(4,2,1,7,6,8,9,10)$	$(3,5)$
3	$(2,1,7,6,8,9,10)$	$(3,5),(4)$
4	$(1,7,6,8,9,10)$	$(3,5),(4),(2)$
5	$(7,6,8,9,10)$	$(3,5),(4),(2),(1)$
6	$(6,8,9,10)$	$(3,5,7),(4),(2),(1)$
7	$(8,9,10)$	$(3,5,7),(4,6),(2),(1)$
8	$(9,10)$	$(3,5,7,8),(4,6),(2),(1)$
9	$(10)$	$(3,5,7,8,9),(4,6),(2),(1)$
10	$\emptyset$	$(3,5,7,8,9,10),(4,6),(2),(1)$

Randomisierter Quicksort

Im randomisierten Quicksort Algorithmus wird das Pivot-Element zufällig gleichverteilt gewählt.

Shellsort

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

Benutzt Binärbäume[12].

Splaysort

Benutzt Splay-Bäume[13].

Straight Insertion Sort

Straight Insertion Sort ist eine Abwandlung von Insertionsort, siehe unten.

Timsort

Timsort[15] basiert auf Natural Mergesort und Insertionsort.

Weitere Algorithmen mit adaptiven Eigenschaften

Bubblesort, Combsort, Insertionsort.

Beispiel

Straight Insertion Sort

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 $\Theta (n+\operatorname {Inv} (X))$ [4]. Damit hat Straight Insertion Sort auf einer bereits sortierten Eingabe die minimale Laufzeit $\Theta (n)$ ; um eine Liste auf Sortiertheit zu prüfen, muss jedes Element mindestens einmal betrachtet werden.

Ausblick: AdaSort

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

\operatorname {RUNS} (X)={\frac {\operatorname {Runs} (X)}{|X|}}

.

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 $n\in \{50,100,1000,10000,100000,500000,1000000\}$ angepasst, und auf Eingaben fast ohne Ordnung mit $\operatorname {RUNS} (X)\approx 0.8$ eingeschränkt. Da das Machine-Learning-Verfahren ebenfalls nur für diese n Entscheidungsgrenzen gelernt hat, ist damit ist nicht klar, wie gut AdaSort im Vergleich zu anderen Algorithmen für beispielsweise $n=357211,RUNS=0.001$ ist, also $\approx 357$ Runs mit durchschnittlicher Länge von $\approx 1000$ . Es ist zu vermuten, dass für allgemeine $n$ 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

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.
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.
S. Edelkamp, A. Elmasry, J. Katajainen.Two Constant-Factor-Optimal Realizations of Adaptive Heapsort, 2011, S. 3.
A. Elmasry. Adaptive sorting with AVL trees., 2004, S. 309.
Natural Mergesort. In: FH Flensburg. Abgerufen am 20. Juli 2019.
Patience is a Virtue: Revisiting Merge and Sorton Modern Processors. Abgerufen am 30. Juli 2019.
G. Brodal, R. Fagerberg and G. Moruz. On the adaptiveness of quicksort., 2005, S. 3.
C. Plaxton, B. Poonen, T. Suel, Improved Lower Bounds for Shellsort. 1992, S. 9.
Smoothsort's behavior on presorted sequences. Abgerufen am 30. Juli 2019.
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.
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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[Petersson155-1] O. Petersson, A. Moffat: A framework for adaptive sorting. 1992, S. 155+156.

[2] V. Estivill-Castro, D. Wood: A Survey of Adaptive Sorting Algorithms. 1992, I.2.

[3] K. Mehlhorn: Sorting Presorted Files. 1978, S. 11.

[Peterson165-4] O. Petersson, A. Moffat: A framework for adaptive sorting. 1992, S. 165.

[5] G. Stolting, Chapman & Hall/CRC Computer and Information Science Series.Handbook of Data Structures and Applications, 2005, S. 11–8.

[ConstantFactor-6] S. Edelkamp, A. Elmasry, J. Katajainen.Two Constant-Factor-Optimal Realizations of Adaptive Heapsort, 2011, S. 3.

[AVL-7] A. Elmasry. Adaptive sorting with AVL trees., 2004, S. 309.

[Flensburg-8] Natural Mergesort. In: FH Flensburg. Abgerufen am 20. Juli 2019.

[Patience-9] Patience is a Virtue: Revisiting Merge and Sorton Modern Processors. Abgerufen am 30. Juli 2019.

[10] G. Brodal, R. Fagerberg and G. Moruz. On the adaptiveness of quicksort., 2005, S. 3.

[shellsort-11] C. Plaxton, B. Poonen, T. Suel, Improved Lower Bounds for Shellsort. 1992, S. 9.

[hertel-12] Smoothsort's behavior on presorted sequences. Abgerufen am 30. Juli 2019.

[inversionsensitive-13] A. Elmasry, A. Hammad. An Empirical Study for Inversions-Sensitive Sorting Algorithms., 2005, S. 597.

[14] N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. On the Worst-Case Complexity of TimSort., 2012, S. 4:8.

[Tim-15] N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. On the Worst-Case Complexity of TimSort., 2012, S. 4:4.

[16] K. Mehlhorn: Sorting Presorted Files. 1978, S. 14.

[17] S. Majumdar, I. Jain, K. Kukreja AdaSort: Adaptive Sorting using Machine Learning. 2016.