sorteringsalgoritmer er en vanskelig kombinasjon av fundamentalt nødvendig og dypt omstridt. Fra nye ingeniører som ønsker å imponere i et intervju til eldre ingeniører som søker ut en løsning på en raskt skalerende database, er det utallige faktorer å ta hensyn til. Hva er hastigheten på sammenligning mellom to objekter? Hva er byttetiden? Hvor stor er databasen? Hvilken type objekter inneholder den? Er det allerede semi-sortert? Skal resultatene være stabile?

Hvert av disse spørsmålene kan trekke ut argumenter til fordel for en algoritme eller en annen. Er kildedataene store og komplekse? De fleste språk standard til standard, Rask Sortering Med Sin O (n log n) tid kompleksitet. Er det mindre? Innsetting Sort gjør underverker på dem. For det meste sortert? Heck, Bubble Sort kan nesten fungere for det. Hvis du vil lese/visualisere fordelene til hver, sjekk ut denne sammenligningen av toptal.com.

En sorteringsalgoritme du ikke finner på det nettstedet, eller nesten alle andre, Er Tim Sort. Denne obskure typen er for tiden unik For Python, og brukes som standard sorteringsalgoritme. Ring array.sort I Python, Og Tim Sort er det som blir utført. Til tross for Dette er det sjelden å finne ingeniører som både kjenner Og forstår Tim Sort. Så: hva er det?

Fig 1: Tim Peters, oppfinner av Timsort

Tim Sort ble først implementert i 2002 Av Tim Peters for Bruk I Python. Det kom angivelig fra forståelsen at de fleste sorteringsalgoritmer er født i skolerom, og ikke designet for praktisk bruk på virkelige data. Tim Sort utnytter vanlige mønstre i data, og benytter en kombinasjon Av Sammenslåingssortering og Innsettingssortering sammen med noen intern logikk for å optimalisere manipuleringen av storskala data.

hvorfor tim sort?

ser vi på figur 2, kan vi umiddelbart se noe interessant. På sitt beste, Tim Sortere utkonkurrerer Merge Sortering Og Rask Sortering. På sitt verste, det kjører på sammenlignbare speed Merge Sortering og faktisk utkonkurrerer Rask Sortering. Med andre ord, det er uventet fort.Når Det gjelder plass, Er Tim Sort på den verre enden av spekteret, men romvurderingen for de fleste sorteringsalgoritmer er ganske sparsom. O (n) er ikke for grovt i de fleste tilfeller; det er verdt å merke seg som en mulig mangel, og det ene stedet Hvor Rask Sortering virkelig overgår Tim Sortering.

det siste elementet som sorteringsalgoritmer ofte vurderes på, er stabilitet. Stabilitet er konseptet at når de sorteres, opprettholder objekter av lik verdi sin opprinnelige rekkefølge. Nå lurer du kanskje på hvorfor vi bryr oss om det. Varene er av lik verdi-hvorfor har vi noe imot hvordan de er bestilt?

det enkle svaret er at stabilitet er viktig for stablede sorter. Det vil si at du først sorterer basert på ett kriterium, deretter basert på en annen. Hvis du gjør dette i en ustabil algoritme, mister du øyeblikkelig pålitelighet fra din første sortering når du kjører den andre. Til referanse Er Hurtigsortering ustabil, Og Merge Sortering er stabil.

Tim Sort er også stabil, for ikke å nevne rask hvis litt tungvekt (i forhold Til Hurtigsortering bare). Mens sorteringsalgoritmer kan (og bør) dømmes av andre hensyn, er disse de store tre.

Implementeringen i Tre Trinn

Tim Sort er kompleks, selv etter algoritmiske standarder. Implementeringen er best brutt ned i deler.

Binært Søk

det første du trenger for å implementere En Tim-Sortering er en binær søkemetode. Dette brukes bare til å implementere Innsettingssorteringen senere.

for referanse: Binære Søkealgoritmer

Innsettingssortering & Slå Sammen Sortering

For Det Andre må Du kode Innsettingssortering Og Slå Sammen Sortering. Dette er kjente algoritmer, og bør være i baklommen til de fleste ingeniører, men vi går over grunnleggende om hvordan de fungerer og hvorfor de er verdifulle for oss her.

