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 ${\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.