Algorytmy i struktury danych · Senior · Pytanie 31 z 75
Dlaczego Timsort tak dobrze radzi sobie z prawdziwymi danymi?
- 1Przełącza się na sortowanie przez zliczanie dla liczb
- ✓Poprawna odpowiedź: Wykrywa istniejące posortowane serie i je scala
- 3Sortuje równolegle na wszystkich rdzeniach procesora
Wyjaśnienie
Prawdziwe dane są często częściowo uporządkowane: dopisywane logi, prawie posortowane listy. Timsort znajduje serie rosnące (lub odwrócone malejące), wydłuża krótkie przez wstawianie i scala je „galopem”, zbliżając się do O(n) na prawie posortowanych danych.