timsort/timsort.md

Timsort

Wofür braucht man Sortieralgorithmen?

• Wörterbuch
• Preisvergleich

Einführung Timsort

• Hybrid aus Insertion und Mergesort
• weniger als 64 Elemente: Insertionsort

Insertionsort

• erste Element des unsortierten Arrays in das sortierte Array kopiert
• Danach wird geschaut, ob das zweite Element größer als das letzte Element im sortierten Array ist. Dann wird es rechts davon einsortiert
• Ansonsten wird der Index vom zu überprüfenden Element halbiert und von vorne begonnen
• In der Mitte des eingegrenzten Bereiches wird überprüft, ob das Element größer oder kleiner ist, so wird der mögliche Bereich mit jedem Mal halbiert
• Nachdem die richtige Stelle gefunden wurde, wird die Zahl dort eingeschoben

Runs

• mehr als 64 Elemente
• Das unsortierte Array wird in Runs aufgeteilt
• jeder Runs hat eine Mindestgröße, den minrun, normlerweise zwischen 32 und 64
• minrun wird so ausgewählt, dass die Anzahl der Runs etwas weniger als eine 2er-Potenz
• viele Daten enthalten bereits sortierte Teile
• Aufsteigende und aufsteigende Reihe werden erkannt
• absteigende Reihen werden umgekehrt
• jeder Run wird mit Insertionsort sortiert

Merge

• jeweiles zwei Arrays werden gemerged
• Überprüfung am Anfang welches Arrays die Zahl kleiner ist
• kopieren der Zahl in das sortierte Array und lösche der Zahl im Ursprungsarray
• nach einem Durchgang nur noch die Hälfte der Arrays
• wiederholen bis alle Zahlen im einen Array sind

Galloping

• wenn 7 mal in Folge die kleinere Zahl im selben Array ist
• wird nach der Zahl des anderen Arrays, welche als nächstes einsortiert wird, im ersten Array gesucht
• alles von der aktuellen Position bis zur gefundenen Position des ersten Arrays wird in das sortierte Array kopiert

Quellen

Erklärvideo, wikipedia, exponential search, Beispiel Implementation,

Bilder

Insertionsort Visuialzion, Minrun, Merge, Pferd, Galloping, Regal, Komplexität

Code

Timsort Implementation