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, besitzen zumindest eine „gewisse Adaptivität“, weil (vor-)sortierte gegenüber völlig chaotischen Mengen weniger Vertauschungen erfordern.

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).

Kontaktformular