Der perfekte Sortieralgorithmus

Sortieralgorithmen sollen vor allem schnell und meistens auch stabil sein sowie möglichst wenig (zusätzlichen) Speicher benötigen, nicht zuletzt nicht gar zu komplex und damit realistisch implementierbar sein. Alle diese Ziele gleichermaßen zu erreichen bzw. zu optimieren hat sich als Zielkonflikt herausgestellt.

Bei den schnellen Sortieralgorithmen gibt es einige, die aus der Menge der unsortierten Daten eine komplett neue aufbauen, und das meistens sogar stabil. Sie duplizieren sozusagen die Sortiermenge mit veränderter, geordneter, sortierter, meistens sogar stabiler Struktur, die am Ende zurückgeschrieben, d.h., die unsortierte Startmenge damit überschrieben wird. Selbstredend benötigen diese Algorithmen viel zusätzlichen Speicher. Duchweg reichlich kompliziert sind sie obendrein. Vertreter in diesem Programm sind AVL-, B-, Binary-Search-Tree-, Fibonacci- (instabil), Patience-, Red-Black-, Skip-, Splay-, Tree- (instabil) und Trisort.

Weitere schnelle Sortieralgorithmen sind Heap- (inkl. seiner starken Abwandlung Smooth-), Merge- (inkl. Naturalmerge-) und Quicksort.

Mergesort ist neben schnell auch stabil, arbeitet aber rekursiv und benötigt dafür zusätzlichen (Stack-)Speicher. Diesen Nachteil haben das einfache iterative und das Naturalmergesort nicht. Jedoch läuft das gewöhnliche Verschmelzen aller Mergesorts parallel zu der zu sortierenden Menge im Speicher ab (Datenduplizierung) und benötigt mithin erheblichen zusätzlichen Speicher. Dieser Nachteil wurde mit den In-Situ-Verschmelzungsalgorithmen (etliche in diesem Programm enthalten) mehr oder weniger beseitigt, doch wirken diese sich negativ auf die Geschwindigkeit aus, von der Komplexität dieser Sortier- und vor allem Verschmelzungsalgorithmen ganz zu schweigen. Auch die Stabilität geht bei manchen verloren.

Quicksort ist zwar für gewöhnlich, d.h., auf unsortierte Mengen angewandt, sehr schnell, dafür aber instabil und ebenfalls rekursiv. Doch es gab erfolgreiche Versuche, beide Nachteile aufzuheben. Die aufgestöberten bzw. gefundenen, mehr oder weniger komplizierten Vertreter sind in diesem Programm implementiert. Leider wurden beide mühsam erkämpften Vorteile bisher nicht in einem Algorithmus kombiniert bzw. vereint.

Bliebe das Heapsort, das sowohl schnell als auch speichersparend ist. Davon ist im Programm eine stabile Version enthalten, bei der jedoch die Geschwindigkeit einbricht. Gelänge es, Stabilität zu erreichen und mit Geschwindigkeit zu vereinen, wäre auch hier ein (evtl. nahezu) perfekter Sortieralgorithmus gefunden, sofern er nicht überbordernd kompliziert ist. Seine Abwandlung Smoothsort hingegen ist bereits wieder sehr kompliziert und damit nur schwierig zu implementieren sowie instabil und wohl auch nicht stabilisierbar.

Es wurde(n) demnach faktisch nur die Hälfte, bestenfalls zwei Drittel (bei nichtgeforderter Stabilität) aller Anforderungen in den besten Sortieralgorithmen vereint. Die jahrzehntelange, bisher vergebliche Suche macht es wahrscheinlich, daß es, wenn überhaupt, keine einfache Lösung gibt, sodaß, wenn eine gefunden wird, diese zwar schnell, stabil und speichersparend, nicht jedoch trivial sein wird. Es gibt also für die (theoretische) Informatik auch auf dem Gebiet der Sortieralgorithmen noch sehr viel zu tun.

Kontaktformular