Smoothsort

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Der Smoothsort-Algorithmus beim Sortieren eines Arrays aus permutierten Werten.

Das Smoothsort-Sortierverfahren ist eine Variation von Heapsort, welche von Edsger W. Dijkstra 1981 entwickelt wurde. Der Vorteil liegt darin, dass es im Best-Case mit einem Aufwand von  \mathcal{O}(n ) bei vorsortierten Folgen auskommt. Auf Grund der Kompliziertheit wird es aber selten benutzt. Dies liegt daran, dass es im Worst-Case und Average-Case keine Verbesserung in der Laufzeit gegenüber dem Heapsort-Algorithmus mitbringt.

Weblinks[Bearbeiten]