Timsort

Pasul 1. Împărțirea în subbariere și sortarea lor.

• Pointerul elementului curent este plasat la începutul matricei de intrare.
• Începând de la elementul curent, această matrice este căutată pentru rularea sub-taxa ordonată. Prin definiție, run va include în mod unic elementul curent și pe cel care îl urmează. Dacă subbarajul rezultat este sortat în ordine descrescătoare, elementele sunt rearanjate astfel încât să meargă în ordine crescătoare.
• Dacă dimensiunea rulării curente este mai mică decât minrun, elementele care urmează rulării găsite sunt selectate în cantitatea minrun-size (run). Astfel, rezultatul va fi un subgrup de dimensiune minrun sau mai mult, din care o parte (și, în mod ideal, toată) este comandată.
• Sortarea prin inserare este aplicată acestui subbaraj. Deoarece dimensiunea subbarajului este mică și o parte a acestuia este deja comandată, sortarea este rapidă și eficientă.
• Pointerul elementului curent este plasat pe elementul care urmează subbarajului.
• Dacă nu se ajunge la sfârșitul matricei de intrare, treceți la pasul 2, în caz contrar, terminați acest pas.

Pasul 2. Îmbinați.

Dacă datele matricei de intrare au fost apropiate de aleatoriu, atunci dimensiunea subtabelor ordonate este apropiată de minrun; dacă datele au conținut intervale ordonate, subbarray-urile ordonate au o dimensiune mai mare decât minrun.

Trebuie să îmbinăm aceste sub-tare pentru a obține matricea rezultată, complet ordonată. Pentru a fi eficientă, o asociație trebuie să îndeplinească două cerințe:

• Îmbinați sub-mare de dimensiuni aproximativ egale
• Mențineți stabilitatea algoritmului - adică nu faceți permutări fără sens.

Algoritm:

• Este creată o stivă goală de perechi <subbarray start index>-<subbarray size>. Se ia primul subbary comandat.
• Perechea de date <start index>-<size> pentru subbary-ul curent este adăugată la stivă.
• Se stabilește dacă este necesară îmbinarea subbaryului curent cu cele anterioare. Pentru a face acest lucru, sunt verificate două reguli (fie X, Y și Z să fie dimensiunile primelor trei subbaryuri din stivă):

• Dacă una dintre reguli este încălcată, matricea Y este îmbinată cu cea mai mică dintre matricele X și Z. Se repetă până când ambele reguli sunt îndeplinite sau datele sunt complet ordonate.
• Daca mai sunt subbarajuri neconsiderate, se ia urmatoarea si se trece la pasul 2. In caz contrar, finalul.

Scopul acestei proceduri este menținerea echilibrului. Modificările vor arăta ca în imaginea din dreapta, ceea ce înseamnă că dimensiunile subgrupurilor de pe stivă sunt eficiente pentru sortarea ulterioară. În cazul ideal: există subgrupuri de mărimea 128, 64, 32, 16, 8, 4, 2, 2. În acest caz, nu se vor efectua îmbinări până la întâlnirea ultimelor 2 subgrupuri, după care vor fi 7 îmbinări perfect echilibrate. efectuat.

Procedura de îmbinare a subbarajelor

Procedura de îmbinare traversează și compară în funcție de modul în care sunt aranjate sub-tabele, astfel încât algoritmul necesită proceduri de traversare de la stânga la dreapta (dacă matricea mai mică este în stânga) și de la dreapta la stânga (dacă matricea mai mică este în dreapta). În practică, de obicei ne limităm la prima procedură și selectăm matricea din stânga, indiferent de dimensiunea acesteia - acest lucru nu are aproape niciun efect asupra vitezei de sortare.

