Lästa siffror
Flyttar
Varv

  • Aktiv hink
  • Nyss flyttad
  • Kopierade tillbaka
  • På plats

Mer om radixsortering

Radixsortering

Radixsortering sorterar heltal utan att någonsin jämföra två av dem. Den sorterar listan efter entalssiffran, sedan efter tiotalssiffran och sedan efter hundratalssiffran, och varje gång flyttar den värdena till tio hinkar och kopierar tillbaka dem i ordning. Se hinkarna fyllas i raden under listan, en flytt i taget, och se listan bli sorterad efter fler och fler siffror. Tryck på Spela för att se sorteringen, eller använd Steg och Bakåt för att gå en flytt i taget. Dra i stegreglaget för att hoppa vart som helst. Hinkarna 0 till 9 står sida vid sida i raden under listan. Rutorna räknar lästa siffror, flyttar och varv. Välj hur många staplar, hur de börjar, eller skriv dina egna tal upp till 999. När tavlan är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.

Hur det fungerar

  1. Välj antal staplar och startordning, eller skriv dina egna heltal upp till 999 för att se varvet för hundratalen.
  2. Tryck på Spela, eller använd Steg och Bakåt för att flytta ett värde i taget. Dra i stegreglaget för att hoppa var som helst i sorteringen.
  3. Följ varje varv: räkna siffrorna, flytta varje värde till sin hink och kopiera sedan tillbaka hinkarna.

Så fungerar radixsortering

Titta bara på sista siffran i varje tal och sortera listan efter den: lägg varje tal i en av tio hinkar, 0 till 9, i den ordning de kommer, och kopiera sedan tillbaka hinkarna en efter en. Gör samma sak med tiotalssiffran och sedan med hundratalssiffran. Eftersom varje varv behåller ordningen mellan tal med samma siffra avgör de tidigare varven fortfarande ordningen mellan dem, och efter sista varvet är hela listan sorterad.

Inga jämförelser alls

Jämförande sortering kräver i värsta fall minst ungefär n log₂ n jämförelser, vilket smart knep den än använder. Radixsortering kommer runt den gränsen genom att läsa siffror i stället: varje varv läser en siffra i varje värde och flyttar varje värde två gånger, så d siffror kräver d varv och arbetet växer med n · d. För långa listor med korta nycklar lönar det sig: en miljon tal upp till 999 kräver tre varv, där en jämförande sortering behöver runt 20 miljoner jämförelser. Priset är att den bara fungerar för nycklar som består av siffror eller tecken, och att den behöver plats för hinkarna.

Ofta ställda frågor

Hur fungerar radixsortering?

Den sorterar talen efter sista siffran, sedan efter siffran före den, och så vidare fram till första siffran. Varje varv lägger talen i tio hinkar efter den siffran, utan att ändra deras ordning, och kopierar tillbaka hinkarna. Efter varvet för den mest signifikanta siffran är listan sorterad.

Varför börja med sista siffran?

Eftersom varje varv är stabilt: tal med samma siffra behåller den ordning som de tidigare varven gav dem. Så det sista varvet, på första siffran, avgör ordningen, och vid lika siffror avgör de siffror som redan är sorterade. Det kallas LSD-radixsortering (least significant digit, minst signifikanta siffran).

Är radixsortering snabbare än quicksort?

Det kan den vara, för många korta nycklar: arbetet växer med antalet värden gånger antalet siffror, utan n log n. För få värden, mycket långa nycklar eller data som inte består av siffror är quicksort och mergesort oftast snabbare och enklare.

Hur hänger den ihop med räknesortering?

Varje varv i radixsortering är en räknesortering (counting sort) på en siffra: räkna hur många värden som har varje siffra, räkna ut var varje hink börjar och flytta dit värdena i ordning.

Skickas mina tal någonstans?

Nej. Sorteringen körs i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Gå till Editor