Smoothsort

Eine gesichtete Version dieser Seite, die am 8. April 2021 freigegeben wurde, basiert auf dieser Version.

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 mit einer Laufzeit von $\Theta (n\cdot \log n)$ keine Verbesserung gegenüber dem Heapsort-Algorithmus mitbringt.

Weblinks