Radixsortering
Radixsortering sticker ut bland sorteringsalgoritmerna: den frågar aldrig vilket av två värden som är störst. Den läser talen siffra för siffra och sorterar dem efter en siffra i taget, med tio hinkar. Idén är äldre än datorerna: det var så sorteringsmaskinerna för hålkort fungerade.
Idén
Sortera talen enbart efter entalssiffran. Sortera dem sedan efter tiotalssiffran, men så att tal med samma tiotalssiffra behåller den ordning som första varvet gav dem. Sedan efter hundratalssiffran, på samma sätt. Efter sista varvet är listan sorterad: hundratalen avgör först, tal med samma hundratal står redan i ordning efter sina tiotal, och tal med samma tiotal i ordning efter sina ental.
Ett varv, med hinkar
Varje varv använder tio hinkar, en för varje siffra 0 till 9. Gå igenom listan från början till slut och flytta varje tal till hinken för dess siffra, bakom talen som redan ligger där. Töm sedan tillbaka hinkarna i listan i ordning, hink 0 först. Att talen flyttas i listans ordning och läggs sist i en hink är det som gör varvet stabilt. Appen räknar först talen för varje siffra, så att hinkarna kan stå sida vid sida i en rad, var och en direkt efter den förra: det är en räknesortering på en siffra.
Ett exempel
Ta 170, 45, 75, 90, 802, 24, 2, 66. Efter entalssiffran: 170, 90, 802, 2, 24, 45, 75, 66. Efter tiotalssiffran: 802, 2, 24, 45, 66, 170, 75, 90; observera att 802 och 2, båda med tiotalssiffran 0, behåller sin ordning från första varvet. Efter hundratalssiffran: 2, 24, 45, 66, 75, 90, 170, 802. Tre varv över åtta tal: 24 lästa siffror och 48 flyttar, och inte en enda jämförelse.
Hur snabb är den?
Varje varv läser en siffra i varje tal och flyttar varje tal två gånger, så för n tal med d siffror växer arbetet med n · d. En jämförande sortering kräver i värsta fall minst ungefär n log₂ n jämförelser, eftersom den måste skilja mellan n! möjliga ordningar med en ja-eller-nej-fråga i taget. Radixsortering är inte bunden av det, eftersom den aldrig ställer sådana frågor. För många korta nycklar, som en miljon tal under 1 000, är tre varv betydligt mindre arbete än de ungefär 20 miljoner jämförelser som en jämförande sortering skulle behöva. För långa nycklar eller få värden försvinner fördelen.
LSD och MSD, och historia
Versionen här börjar med den minst signifikanta siffran (LSD). Det omvända sättet, mest signifikanta siffran först (MSD), delar upp listan i hinkar efter första siffran och sorterar varje hink för sig, vilket passar strängar av olika längd. Radixsortering går tillbaka till de hålkortssorterare som följde på Herman Holleriths tabuleringsmaskiner för den amerikanska folkräkningen 1890: en sorterare släppte varje kort i ett av tio fack efter hålet i en kolumn, och operatörerna körde bunten genom maskinen en gång per kolumn, med början i den sista.
Utforska
Öppna appen och tryck på Steg. Varje varv räknar först siffrorna, och det märker ut hinkarna 0 till 9 i raden under listan. Sedan faller talen ner i sina hinkar ett i taget, med den aktiva hinken markerad, och kopieras tillbaka. Skriv dina egna tal upp till 999, som exemplet ovan, för att se alla tre varven.
Ofta ställda frågor
Vilken tidskomplexitet har radixsortering?
O(n · d) för n nycklar med d siffror i en fast bas, plus kostnaden för hinkarna i varje varv. Den behöver O(n) extra minne för bufferten som hinkarna ligger i.
Är radixsortering stabil?
LSD-radixsortering måste vara det: den fungerar bara för att varje varv håller värden med samma siffra i den ordning de kom in. Slutresultatet är därför också stabilt.
Klarar radixsortering negativa tal eller decimaltal?
Inte direkt, men med ett knep: förskjut negativa tal så att alla blir positiva, eller sortera dem för sig och vänd på dem. Flyttal kan sorteras efter sina bitmönster efter en liten omvandling.
Varför bas 10?
För att den är lätt att följa. Datorer sorterar oftast 8 eller 16 bitar i taget, så ett 32-bitarstal kräver fyra eller två varv, med 256 eller 65 536 hinkar.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova radixsortering