Algorithmen - Sortieralgorithmus Timsort
Timsort, im Gegenteil zum „Bubble“ und „Insertion“ ist relativ neu – es wurde 2002 von Tim Peters erfunden und auch nach ihm benannt. Seitdem ist es zum Standard-Sortieralgorithmus von Python, OpenJDK 7 und Android JDK 1.5 geworden. Und damit man versteht, wieso, muss man einfach auf diese Tabelle aus Wikipedia schauen
Unter der großen Auswahl gibt es in der Tabelle nur 7 adäquate Algorithmen (mit der Schwierigkeit O(n log(n)) im Durchschnitt und im schlimmsten Fall), von denen nur 2 Stabilität und die Schwierigkeit O(n) im besten Fall vorweisen können. Einer von diesen beiden ist die „Sortierung mit einem Binärbaum“ und der andere ist Timsort.
Der Algorithmus ist auf der Idee aufgebaut, dass in der reellen Welt die zu sortierende Menge oft angeordnete (egal, in welcher Reihenfolge) Untermengen enthält. Das ist in Wirklichkeit oft so. Bei solchen Daten übertrifft Timsort alle anderen Algorithmen um Längen.
http://gumzo.de/post/143/
Unter der großen Auswahl gibt es in der Tabelle nur 7 adäquate Algorithmen (mit der Schwierigkeit O(n log(n)) im Durchschnitt und im schlimmsten Fall), von denen nur 2 Stabilität und die Schwierigkeit O(n) im besten Fall vorweisen können. Einer von diesen beiden ist die „Sortierung mit einem Binärbaum“ und der andere ist Timsort.
Der Algorithmus ist auf der Idee aufgebaut, dass in der reellen Welt die zu sortierende Menge oft angeordnete (egal, in welcher Reihenfolge) Untermengen enthält. Das ist in Wirklichkeit oft so. Bei solchen Daten übertrifft Timsort alle anderen Algorithmen um Längen.
http://gumzo.de/post/143/
Please also mark the comments that contributed to the solution of the article
Content-Key: 212743
Url: https://administrator.de/contentid/212743
Printed on: April 23, 2024 at 22:04 o'clock