Adaptivität

Die Adaptivität steht in engem Zusammenhang mit der Sortiergeschwindigkeit, dennoch sei ihr ein eigener Abschnitt gewährt.

Einige Algorithmen reagieren auf ein erhöhtes Ordnungsniveau der zu sortierenden Menge (vorsortiert, komplett sortiert oder viele gleiche Elemente) dergestalt, daß ihre Geschwindigkeit spürbar zunimmt, dieses Verhalten nennt man Adaptivität (auch Ordnungsverträglichkeit). Andere, eben nichtadaptive Sortieralgorithmen sind diesbezüglich unempfindlich und sortieren unbeindruckt davon mit gleicher Geschwindigkeit bzw. gleichem Zeitaufwand (z.B. die verschiedenen Heapsorts (nicht jedoch Smoothsort) und Mergesorts (nicht jedoch Naturalmergesort)). Ggf. kann diese Adaptivität durch eine Verbesserung eines vorher nichtadaptiven, aber grundsätzlich adpativierbaren Algorithmus' erreicht werden (das ist in diesem Programm beim Bubblesort geschehen). Alle Sortieralgorithmen, die Vergleiche zwischen den Sortierelementen und anschließendem optionalem Elementetausch ((nur) wenn die Elemente die falsche Reihenfolge zueinander haben) vollziehen, sind adaptiv, weil (vor-)sortierte gegenüber völlig chaotischen Mengen weniger Vertauschungen erfordern. Aber auch die Anzahl der Vergleiche allein hängt bei manchen Sortieralgorithmen schon von der Elementeordnung ab (z.B. Insertionsort), bei anderen nicht (z.B. Bubblesort). Es gibt demnach genaugenommen eine Adaptivität hinsichtlich der Elementvergleiche und eine hinsichtlich der Elementebewegungen (Verschiebungen und / oder Vertauschungen).

Eine ganz simple und plausible Möglichkeit, den meisten (vergleichsbasierten) Sortieralgorithmen eine „Grundadaptivität“ zuzuordnen, besteht darin, die zu sortierende Menge vor dem Start des Algorithmus' auf Sortiertheit zu prüfen und den Algorithmus daraufhin nur optional zu starten, die Vorabprüfung sozusagen zum Bestandteil des Algorithmus' selbst zu machen. Das ist ggf. ohne zusätzlichen Aufwand möglich, da es Sortieralgorithmen gibt, die ohnenhin am Ende der Hauptschleife auf Sortiertheit prüfen.

Ein adaptiver Sortieralgorithmus kann zusätzlich beschleunigt werden, indem absteigende Elementefolgen bzw. Teilmengen (sog. inverse „Run“s) der zu sortierenden Startmenge vor dem eigentlichen Sortieren invertiert bzw. gewendet werden (z.B. Naturalmergesort).

Je geringer die Adaptivität eines Sortieralgorithmus' ist, desto wahrscheinlicher ist es, daß er sich als Sortiernetz(werk) realisieren läßt.