Räknade
Flyttar
Räknare

  • Räknas
  • Nyss flyttad
  • På plats

Mer om räknesortering

Räknesortering

Räknesortering fungerar när värdena är heltal inom ett litet intervall. Den har en räknare för varje möjligt värde, räknar hur ofta varje värde förekommer och vet utifrån antalen exakt var varje värde hör hemma. Se räknarna fyllas medan listan läses och tömmas igen när varje värde flyttas till sitt block, en flytt i taget. 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. Remsan mellan listan och buffertraden har en räknare för varje värde. Rutorna visar antalet räknade värden, flyttar och räknare. Välj hur många staplar, hur de börjar, eller skriv dina egna tal. 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. Prova en lista med få unika värden.
  2. Tryck på Spela, eller använd Steg och Bakåt för att gå ett värde i taget. Dra i stegreglaget för att hoppa var som helst i sorteringen.
  3. Följ räknarna: de fylls på medan listan läses och räknar sedan ned när varje värde placeras.

Så fungerar räknesortering

Gör en räknare för varje värde från det minsta till det största. Läs listan en gång och lägg till ett på räknaren för varje värde du ser. Summera sedan antalen från det minsta värdet: ett värdes block börjar direkt efter alla mindre värden. Gå till sist igenom listan igen, flytta varje värde till nästa lediga plats i sitt block och kopiera tillbaka resultatet.

Snabb för ett litet intervall

Räknesortering läser listan två gånger och går igenom räknarna en gång, så arbetet växer med n + k: antalet värden plus antalet räknare. För många värden inom ett litet intervall, som provpoäng från 0 till 100 eller åldrar, slår det alla jämförelsebaserade sorteringar. För ett brett intervall slösar den tid och minne på räknare som ingen använder: tre värden utspridda från 1 till 1 000 000 skulle kräva en miljon räknare. Det är också steget som radixsortering upprepar för varje siffra.

Ofta ställda frågor

Hur fungerar räknesortering?

Den räknar hur ofta varje värde förekommer, summerar antalen för att hitta var varje värdes block börjar och flyttar sedan varje värde direkt till nästa lediga plats i sitt block. Den jämför aldrig två värden.

När ska du använda räknesortering?

När värdena är heltal, eller kan göras om till heltal, och intervallet från minsta till största inte är mycket större än antalet värden: betyg, åldrar, korta koder. Då tar den tid proportionell mot n + k.

Är räknesortering stabil?

Ja, när värdena flyttas i listans ordning till nästa lediga plats i sitt block, som här. Det är därför radixsortering kan använda den för varje siffra.

Varför inte bara skriva varje värde så många gånger som det räknades?

För vanliga tal fungerar det, och det är till och med enklare. Men riktiga data innehåller oftast mer än nyckeln, till exempel ett namn till varje poäng, och det går förlorat om bara de räknade nycklarna skrivs ut. När själva elementen flyttas följer allt med.

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