„Smoothsort“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[gesichtete Version]

← Zum vorherigen Versionsunterschied Zum nächsten Versionsunterschied →

Inhalt gelöscht Inhalt hinzugefügt

VisuellWikitext

Inline

Version vom 20. Mai 2023, 20:20 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

@@ Zeile 1: / Zeile 1: @@
 {{Lückenhaft|Bei vielen anderen Algorithmen erfolgt eine Beschreibung in [[Pseudocode]]. Warum hier nicht?}}
-[[Datei:Smoothsort.gif|frame|rechts|Der Smoothsort-Algorithmus beim Sortieren eines Arrays aus permutierten Werten.]]
+[[Datei:Smoothsort.gif|gerahmt|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'' mit einer Laufzeit von <math>\Theta(n \cdot \log n)</math>  keine Verbesserung 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]]-Algorithmus mitbringt.
 == Weblinks ==