„Smoothsort“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[ungesichtete Version]

[gesichtete Version]

← Zum vorherigen Versionsunterschied Zum nächsten Versionsunterschied →

Inhalt gelöscht Inhalt hinzugefügt

VisuellWikitext

Inline

Version vom 24. November 2016, 12:48 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 keine Verbesserung ( ${\mathcal {O}}(n\cdot \log n)$ ) in der Laufzeit 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. Außerdem ist es kein gutes Präsentationsthema #RIPDario #Denkursstreichichehh
+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.
 == Weblinks ==