Timsort

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Timsort ist ein hybrider Sortieralgorithmus, der von Mergesort und Insertionsort abgeleitet ist. Er wurde entwickelt, um auf verschiedenen realen Daten schnell zu arbeiten. Er wurde 2002 von Tim Peters für die Nutzung in Python entwickelt und ist seit der Version 2.3 der Standard-Sortieralgorithmus in Python. Mittlerweile wird er auch in Java SE 7 und auf der Android-Plattform genutzt.[1][2]

Funktionsweise[Bearbeiten]

Tim Peters beschreibt den Algorithmus folgendermaßen:

„[…] ein anpassungsfähiges, stabiles Natural Mergesort, das bescheidenerweise Timsort heißt (hey, ich hab's verdient <zwinker>). Es ist leistungsfähiger als Natural Mergesort beim Sortieren von vielen Arten von teilweise sortierten Arrays (weniger als lg(N!) Vergleiche erforderlich, sogar bis hinunter zu N-1), dennoch so schnell wie das von Python vorher eingesetzte, stark optimierte hybride Samplesort beim Sortieren zufälliger Arrays.

Kurz gefasst, geht die Hauptroutine einmal von links nach rechts durch das Array, dabei identifiziert sie abwechselnd die nächste vorsortierte Teilfolge oder fügt diese „intelligent“ mit den vorher erkannten vorsortierten Teilfolgen zusammen. Der Rest dient der Beschleunigung und der hart-erkämpften Verbesserung der Speichereffizienz.“

Tim Peters: [3]

Es findet bereits sortierte Abschnitte in den Daten. Absteigend sortierte Abschnitte werden umgedreht. Dann wird geprüft, ob die Länge dieser Abschnitte die minimale Abschnittslänge für die jeweilige Array-Größe erreicht. Die minimale Abschnittslänge hängt von der Größe des Arrays ab. Für Arrays mit weniger als 64 Elementen ist die minimale Abschnittslänge das gesamte Array, sodass Timsort in dem Fall einem Insertionsort entspricht. Für größere Arrays wird als minimale Abschnittslänge eine Zahl zwischen 32 und 64 gewählt, sodass die Größe des Arrays geteilt durch die minimale Abschnittslänge gleich einer oder minimal kleiner als eine Zweierpotenz ist. Der Algorithmus nutzt einfach die sechs höchsten Bits der Array-Länge und addiert eins dazu, falls noch zumindest eines der weiteren Bits gesetzt ist. Wenn ein Abschnitt nicht die minimale Abschnittslänge erreicht, wird er mit Insertionsort vergrößert, bis er lang genug ist. Die Abschnitte werden dann mittels Mergesort zum fertig sortierten Array zusammengefügt.[3]

Komplexität und Effizienz[Bearbeiten]

Wie Mergesort ist Timsort ein stabiles, vergleichsbasiertes Sortierverfahren mit einer Best-Case-Komplexität von \Theta(n) und einer Worst- und Average-Case-Komplexität von  \mathcal{O}(n \cdot \log (n)) .[4]

Nach der Informationstheorie kann kein vergleichsbasiertes Sortierverfahren mit weniger als Ω(n log n) Vergleichen im Average-Case auskommen. Auf realen Daten braucht Timsort oft deutlich weniger als Ω(n log n) Vergleiche, weil es davon profitiert, dass Teile der Daten schon sortiert sind.[5]

Bekannte Fehler[Bearbeiten]

Im Februar 2015 stellte der Amsterdamer Informatiker Stijn de Gouw fest, dass alle Implementierungen des Timsort-Algorithmus einen Fehler enthalten.[6] Dieser Fehler hat keine praktischen Auswirkungen, da er nur auf Rechnern mit sehr viel Speicher auftreten kann, die zurzeit nicht existieren. Dennoch wurde der Fehler in Python[7] und Java[8] behoben.

Einzelnachweise[Bearbeiten]

  1. jjb: Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort. In: Java Development Kit 7 Hg repo. Abgerufen am 24 Feb 2011.
  2. Class: java.util.TimSort<T>. In: Android JDK 1.5 Documentation. Abgerufen am 24 Feb 2011.
  3. a b Tim Peters: timsort. In: Python Issue Tracker. Abgerufen am 24 Feb 2011.
  4. Tim Peters: [Python-Dev] Sorting. In: Python Developers Mailinglist. Abgerufen am 24 Feb 2011: „[Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N-1 compares is best).“
  5. Alex Martelli: Python in a Nutshell (In a Nutshell (O'Reilly)). O'Reilly Media, Inc., 2006, ISBN 0596100469.
  6. http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
  7. http://bugs.python.org/issue23515
  8. https://bugs.openjdk.java.net/browse/JDK-8072909

Weblinks[Bearbeiten]