1. O matrice temporară este creată cu dimensiunea celei mai mici dintre sub-tarile unite.
2. Cea mai mică dintre subtaiere este copiată într-o matrice temporară
3. Pointerii către poziția curentă sunt plasați pe primele (ultimele) elemente ale unui tablou mai mare și temporar.
4. La fiecare pas următor, se ia în considerare valoarea elementelor curente din tablourile mai mari și temporare, cele mai mici (mai mari) dintre ele sunt luate și copiate într-o nouă matrice sortată. Pointerul elementului curent este mutat în tabloul din care a fost luat elementul.
5. Pasul 4 se repetă până când una dintre matrice se termină.
6. Toate elementele matricei rămase sunt adăugate la sfârșitul noii matrice.

Modificarea procedurii de îmbinare a subbaryurilor (Mod Galop)

Imaginează-ți procedura de îmbinare a următoarelor matrice:

Procedura de mai sus va funcționa pentru ei, dar de fiecare dată la al patrulea pas va trebui să efectuați o comparație și o copie. Ca rezultat, 10.000 de comparații și 10.000 de exemplare. Algoritmul lui Timsort oferă o modificare în acest moment, pe care el o numește „galop”. Algoritm:

• Procedura de îmbinare începe, așa cum se arată mai sus.
• La fiecare operațiune de copiere a unui element dintr-un subbaraj temporar sau mai mare în cel rezultat, se reamintește din ce subgrup a fost elementul.
• Dacă un anumit număr de elemente (în această implementare a algoritmului acest număr este 7) au fost deja preluate din aceeași matrice, se presupune că vom continua să luăm date din acesta. Pentru a confirma această idee, algoritmul intră în modul „galop”, adică se deplasează prin matricea candidată pentru furnizarea următoarei porțiuni mari de date prin căutare binară (matricea este ordonată) a elementului curent din a doua. matrice care urmează să fie alăturată.
• În momentul în care datele din matricea furnizorului curent nu mai sunt adecvate (sau s-a ajuns la sfârșitul matricei), datele sunt copiate în întregime.

Modul galop, de exemplu:

Primele 7 iterații compară numerele 1, 2, 3, 4, 5, 6 și 7 din matricea A cu numărul 20000, deoarece 20000 este mai mare - elementele matricei A sunt copiate în cel rezultat. Pornind de la următoarea iterație, algoritmul trece la modul „galop”: compară secvenţial elementele 8, 10, 14, 22, 38, n+2^i, …, 10000 ale tabloului A cu numărul 20000 (~log2 N comparatii). După ce se ajunge la sfârșitul matricei A și se știe că totul este mai mic decât B, datele necesare din matricea A sunt copiate în cel rezultat.

Note

1. ↑ Funcție de sortare incorectă în Android, Rust, Java și Python . „Hacker”. Consultat la 5 decembrie 2015. Arhivat din original pe 8 decembrie 2015. (nedefinit)
2. ↑ jjb Commit 6804124: Înlocuiți „mergesort modificat” în java.util.Arrays.sort cu timsort . Kit de dezvoltare Java 7 Hg repo . Consultat la 24 februarie 2011. Arhivat din original pe 4 septembrie 2012. (nedefinit)
3. ↑ Apple Swift  Sort . GitHub . Preluat la 5 mai 2021. Arhivat din original la 24 iunie 2021.
4. ↑ Clasa: java.util.TimSort<T> . Documentația Android JDK 1.5 . Consultat la 24 februarie 2011. Arhivat din original pe 4 septembrie 2012. (nedefinit)
5. ↑ Hetland, 2010 .

Literatură

• Peter McIlroy „Optimistic Sorting and Information Theoretic Complexity”, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, ISBN 0-89871-313-7 , Chapter 53, pp 467-474, ianuarie 1993. [1]
• Magnus Lie Hetland. Algoritmi Python: Stăpânirea algoritmilor de bază în limbajul Python. - Apress, 2010. - 336 p. - ISBN 978-1-4302-3237-7 .

Link -uri

• Reprezentarea algoritmului de la creatorul său  (ing.) . Arhivat din original pe 4 septembrie 2012.
• Timsort implementat în Python pentru PyPy  ( py). Arhivat din original pe 4 septembrie 2012.
• Vizualizare algoritm  (ing.) . Arhivat din original pe 4 septembrie 2012.