Sortierprinzipien

Beim Sortieren gibt es zwei grundlegende Vor- oder Herangehensweisen, die ich so explizit noch nirgendwo beschrieben fand:

• Entweder wird die komplette Startmenge sortiert, das allerdings, weil ein Durchgang nicht ausreicht, um das Ordnungsniveau bis zur völligen Sortiertheit anzuheben, sooft wie nötig wiederholt wird. Die Menge wird also in jedem Durchlauf genaugenommen nur teilsortiert („Gesamtmenge teilsortiert“).
• Oder es wird nur ein Teil der Startmenge sortiert, dieser aber von Anfang an in nur einem Durchgang vollständig, und dieser Teil wird durch Hinzunahme immer weiter Elemente aus der unsortierten Menge immer mehr vergrößert, bis es keine unsortierte Elementemenge mehr gibt („Teilmenge komplettsortiert“). Das entspricht dem sog. Teile-und-herrsche-Prinzipg („divide et impera“).

Viele, wenn nicht sogar die meisten Sortieralgorithmen lassen sich mehr oder weniger eindeutig einem dieser beiden Prinzipien zuordnen. Es gibt aber auch Sortieralgorithmen, die sich beider Heransgehensweisen bedienen, so Quicksort und - was nicht offensichtlich ist - Stupidsort. Weiterhin ist es möglich, daß das zweite Prinzip im ersteren enthalten ist: So bauen die iterativen Mergesorts zunächst über die gesamte Sortiermenge zunächst kleine, komplett sortierte Bereiche auf, die allmählich wachsen und anzahlig geringer werden, bis schließlich die gesamte Menge sortiert ist.

Es gibt bei beiden Prinzipien auch weitere Unterschiede. So ist es beim ersten möglich, daß mehrere sortierte Teilmengen gebildet werden, die immer mehr Elemente enthalten und deshalb anteilig schrumpfen (z.B. Merge - und Shearsort). Oder das Ordnungsniveau wird ohne diese Eigenschaft insgesamt erhöht (Shellsort). Besonders rätselhaft ist letzteres bei Radixsort LSD, wo in den ersten Durchgängen überhaupt keine Steigerung des Ordnugnsniveaus wahrnehmbar ist, diese natürlich aber dennoch stattfindet.

Beim zweiten Prinzip kann die sortierte Teilmenge sich unverändert in der sortierten Endmenge wiederfinden (z.B. Bubble,- Heap- und Selectionsort) oder noch weitere Elemente eingefügt bekommen (z.B. Insertion- und Mergesort).

Deutlich unterscheidbar sind beide Prinzipien auch in diesem Programm in der sog. Combobox „Vorsortierung/-mischung“ rechts oben im Bedienformular. Je nach Sortierprinzip kann bzw. muß das Maß der Vorsortierung unterschiedlich eingestellt werden. Nur beim Merge- und beim Quicksort ist das nicht ganz korrekt, denn beide sind eigentlich rekursiv und wurden in eine iterative Ersatzstruktur transformiert.

Möglicherweise hängt die Klassifikation in stationäre und nichtstationäre Sortieralgorithmen damit zusammen. Auch erinnert mich dieses Bild an diese meine Klassifikation.

Während die erste Teilmenge überwiegend von iterativen Algorithmen realisiert wird, werden für die zweite eher rekursive Algorithmen verwendet.