Sortieralgorithmen

Dijkstras SmoothSort

Sortieralgorithmen haben mich schon immer fasziniert. Bis vor Kurzem wurden in Runtime-Libraries und in Produkten nur suboptimale Algorithmen eingesetzt. Mit der Einführung von JAVA und .NET hat sich das geändert. Ich erinnerte mich aber, dass es einen relativ wenig bekannten Algorithmus "SmoothSort" von Edsger W. Dijkstra gibt, der im günstigsten, weitgehend schon sortierten Fall nur O(n) Vegleiche benötigt.

Dijkstras Darstellung ist nicht leicht zu lesen und noch schwieriger zu implementieren. Ich habe eine JAVA-Implementation für Listen in einer genereischen Klasse Order implementiert, welche für meinen Geschmack einfacher verständlich ist und als Basis für Adaptionen für Arrays oder andere Programmiersprachen dienen kann.

Um Dijkstras Algorithmus mit bestehenden zu vergleichen, sind in der selben Klasse eine MergeSort, ein SwapSort, ein HeapSort und ein SmoothSort implementiert. Der MergeSort entspricht ziemlich exakt dem Algorithmus, der in der Collections-Klasse der JAVA-Runtime-Libary verwendet wird. Der SwapSort scheint eine neue "in place"-Variante des MergeSort zu sein, die in jeder Hinsicht überrascht. Dieser Algorithmus wurde offenbar kürzlich von Siegfried Sielaff neu erfunden. Er scheint allen anderen Algorithmen deutlich überlegen zu sein. Den HeapSort implementierte ich als Vorbereitung zum SmoothSort. Der SmoothSort ist demjenigen von Dijkstra ziemlich ähnlich.

Ich gehe davon aus, dass ich zum letzten Mal Sortieralgorithmen bearbeitet habe.