sorteringsalgoritmer är en besvärlig kombination av grundläggande nödvändiga och djupt omtvistade. Från nya ingenjörer som vill imponera i en intervju till äldre ingenjörer som letar efter en lösning på en snabbt skalande Databas, det finns otaliga faktorer att ta hänsyn till. Vad är hastigheten på jämförelsen mellan två objekt? Vad är bytestiden? Hur stor är databasen? Vilken typ av objekt innehåller den? Är det redan halvsorterat? Måste resultaten vara stabila?

var och en av dessa frågor kan dra ut argument till förmån för en eller annan algoritm. Är källdata stora och komplexa? De flesta språk standard till standard, snabb sortering med sin O (n log n) tidskomplexitet. Är det mindre? Insättning Sortera fungerar underverk på dem. Mestadels sorterad? Heck, Bubble Sort kan nästan fungera för det. Om du vill läsa/visualisera fördelarna med varje, kolla in denna jämförelse av toptal.com.

en sorteringsalgoritm som du inte hittar på den webbplatsen, eller nästan någon annan, är Tim Sort. Denna obskyra sort är för närvarande unik för Python och används som standardsorteringsalgoritm. Ring array.sort I Python, och Tim Sort är vad som körs. Trots detta är det sällsynt att hitta ingenjörer som både känner och förstår Tim Sort. Så: vad är det?

Tim Sort implementerades först 2002 av Tim Peters för användning i Python. Det kom påstås från förståelsen att de flesta sorteringsalgoritmer är födda i Skolrum och inte utformade för praktisk användning på verkliga data. Tim Sort utnyttjar vanliga mönster i data och använder en kombination av Sammanslagningssortering och Infogningssortering tillsammans med viss intern logik för att optimera manipuleringen av storskaliga data.

• varför Tim Sortera?
• implementeringen i tre steg
• binär sökning
• Insertion Sortera & sammanfoga Sortera
• implementera Tim Sort
• slutsats
• tack

varför Tim Sortera?

titta på Figur 2, Vi kan omedelbart se något intressant. I bästa fall överträffar Tim Sort Merge Sort och Quick Sort. I värsta fall körs den med jämförbar Hastighetssammanfogning och överträffar faktiskt snabb sortering. Med andra ord är det oväntat snabbt.

När det gäller rymden är Tim Sort på den sämre änden av spektrumet, men rymdhänsynen för de flesta sorteringsalgoritmer är ganska gles. O (n) är inte för grovt i de flesta fall; det är värt att notera som en möjlig brist, och den enda platsen där Quick Sort verkligen överträffar Tim Sort.

det sista objektet som sorteringsalgoritmer ofta bedöms på är stabilitet. Stabilitet är konceptet att när de sorteras behåller objekt av lika värde sin ursprungliga ordning. Nu kanske du undrar varför vi bryr oss om det. Artiklarna är av lika värde-varför har vi något emot hur de beställs?

det enkla svaret är att stabilitet är viktigt för staplade sorter. Det vill säga, du sorterar först baserat på ett kriterium, sedan baserat på ett andra. Om du gör det i en instabil algoritm förlorar du omedelbart pålitlighet från din första sort när du kör den andra. Som referens är snabb sortering instabil och sammanfoga sortering är stabil.

Tim Sort är också stabil, för att inte tala om snabb om något tungvikt(i jämförelse med snabb sortering endast). Medan sorteringsalgoritmer kan (och bör) bedömas utifrån andra överväganden är dessa de tre stora.

implementeringen i tre steg

Tim Sort är komplex, även med algoritmiska standarder. Genomförandet är bäst uppdelat i delar.

binär sökning

det första du behöver för att implementera en Tim-Sort är en binär sökmetod. Detta används bara för att implementera din Insättningsort senare.

för referens: binära sökalgoritmer

Insertion Sortera & sammanfoga Sortera

För det andra måste du koda Insertion sortera och sammanfoga Sortera. Dessa är välkända algoritmer, och bör vara i bakfickan på de flesta ingenjörer, men vi ska gå igenom grunderna i hur de fungerar och varför de är värdefulla för oss här.

