Timsort
Script error: No such module "AfC submission catcheck".
Timsort[edit]
Timsort on efektiivne sorteerimisalgoritm, mis on saadud piste- ja ühildusmeetodeid kombineerides[1], alusmeetodeid optimiseerides ning täiendades. Timsort loodi 2002. aastal Pythoni programmeerimiskeele jaoks Tim Petersi poolt[2]. Lisaks on Timsorti implementeeritud veel mitmed programmeerimiskeeled nagu Java[3], Swift[4] ja Rust[5]. 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[1]. 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[edit]
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- ning ü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:
run - kui massiivis on üle 64 elemendi, otsib Timsort massiivist natural run-e, mis on vähemalt kahest elemendist koosnevad juba sorteeritud massiivi lõigud, mis ongi algoritmi kontekstis run. Kui leitakse kahanevas järjekorras run, pööratakse see tagurpidi. Viited nendele lõikudele pannakse pinusse[6]. Väiksematel (pikkus n < 64) massiividel rakendatakse lihtsalt pistemeetodit.
minrun - massiivi pikkusest tuletatud arv vahemikus (32; 64], millega jagatise tulemusena massiivi pikkusega saadakse kas võrdne või väiksem arv mõnest kahe astmest. Algoritm valib selle arvu, sest suvalises jadas on pikkade natural run-ide esinemine ebatõenäoline. Kui natural run-is esineb vähem kui minrun elementi, pikendatakse see run minrun elementi pikaks. Suvalises massiivis selle tulemusena kipuvad kõik run-id olema pikkusega minrun[7].
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[6].
Esimene samm: minrun-i leidmine
Teine samm: sisendmassiivi tükeldamine run-ideks ning nende sorteerimine
- alustame massiivi algusest, otsides natural run-e
- kui hetkene run on väiksem kui minrun, võta järgnevaid elemente kuni selle run-i pikkus on minrun
- saadud run sorteeritakse pistemeetodiga
Kolmas samm: sorteeritud run-ide ühildamine
- ideaalis peaks massiivis olema sarnase pikkusega sorteeritud run-id
- loo tühi ennikutest (run-i algusaadress, run-i pikkus) koosnev pinu
- hakka lisama run-e järjest pinusse
- iga pinusse lisamise puhul tuleb kontrollida, pinu peal olevad run-id vastavad järgnevatele tingimustele:
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| > |X| + |Y|
ii. |Y| > |X|[7]
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.
- loome ajutise run-i mille suurus on allesjäänud run-idest vähima pikkus
- paneme kõik elemendid lühemast run-ist ajutisse run-i
- võrdleme suurema ja ajutise run-i elemente:
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 binaarotsingut.
Näide, et toimuvat illustreerida paremini:
Olgu meil run X = [1, 2, 3, 4, 5, .. 100] ning Y = [101, 102, 103, .. 200].
.svg)
Esimesed 7 (eelnevalt defineeritud algne galopi sammu suurus) elementi run-ist X võrreldakse run Y esimese elemendiga. 101 > 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[edit]
Ajalised keerukused[8]:
Halvim juht: O(n log n)
Parim juht: O(n)
Keskmine juht: O(n log n)
Ruumiline keerukus: O(n)
Verifikatsioon[edit]
2015. aastal leidsid hollandi ja saksa teadlased[9] tavapärases Java Timsordi implementatsioonis vea ning andsid välja verifitseeritud parandatud algoritmi.
2018. aastal tõestati Timsordi halvima juhu ajaline keerukus[2].
Viited[edit]
- ↑ 1.0 1.1 Zhang, Yu; Zhao, Yongwang; Sanan, David (2018-12-08). "A Verified Timsort C Implementation in Isabelle/HOL". arXiv:1812.03318 [cs.SE].
- ↑ 2.0 2.1 Auger, Nicolas; Jugé, Vincent; Nicaud, Cyril; Pivoteau, Carine (2018). "On the Worst-Case Complexity of TimSort". DROPS-IDN/V2/Document/10.4230/LIPIcs.ESA.2018.4. Schloss-Dagstuhl - Leibniz Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2018.4. Unknown parameter
|s2cid=ignored (help) - ↑ "Loading..." bugs.openjdk.org. Retrieved 2024-01-03.
- ↑ "Is sort() stable in Swift 5?". Swift Forums. 2019-07-04. Retrieved 2024-01-03.
- ↑ "slice - Rust". doc.rust-lang.org. Retrieved 2024-01-03.
- ↑ 6.0 6.1 "Timsort — "The Fastest Sorting Algorithm" – The IE Blog". 2019-12-03. Retrieved 2024-01-03.
- ↑ 7.0 7.1 "cpython: 034b077d3015 Objects/listsort.txt". 2016-01-28. Archived from the original on 2016-01-28. Retrieved 2024-01-03.
- ↑ "TimSort - Data Structures and Algorithms Tutorials". GeeksforGeeks. 2017-05-19. Retrieved 2024-01-03.
- ↑ de Gouw, Stijn; Rot, Jurriaan; de Boer, Frank S.; Bubel, Richard; Hähnle, Reiner (2015). Kroening, Daniel; Păsăreanu, Corina S., eds. OpenJDK's Java.utils.Collection.sort() Is Broken: The Good, the Bad and the Worst Case. Computer Aided Verification. Lecture Notes in Computer Science. Cham: Springer International Publishing. pp. 273–289. doi:10.1007/978-3-319-21690-4_16. ISBN 978-3-319-21690-4. Search this book on
This article "Timsort" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Timsort. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
