„Smoothsort“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[gesichtete Version]

← Zum vorherigen Versionsunterschied Zum nächsten Versionsunterschied →

Inhalt gelöscht Inhalt hinzugefügt

VisuellWikitext

Inline

Version vom 31. August 2019, 04:03 Uhr

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

Weblinks

Ein PDF von Dijkstras Veröffentlichung zum Smoothsort (englisch) (331 kB)

@@ Zeile 1: / Zeile 1: @@
 [[Datei:Smoothsort.gif|frame|rechts|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 [[Landau-Symbole|<math> \mathcal{O}(n ) </math>]] 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 (<math>\mathcal{O}(n \cdot \log n)</math>) in der Laufzeit gegenüber dem [[Heapsort|Heapsort-Algorithmus]] mitbringt.
+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 [[Landau-Symbole|<math> \mathcal{O}(n ) </math>]] 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 <math>\Theta(n \cdot \log n)</math>  keine Verbesserung gegenüber dem [[Heapsort|Heapsort-Algorithmus]] mitbringt.
 == Weblinks ==