66 lines
2.7 KiB
Markdown
66 lines
2.7 KiB
Markdown
# 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](https://www.youtube.com/watch?v=_dlzWEJoU7I),
|
|
[wikipedia](https://en.wikipedia.org/wiki/Timsort),
|
|
[exponential search](https://en.wikipedia.org/wiki/Exponential_search),
|
|
[Beispiel Implementation](https://www.geeksforgeeks.org/timsort/),
|
|
|
|
### Bilder
|
|
|
|
[Insertionsort Visuialzion](https://media.geeksforgeeks.org/wp-content/uploads/insertionsort.png),
|
|
[Minrun](https://upload.wikimedia.org/wikipedia/commons/6/63/Selection_of_minrun_by_timsort.png),
|
|
[Merge](https://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Merge_sort_algorithm_diagram.svg/1064px-Merge_sort_algorithm_diagram.svg.png),
|
|
[Pferd](https://i.ytimg.com/vi/ZVzd_Y1Gdbg/maxresdefault.jpg),
|
|
[Galloping](https://upload.wikimedia.org/wikipedia/commons/2/2d/Galloping_mode_timsort.png),
|
|
[Regal](https://homepage.univie.ac.at/martina.gajdos/Bilder/WB-Doppels-dt.png),
|
|
[Komplexität](https://hackernoon.com/hn-images/1*1CkG3c4mZGswDShAV9eHbQ.png)
|
|
|
|
## Code
|
|
|
|
[Timsort Implementation](https://git.redstoneunion.de/MrGeorgen/timsort)
|