insertion sort är en mycket grundläggande sorteringsalgoritm. Den går genom arrayen, och när den stöter på ett objekt som inte är i ordning (strängt mindre/mer än objektet före det) flyttar det det till lämplig position i den redan sorterade arrayen. Insertion Sort är ökänd för att arbeta mycket snabbt på redan sorterade matriser, liksom mindre matriser. Faktum är att vi kan se från Fig 2 Att insättningssortering har en imponerande bästa körtid på O(n). Tänk på att gå vidare med Tim Sort: bästa fallet för insättning Sort är en redan sorterad array. Det kanske låter dumt, men det kommer att vara relevant.

merge sort å andra sidan fungerar enligt en grundläggande princip: det är ytterst lätt att slå samman redan sorterade matriser. Så det delar upp en startmatris i hälften om och om igen tills det bara är enstaka element. Sedan bygger det långsamt om huvudmatrisen genom att slå samman dessa element i sorterad ordning. Eftersom vi började från byggstenar i storlek ett var det väldigt enkelt att bygga initiala sorterade arrayer. Då är det lätt att slå samman dem. I slutändan spenderar vi O (n log n) tid, och (viktigare) gör vi det på ett sätt som garanteras vara stabilt.

till exempel implementeringar Se:

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

Insertion Sort:https://www.geeksforgeeks.org/insertion-sort/

implementera Tim Sort

nyckeln till att förstå Tim sorts implementering är att förstå dess användning av körningar. Tim Sort utnyttjar naturligt förekommande förinställda data till sin fördel. Med presorted menar vi helt enkelt att sekventiella element alla ökar eller minskar (vi bryr oss inte om vilka).

först ställer vi in en minrun storlek. Vad vi menar med detta är att vi vill se till att alla våra körningar är åtminstone en viss längd. Observera att vi inte garanterar att vi hittar körningar av denna storlek — vi kommer in i detta senare. Vi säger helt enkelt att en körning måste vara minst av en viss längd.

När vi stöter på en körning ställer vi den åt sidan. När vi hittar den längsta körningen inom ettminrun intervall. Vi har nu en välbekant datastruktur: en liten, sorterad array. Om det är minst minrun I Längd, då huzzah! Vi är bra på att gå vidare. Om det inte är, sätter vi insättningssortering i spel.

Du kanske kommer ihåg från ovan att Infogningssortering är särskilt effektiv på två typer av arrayer: små och redan sorterade. Vad vi just gjort är en liten, sorterad array. Om det inte är minst minrun I längd, når vi framåt och tar tag i tillräckligt med andra element för att slutföra körningen, använd sedan insättningssortering för att driva dem in i vår sorterade array, snabbt och enkelt. Självklart, om en körning möter slutet av matrisen kan du låta det vara lite kort.

När du har skapat alla dina körningar (dvs. sorterade subarrays) använder du din Sammanfogningssortering för att gå med dem tillsammans. I bästa fall är hela arrayen redan sorterad och Tim Sort är smart nog att veta att det inte behöver göra något annat. Andra gånger tenderar det bara att vara extremt effektivt. Som en extra fördel är både Infogningssortering och Sammanfogningssortering stabila, så den resulterande matrisen är stabil.

För dem som föredrar kulor:

1. upprätta enminrun storlek som är en effekt av 2 (vanligtvis 32, aldrig mer än 64 eller din insättning Sort kommer att förlora effektivitet)
2. hitta en körning i den förstaminrun av data.
3. om körningen inte är minst minrun I Längd, använd insättningssortering för att ta tag i efterföljande eller tidigare objekt och sätt in dem i körningen tills det är rätt minsta storlek.
4. upprepa tills hela matrisen är uppdelad i sorterade underavsnitt.
5. använd den senare halvan av Merge Sort för att gå med i de beställda matriserna.

slutsats

Tim Sort är kraftfull. Det är snabbt och stabilt, men kanske viktigast av allt utnyttjar det verkliga världsmönster och använder dem för att bygga en slutprodukt. Är det för varje situation? Förmodligen inte. Lycka till att programmera det på en whiteboard under en intervju, och om du bara behöver en snabb enkel sorteringsalgoritm i en nypa vill du förmodligen inte bry dig om att implementera något så här komplext. Men för Dataforskare som krossar siffror är det mer än värt en titt.

för nyfikna kan du kolla in hela Tim-Sorteringskoden på github.

tack

Tack en och alla till mina läsare. Jag uppskattar din tid och hoppas verkligen att du hittade innehållet informativt. Om du har några frågor eller svar är du välkommen att släppa en nedan.