Smoothsort

Smoothsort
Der Smoothsort-Algorithmus beim Sortieren eines Arrays aus permutierten Werten.

Das Smoothsort-Sortierverfahren ist eine Variation von Heapsort, welche von Edsger Wybe 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.

Links


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Smoothsort — est un algorithme de tri par comparaison inventé en 1981 par Edsger Dijkstra. C est un tri de complexité en O(n.log n), tout comme le tri par tas dont il est inspiré, et le tri rapide dans la plupart des cas. Mais si les données sont déjà… …   Wikipédia en Français

  • Heapsort — Infobox Algorithm class=Sorting algorithm A run of the heapsort algorithm sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property. Before the actual sorting… …   Wikipedia

  • Algorithme De Tri — Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d organiser une collection d objets selon un ordre déterminé. Les objets à trier font donc partie d un ensemble muni d une relation d ordre (de manière… …   Wikipédia en Français

  • Algorithme de tri — Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d organiser une collection d objets selon un ordre déterminé. Les objets à trier font donc partie d un ensemble muni d une relation d ordre (de manière… …   Wikipédia en Français

  • Méthode de tri — Algorithme de tri Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d organiser une collection d objets selon un ordre déterminé. Les objets à trier font donc partie d un ensemble muni d une relation d ordre… …   Wikipédia en Français

  • Tri stable — Algorithme de tri Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d organiser une collection d objets selon un ordre déterminé. Les objets à trier font donc partie d un ensemble muni d une relation d ordre… …   Wikipédia en Français

  • Haldensortierung — Der Heapsort Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen… …   Deutsch Wikipedia

  • Heap-Sort — Der Heapsort Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen… …   Deutsch Wikipedia

  • Heap Sort — Der Heapsort Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen… …   Deutsch Wikipedia

  • Qsort — Tri rapide Le tri rapide (en anglais quicksort) est une méthode de tri inventée par C.A.R. Hoare en 1961 et fondée sur la méthode de conception diviser pour régner. Il peut être implémenté sur un tableau (tri sur place) ou sur des listes ;… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”