Fig 3: Innsettingsort (høflighet avhttps://www.geeksforgeeks.org/insertion-sort/)

innsettingssortering er en veldig grunnleggende sorteringsalgoritme. Den går gjennom matrisen, og når den møter et element som er ute av drift (strengt mindre / mer enn varen før den), flytter den den til riktig posisjon i den allerede sorterte matrisen. Innsetting Sort er beryktet for å jobbe veldig raskt på allerede sorterte arrays, samt mindre arrays. Faktisk kan Vi se Fra Fig 2 at Innsettingssorten har en imponerende best case-kjøretid På O (n). Husk fremover Med Tim Sort: best case For Innsetting Sort er en allerede sortert array. Det kan høres dumt, men det vil være relevant.

Fig 4: merge sortering (courtesy ofhttps://commons.wikimedia.org/wiki/File:Merge_sort_algorithm_diagram.svg)

merge sortering derimot opererer etter et grunnleggende prinsipp: det er svært enkelt å slå sammen allerede sorterte arrays. Så, det deler en start array i to om og om igjen før det er noe annet enn enkeltelementer. Deretter gjenoppbygger den sakte hovedgruppen ved å slå sammen disse elementene igjen i sortert rekkefølge. Fordi vi startet fra byggeklosser av størrelse en, var det veldig enkelt å bygge innledende sorterte arrays. Da er det enkelt å slå sammen dem. Til slutt bruker Vi O (n log n) tid, og (viktigere) gjør vi det på en måte som er garantert å være stabil.

for eksempel implementeringer se:

Merge Sortering: https://www.geeksforgeeks.org/merge-sort/

Innsetting Sortering: https://www.geeksforgeeks.org/insertion-sort/

Implementere Tim Sort

nøkkelen til å forstå tim Sort implementering er å forstå Bruken av kjøringer. Tim Sort utnytter naturlig forekommende presorted data til sin fordel. Ved presorted mener vi bare at sekvensielle elementer er alle økende eller avtagende (vi bryr oss ikke om hvilke).

først setter vi en minrun størrelse. Det vi mener med dette er at vi ønsker å sikre at alle våre løp er minst en viss lengde. Vær oppmerksom på at vi ikke garanterer at vi vil finne løp av denne størrelsen — vi kommer inn på dette senere. Vi sier bare at en løp må være minst av en viss lengde.

når vi møter en løp, setter vi den til side. Når vi finner den lengste løp i etminrun område. Vi har nå en kjent datastruktur: en liten, sortert array. Hvis det er minst minrun i lengde, så huzzah! Vi er klare til å gå videre. Hvis det ikke er det, setter Vi Innsettingssortering inn i spill.

du kan huske ovenfra At Innsettingssorten er spesielt effektiv på to typer arrays: små og allerede sorterte. Det vi nettopp laget er en liten, sortert array. Hvis det ikke er minst minrun i lengde, kommer vi fremover og tar nok andre elementer til å fullføre løp, og bruk Deretter Innsettingssortering for å skyve dem inn i vår sorterte array, raskt og enkelt. Selvfølgelig, hvis en løp møter slutten av arrayet, kan du la det være litt kort.

når du har opprettet alle løpene dine (dvs.sorterte delarrays), bruker Du Flettesorteringen til å bli med dem sammen. I beste fall er hele arrayet allerede sortert, Og Tim Sort er smart nok til å vite at Det ikke trenger å gjøre noe annet. Andre ganger har det en tendens til å bare være ekstremt effektiv. Som en ekstra fordel er Både Innsettingssortering og Sammenslåingssortering stabile, slik at den resulterende matrisen er stabil.

For de som foretrekker kuler:

1. Opprett en minrun størrelse som er en effekt på 2 (vanligvis 32, aldri mer enn 64 eller Din Innsettingssortering vil miste effektivitet)
2. Finn et løp i den første minrun av data.
3. hvis kjøringen ikke er minst minrun i lengde, bruk Innsettingssortering for å hente etterfølgende eller tidligere elementer og sett dem inn i kjøringen til den er riktig minimumsstørrelse.
4. Gjenta Til hele arrayet er delt inn i sorterte underavsnitt.
5. Bruk siste halvdel Av Merge Sortering for å bli med i de bestilte matrisene.

Konklusjon

Tim Sort er kraftig. Det er raskt og stabilt, men kanskje viktigst det utnytter virkelige verdensmønstre og utnytter dem til å bygge et sluttprodukt. Er det for enhver situasjon? Sannsynligvis ikke. Lykke til med å programmere det på en tavle under et intervju, og hvis du bare trenger en rask enkel sorteringsalgoritme i en klemme, vil du sannsynligvis ikke bry deg med å implementere noe dette komplekset. Men for dataforskere som knuser tall er det mer enn verdt en titt.

for de nysgjerrige, kan du sjekke Ut Hele Tim Sorteringskoden på github.

Takk

Takk en og alle til mine lesere. Jeg setter pris på din tid, og håper at du fant innholdet informativt. Hvis du har spørsmål eller svar gjerne slippe en nedenfor.