Sigurno ste se pitali koji algoritam sortiranja se izvršava kada se pokrene ugrađena sort funkcija? Odgovor nije jednstven za sve implementacije ali jedan od najzastupljenijih je definitivno timsort.
Timsort je hibridni, stabilni algoritam, izveden od merge sort i insertion sort algoritama. Razvio ga je Tim Peters 2002. godine za potrebe programskog jezika Python. Danas je njegova primena proširena na Javu, Android, GNU Octave, JavaScript V8, Swift i Rust. Veoma je efikasan nad realnim podacima.
Osnovna ideja timsort algoritma je da iskoristi redosled među elementima koji već postoji kako bi minimizirao broj poređenja i zamena.
Ukoliko je broj elemenata kolekcije manji od 64, oni se sortiraju insertion sort algoritmom. Insertion sort je veoma koristan za sortiranje malih kolekcija, posebno kod kolekcija koje su skoro sortirane. Insertion sort sortira kolekciju tako što umeće jedan po jedan element iz nesortiranog u sortirani deo kolekcije.
Ukoliko je broj elemenata veći, kolekcija se deli na kraće podnizove (prolaze, tokove, engl. runs). U prvoj fazi se određuje dužina prolaza (uglavnom se gleda da bude više od 32). Kolekcija se podeli u prolaze (segmente), pa se elementi prolaza sortiraju upotrebom insertion sort algoritma. Na kraju se susedni prolazi spajaju modifikovanim merge sort algoritmom. Kroz primer prikazaćemo uproštenu verziju algoritma:
Početna kolekcija: [5, 3, 7, 6, 1, 4, 9, 2, 8]
- Podelimo kolekciju na prolaze. Pošto je kolekcija kratka, zanemarićemo minimalnu dužinu od 32 elementa.
Segmenti: [5, 3], [7, 6], [1, 4, 9], [2, 8] - Pošto prolazi još uvek nisu formirani, kreiramo ih sortiranjem segmenata.
Prolazi: [3, 5], [6, 7], [1, 4, 9], [2, 8]
Ceo niz: [3, 5, 6, 7, 1, 4, 9, 2, 8]
- Spajanje prolaza
Spojeni prolazi: [3, 5, 6, 7], [1, 2, 4, 8, 9]
Ceo niz: [3, 5, 6, 7, 1, 2, 4, 8, 9]
- Povećava se veličina prolaza dok ne dostigne dužinu niza. Uglavnom se duplira (dakle od 32, pa 64, pa 128 elemenata).
- Spajanje prolaza
Ceo niz: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Da zaključimo, timsort je veoma efikasan algoritam sortiranja. U najgorem slučaju se izvršava u O(n log n) vremenu. Jedna mana bi mogla da bude prostorna kompleksnost, jer algoritam u osnovnoj implementaciji zahteva dodatnu memoriju. Iako postoji in-place implementacija, ona utiče na performanse pa se, u tom slučaju, algoritam izvršava u većem broju operacija.
U videu možete pogledati primer izvršavanja timsort algoritma:
