Timsort

Timsort on sorteerimisalgoritm, mis on saadud piste- ja ühildusmeetodeid kombineerides ning alusmeetodeid optimeerides ja täiendades. Timsort loodi 2002. aastal Pythoni programmeerimiskeele jaoks Tim Petersi poolt. Lisaks on Timsorti implementeeritud veel mitmed programmeerimiskeeled nagu Java, Swift, ja Rust. Timsort töötab jaga-ja-valitse algoritmi põhimõttel, mis lühidalt seisneb kolmes sammus: jaga sisendmassiiv väiksemateks massiivideks, sorteeri väiksemad massiivid kasutades kahendpistemeetodit, ühilda saadud väiksemad massiivid tagasi üheks tervikuks. Tulemuseks on sorteeritud massiiv. Timsort kasutab ära massiivis juba esinevaid sorteeritud lõike. Timsorti halvima juhu ajaline keerukus on O("n" log "n"), parima juhu ajaline keerukus aga O("n").
Algoritmi kirjeldus.
Timsort on keeruline algoritm. Süvitsi mõistmiseks on kasulik algoritm jagada osadeks. Tim Peters lõi algoritmi põhimõttega, et sorteerides ära kasutada juba sorteeritud lõike, mis esinevad pärismaailmas kasutusel olevatel andmemassiivides. Implementatsiooniks on tarvilik luua kõigepealt meetod kahendotsinguks ning piste- ja ühildusmeetodid. Timsort on stabiilne sorteerimisalgoritm, st sama väärtusega elementide järjekord sorteerimisel ei muutu.
Enne detailsemat algoritmi kirjeldust oleks tarvis teada järgmiseid termineid ja nende põhimõtteid:
Timsort kasutab pistemeetodit sorteerimaks massiive, milles on alla 64 elemendi. Pistemeetod on suurte massiivide puhul aeglane, ent õige implementatsiooni korral väikeste massiivide puhul väga kiire.
Esimene samm: "minrun"-i leidmine
Teine samm: sisendmassiivi tükeldamine "run"-ideks ning nende sorteerimine
Kolmas samm: sorteeritud "run"-ide ühildamine
Tingimused, mida Timsort kasutab määratlemaks, kas "run-"e pinu peal peab omavahel ühendama:
Olgu X, Y, Z pinu pealmised "run-"id. Püstkriipsud "run-"i ümber tähendavad "run-"i pikkust, nt |X|.
i. |Z| &gt; |X| + |Y|
ii. |Y| &gt; |X|
Kui üks neist tingimustest on rikutud, ühendatakse omavahel Y ja lühem X või Z seast.
Seda sammu korratakse kuni kogu pinu täidab neid tingimusi.
Käsitlemata "run"-ide puhul vaadeldakse pinu uuesti läbi, tehes vahetusi ja ühildamisi kui vaja.
Kolmanda sammu eesmärk on hiljem ühildusmeetodiga ühendada järjest sarnasema pikkusega "run-"id, et ühildumine oleks efektiivne.
Näide: oletame, et meil on ideaalne juhus, meil on 8 "run"-i suurusega 128, 64, 32, 16, 8, 4, 2, 2 (järjekord on tegelikkuses suvaline). Algoritm ei ühenda ühtegi "run-"i enne, kui 2 ja 2 saavad pinus "run-"e kontrollides kokku. Sellele järgneb 7 perfektset, efektiivset ühendamist.
Neljas samm:
Eelnevas sammus sorteerisime ja ühendasime erinevaid "run-"e, et saada pinusse optimaalne viimane "run-"ide ühendamise järjekord, lähtuvalt pikkustest (et lõplik ühendamine toimuks võimalikult sarnase pikkusega "run-"idest).
Nüüd hakkame järjest ühendama kahe haaval järelejäänud "run-"e, lõpuks saades sorteeritud massiivi.
i. neist väiksema asetame lühemasse "run-"i (need elemendid on ajutises olemas)
ii. seame järgmiseks vaadeldavaks elemendiks ära võetud elemendist järgmise
iii. kordame kuni üks "run-"idest (suurem või ajutine) on täielikult läbi vaadatud
Tulemusena lõpuks on sorteeritud massiiv.
Neljandas sammus kasutab algoritm ühildusmeetodit, kuid mitte tavalist - seda on kohandatud, suurendades efektiivsust, kasutamaks eelnevalt leitud "run-"e. See tähendab, et kuigi algoritm justkui ütleb neljandas sammus, et hakkame ükshaaval võrdlema kahe "run-"i elemente, siis tegelikult Timsort teeb seda efektiivsemalt. Näide: olgu meil "run-"id elementidega [1, 2, 3, 4, … 100] ning [101, 102, 103, .. 200]. Ebaefektiivne oleks neid üksikute võrdluste põhjal hakata ühildama.
Timsort kasutab selleks võtet, mida kutsutakse nimega "galloping." Eesti keeles samuti galopp, tähendab see sisuliselt seda, et elemente ei tõsteta ühildatud, sorteeritud "run-"i mitte ükshaaval, vaid lõikude kaupa, mis kiirendab protsessi, kuna individuaalsete võrdluste arv on vähendatud. Lõigud leitakse kasutades kahendotsingut.
Näide, et toimuvat illustreerida paremini:
Olgu meil "run" X = [1, 2, 3, 4, 5, .. 100] ning Y = [101, 102, 103, .. 200].
Esimesed 7 (eelnevalt defineeritud algne galopi sammu suurus) elementi "run-"ist X võrreldakse "run" Y esimese elemendiga. 101 &gt; 7, 6, 5… Kõik need "run" X elemendid on väiksemad kui mistahes Y elemendid, mistõttu võib kõik need tõsta sorteeritud "run-"i. Vaatluse alla võetakse järgmised "run" X elemendid 8, 9, 10 jne ning võrreldakse taaskord Y esimese elemendi, 101-ga. Galopi samm muutub järjest suuremaks, et leida veel suuremaid lõike, mille saab sorteeritud "run-"i tõsta.
Joonisel on näha, et Y elemendid 9, 12, 13, 14, 15 on kõik väiksemad kui ajutises "run"-is olev element 21, mistõttu võib kõik punaseks värvitud Y elemendid tõsta sorteeritud "run-"i.
Andmete tükkide kaupa liigutamine on märgatavalt kiirem kui elementide ükshaaval võrdlemine ja tõstmine, mis annabki Timsordi tema efektiivsuse ja kiiruse.
Keerukused.
Ajalised keerukused:
Ruumiline keerukus: O("n")
Verifikatsioon.
2015. aastal leidsid hollandi ja saksa teadlased tavapärases Java Timsordi implementatsioonis vea ning andsid välja verifitseeritud parandatud algoritmi.
2018. aastal tõestati Timsordi halvima juhu ajaline keerukus.