Introduktion till greve Sort

Räkna Sort är en icke-jämförelsebaserad sorteringsalgoritm som utmärker sig när man sorterar heltal över ett litet, känt sortiment. Till skillnad från jämförelsebaserade sorter som Quicksort eller Mergesort, som är beroende av parvisa elementjämförelser, bestämmer Counting Sort den sorterade ordningen genom att räkna frekvensen av varje distinkt värde. Detta tillvägagångssätt ger linjär tidskomplexitet under gynnsamma förhållanden, vilket gör det till ett val för många prestanda-kritiska applikationer där inmatningsdomänen är begränsad.

Algoritmen beskrevs först av Harold H. Seward 1954 och förblir en grundläggande teknik inom datavetenskap. Dess enkelhet och effektivitet gör det idealiskt för uppgifter som att sortera elevåldern, betyg eller någon heltalsdata med en blygsam spridning. Genom att utnyttja extra lagring proportionellt till värdeområdet undviker Counting Sort O (n log n) lägre gränsen för jämförelse sortering, uppnå O(n + k) tid där k är intervalet av ingångsvärden.

Hur greve Sort fungerar

Kärnmekanismen för greve Sort är enkel: det räknas hur många gånger varje värde visas i ingångsarrayen, sedan använder som räknas för att beräkna varje elements slutliga position. Processen består av tre olika faser:

  1. Räkna:[]] Skapa ett räkningsmängd av storlek k (intervallet av ingångsvärdena), initierat till noll. Sätt dig genom ingångsarrayen och stegra upp räknan för varje värde.
  2. ]Att bearbeta prefix:[] Förvandla räkningen till en prefixsummation, där varje element i index jag håller kumulativa tal av element mindre än eller lika med i. Detta steg bestämmer startpositionerna för varje distinkt värde i den sorterade utgången.
  3. Placera element:[] Om du korsar ingångsarrayen från höger till vänster (för stabilitet), använd räknarrayen för att hitta rätt index i utgångsarrayen, placera elementet där och dekretera räkningen. Den slutliga utgången är en sorterad kopia av ingången.

Algoritmen returnerar en ny sorterad array, vilket lämnar den ursprungliga oförändrade. En variant som kallas på plats räknar Sort ]] finns men används sällan eftersom den äventyrar antingen stabilitet eller rymdeffektivitet.

Steg-för-steg-exempel

Överväg att sortera matrisen [4, 2, 2, 8, 3, 1][] där värdena varierar från 0 till 8.

  1. ] Räkna med:[[] Räkna med arraystorlek 9 (0–8) → [0,1,2,1,0,0,0,1]. (Index 1 visas en gång, index 2 två gånger, index 3 två gånger, index 4 en gång, index 8 en gång.)
  2. ]Prefixsummor: Förvandla till kumulativ → [0,1,3,5,6,6,6,6,7]. Nu berättar varje värde oss startpositionen för det numret i sorterad produktion.
  3. Output:[]] Traverse original array from end: first element read is 1 → position = count[1] - 1 = 0 → output [0]=1, dekretantal[1] till 0. Next is 3 → position = count[3] - 1 = 4 → output [4]=3, count[3]=4. Fortsätt tills alla element placerade. Slutresultat: [1,2,3,4,8].

Detta exempel visar hur greve Sort undviker jämförelser helt och hållet, enbart beroende på aritmetisk verksamhet.

Beräkningskomplexitet

Tidskomplexitet

  • ]Bästa, genomsnittliga och sämsta fallet: O(n + k), där n är antalet element och k är intervallet av ingångsvärden. När k är liten i förhållande till n, löper algoritmen i linjär tid.
  • ] Jämförelse med jämförelsesort:] Quicksort och Mergesort har O(n log n) genomsnittlig komplexitet. För n = 106 och k = 1000, Räkna Sort? ( 1 000 000 operationer) är cirka 13 gånger snabbare än en typisk O(n log n) sort.

Rymdkomplexitet

  • ]Primär:]] O(k) för räkningen, plus O(n) för utgångsarrayen. Detta minnesöverhuvud kan vara förbjudet om k är stort (t.ex., sortering 32-bitars heltal där k = 232).
  • ]Stabil variant:] kräver en extra utgångsarray av storlek n; på plats varianter offra stabilitet eller använda komplex indexmanipulation.

När man använder greve Sort

Räkna Sort är mest effektivt under följande villkor:

  • Inmatningen består av heltal (eller data som kan kartläggas till ett litet heltalsintervall, till exempel tecken eller diskreta kategorier).
  • Omfånget k är inte signifikant större än n. En vanlig tumregel är k ≤ O(n).
  • Minnet är inte allvarligt begränsat, eftersom räkna array och utgång buffert kräver extra utrymme.
  • Stabilitet krävs (t.ex. sortering av flera nycklar). Standardgenomförandet är stabilt när element placeras från höger till vänster.

Utmärkt användningsfall inkluderar sorteringsgrader (0-100), åldrar (0-120), produktkategorier (upp till några hundra SKU), eller som subroutin i ]Radix Sort].

Begränsningar och överväganden

