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 ${\displaystyle 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ß ist die Anzahl der Fehlstände, also die Anzahl der Paare in falscher Ordnung, in der Eingabe ${\displaystyle X=(x_{1},\dots ,x_{n})}$:

${\displaystyle \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 sind:

• die Anzahl von Serien aufeinanderfolgender, ansteigender Elemente, sogenannter „runs“:

${\displaystyle \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:

${\displaystyle \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: ${\displaystyle \operatorname {Exc} (X)}$

Beispiele

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

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

Patience Sorting

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

Beispiel

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

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 wurde das Machine-Learning-Verfahren so trainiert, dass es in Abhängigkeit von zwei Parametern, RUNS und n, einen Sortieralgorithmus auswählt. Dabei ist

${\displaystyle \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 ${\displaystyle n\in \{50,100,1000,10000,100000,500000,1000000\}}$ angepasst, und auf Eingaben fast ohne Ordnung mit ${\displaystyle \operatorname {RUNS} (X)\approx 0{,}8}$ 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 ${\displaystyle n=357211,{\text{RUNS}}=0{,}001}$ ist, also ${\displaystyle \approx 357}$ Runs mit durchschnittlicher Länge von ${\displaystyle \approx 1000}$. Es ist zu vermuten, dass für allgemeine ${\displaystyle 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

1. 1 2 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.
4. 1 2 3 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.
6. 1 2 S. Edelkamp, A. Elmasry, J. Katajainen.Two Constant-Factor-Optimal Realizations of Adaptive Heapsort, 2011, S. 3.
7. 1 2 A. Elmasry. Adaptive sorting with AVL trees., 2004, S. 309.
8. 1 2 Hans Werner Lang: Natural Mergesort. In: Hochschule Flensburg. 2001, abgerufen am 20. Juli 2019. 
9. 1 2 Badrish Chandramouli, Jonathan Goldstein: Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. 2014, abgerufen am 30. Juli 2019 (englisch). 
10. ↑ G. Brodal, R. Fagerberg and G. Moruz. On the adaptiveness of quicksort., 2005, S. 3.
11. 1 2 C. Plaxton, B. Poonen, T. Suel, Improved Lower Bounds for Shellsort. 1992, S. 9.
12. 1 2 Smoothsort's behavior on presorted sequences. Abgerufen am 30. Juli 2019. 
13. 1 2 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.
15. 1 2 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.