Räknesortering
Räknesortering sorterar inte alls genom att jämföra värden. Om du vet att varje värde är ett heltal mellan, säg, 1 och 40, kan du helt enkelt räkna hur många det finns av varje och utifrån antalen räkna ut var varje värde hör hemma. För ett litet intervall är det ungefär så snabbt som sortering kan bli.
Räkna
Hitta det minsta och största värdet och gör en räknare för varje värde däremellan, alla med start på noll. Läs listan en gång från början till slut och lägg till ett på räknaren för varje värde du ser. Räknarna bildar nu ett histogram: hur många ettor, hur många tvåor och så vidare. Med n värden och k räknare tar det n steg.
Summera
Värdena som är lika med det minsta värdet kommer först, så deras block börjar på plats 1. Nästa värdes block börjar direkt efter dem, och så vidare: varje block börjar efter summan av alla antal före det. Dessa löpande summor, så kallade prefixsummor, gör histogrammet till en karta över den sorterade listan. Det tar k steg.
Placera
Läs listan en andra gång och flytta varje värde till nästa lediga plats i sitt block. Eftersom värdena flyttas i den ordning de förekommer behåller lika värden sin ursprungliga ordning: räknesortering är stabil. Kopiera tillbaka bufferten, så är listan sorterad. Appen visar hur varje räknare går ned igen medan dess värden placeras.
Ett exempel
Ta 4, 1, 3, 4, 2, 1, 4. Räknarna för 1 till 4 slutar på 2, 1, 1 och 3. Summeringen ger blocken: ettorna på plats 1 och 2, tvåan på plats 3, trean på plats 4 och fyrorna på plats 5 till 7. Att placera värdena i listans ordning ger 1, 1, 2, 3, 4, 4, 4: 7 räknade värden, 14 flyttar, 4 räknare och inga jämförelser.
När du ska använda den
Det totala arbetet växer med n + k. När k är litet jämfört med n, som tusen provpoäng från 0 till 100, är räknesortering snabbare än alla jämförelsebaserade sorteringar, som behöver ungefär n log₂ n jämförelser. När intervallet är brett är den slösaktig: några få värden utspridda upp till en miljon kräver en miljon räknare. Radixsortering löser det genom att köra räknesortering en gång per siffra, så att varje varv bara behöver tio räknare. Harold Seward beskrev räknesortering, tillsammans med radixsortering, 1954.
Utforska den
Öppna appen och tryck på Steg. Remsan mellan listan och buffertraden visar en räknare per värde. Se räknarna fyllas medan listan läses, blocken dyka upp i bufferten när antalen summeras och räknarna gå ned igen när värdena placeras. Välj få unika värden för att se stora block, eller skriv tal långt ifrån varandra för att se hur många räknare ett brett intervall kräver.
Ofta ställda frågor
Vilken tidskomplexitet har räknesortering?
O(n + k) för n värden och k möjliga värden, och O(n + k) extra minne för räknarna och bufferten.
Varför är räknesortering inte alltid snabbast?
Eftersom kostnaden beror på värdenas intervall, inte bara på hur många de är. Om intervallet är mycket större än listan står de flesta räknare kvar på noll, och tid och minne går till spillo.
Klarar räknesortering negativa tal?
Ja. Räknarna går från det minsta värdet till det största, så dra av det minsta värdet för att få en räknares index. Appen gör likadant.
Är räknesortering stabil?
Ja, så länge värdena flyttas i listans ordning till nästa lediga plats i sitt block. Radixsortering är beroende av det.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova räknesortering