Trots sin hastighet har Counting Sort nackdelar som begränsar dess tillämplighet:

  • ]Integer endast:[] Den kan inte direkt sortera flytande punktnummer eller strängar om de inte omvandlas till en sammanhängande heltalsuppsättning.
  • ]Large range:[] Om k dvärgar n-till exempel, sorterar 100 nummer med värden mellan 1 och 107-antalgruppen förbrukar enormt minne medan den sorterar bara några element.
  • ]Non-adaptive:[] Räkna Sort kräver alltid att hela ingången skannas och att man bygger upp räkningen, även om data redan sorteras eller nästan sorteras.
  • ]Negativa värden:[ Standard Counting Sort antar icke-negativa heltal. För att hantera negativa kan du ändra värdena genom att subtrahera minimum (vilket gör intervallet 0 till max - min).

Dessa begränsningar innebär att greve Sort är ett specialiserat verktyg, inte en universell ersättning för allmänt ändamål algoritmer.

Jämförelse med relaterade Sortering Algoritmer

Räkna Sort vs Radix Sort

Radix Sort utökar idén genom att sortera siffror från minst betydande till de flesta betydande, med hjälp av en stabil sort (ofta räkna Sort) vid varje siffra. Medan greve Sort fungerar på ett pass över hela intervallet k, utför Radix Sort flera pass över ett mindre siffra (t.ex. bas 256), vilket minskar minnesanvändningen för stora k. Till exempel, sortering 32-bitars heltal med greve Sort skulle kräva en räkning av 232 poster, medan Radix Sort med 8-bit siffror kräver 256 poster per

Räkna Sort vs Bucket Sort

Bucket Sort distribuerar element i ett antal hinkar och sorterar varje hink individuellt (ofta med insättnings sort). Räkna Sort kan ses som ett speciellt fall av Bucket Sort där varje hink motsvarar ett enda distinkt värde. Bucket Sort fungerar bra på enhetligt distribuerade flytande punktdata, men Räkna Sort är begränsad till heltalsdomäner.

Genomföra en stabil greve Sort

Stabilitet är viktigt när du sorterar efter en nyckel samtidigt som du bevarar den relativa ordningen av lika element från en annan nyckel. Standarden Counting Sort algoritmen är i sig stabil när utgångsplaceringen passerar ingången från höger till vänster. Här är en textkontur av den stabila varianten:

  1. Beräkningsräkningsarray som beskrivits.
  2. Konvertera till prefixsummor (positioner av varje värde i den sorterade utgången).
  3. Sätt ingångsarrayen i omvänd ordning. För varje element, placera den på den position som anges av dess räkning, sedan dekret som räknas.

Eftersom vi behandlar element från slutet går den sista förekomsten av ett visst värde in i det högsta möjliga indexet, vilket bevarar relativ ordning. Denna stabila version är nödvändig för att Radix Sort ska fungera korrekt på varje siffra.

Praktiska tillämpningar

  • ]Educational grading systems: Sorting hundratals tentamen (range 0-100) i O(n) tid.
  • ]Bioinformatik: Sorteringsintegrationen läser räknas eller DNA-k-merfrekvenser när alfabetets storlek är liten (A, C, G, T).
  • ]]Database index underhåll: Sortering unika heltalsidentifierare i intervall liten nog för att passa i minnet.
  • Bildbehandling:] Sortering av histogrambiner eller färgintensiteter (0–255) vid byggande av sidobord.
  • Sorting by secondary key:[] Används inom Radix Sort, som är arbetshästen för effektiv sortering i många bibliotek och språk (t.ex. .NET runtime använder en adaptiv blandning av algoritmer inklusive Räkna Sort för små intervall).

För mer om teorin och varianterna, konsultera auktoritativa referenser som ]Wikipedia: Räkna Sort ] och ]]GeeksforGeeks: Räkna Sort ]. Praktiska jämförelser med andra algoritmer kan hittas i ]Brilliants Räkna Sort artikel ]]]]]]].

Optimera greveplats för stora ranges

När k är stor men n är också stor, blir ren greve Sort minnesintensiv. Flera optimeringar finns:

  • ] Tryckt gleshet: ] Använd en hashkarta istället för en sammanhängande array när utbudet av begagnade värden är stort men antalet distinkta värden är liten. Detta handlar konstant tid indexering för hashing overhead men minskar minnesförbrukningen.
  • ]Hybrid närmar sig: Kombinera räkna Sort med andra algoritmer. Om till exempel intervallet överstiger 106, använd Radix Sort med en bas som håller digit varierar liten.
  • På plats varianter: ] Vissa optimeringar minskar extra utrymme till O(k) utan en utgångsarray, men de offrar i allmänhet stabilitet eller kräver cykler för att lokalisera positioner.

Slutsats

Räkna Sort sticker ut som en anmärkningsvärt effektiv algoritm för sortering av heltal när värdeintervallet är lite relativ till antalet element. Dess O(n + k) tidskomplexitet och linjär prestanda gör det oumbärligt i scenarier som grad sortering, Radix Sort subroutines och applikationer med gränsade integernycklar. Men algoritmens beroende av integreringsinmatning och dess minnesöverhuvud för stora intervall påminner oss om att ingen enda sortering är optimal för alla situationer.