Adaptiver Sortieralgorithmus

Diese Baustelle befindet sich fälschlicherweise im Artikelnamensraum. Bitte verschiebe die Seite oder entferne den Baustein {{Baustelle}}.

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit den Autoren auf.

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 vor kommt, 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 Agorithmus 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 $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 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 .

Ü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 noch nahe am Best-Case ist, wodurch es gerechtfertigt ist, diese Algorithmen hier aufzuführen.

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

Beispiel

Straight Insertion Sort

Straight Insertion Sort ist eine Abwandlung von Insertion Sort. 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.

Eingabe: 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))$. 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.