Laske lajittelu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 18. tammikuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 29 muokkausta .

Counting sort [1] ( eng. counting sort [2] ; lajittelu laskemalla [3] eng. sorting by counting [4] ) on lajittelualgoritmi, joka käyttää lajitellun taulukon ( lista ) numeroalueita vastaavien elementtien laskemiseen . Laskevan lajittelun käyttö on hyödyllistä vain silloin, kun lajitetuilla luvuilla on (tai voidaan yhdistää) mahdollisten arvojen alue, joka on tarpeeksi pieni verrattuna lajiteltuun joukkoon, esimerkiksi miljoona luonnollista lukua alle 1000.

Oletetaan, että syöttötaulukko koostuu kokonaisluvuista välillä - , jossa . Lisäksi algoritmi yleistetään mielivaltaiselle kokonaislukualueelle. Laskentalajittelussa on useita muunnelmia, alla on kolme lineaarista ja yksi neliö, joka käyttää erilaista lähestymistapaa, mutta jolla on sama nimi. $n$ $0$ $k-1$ $k \in \mathbb N$

Yksinkertainen algoritmi

Tämä on algoritmin yksinkertaisin versio. Luo aputaulukko C[0..k], joka koostuu nollista, ja lue sitten peräkkäin syötetaulukon elementit , kasvaen yhdellä Akutakin kohti . Nyt riittää, että käydään taulukon läpi , kirjoita jokaiselle taulukossa numero j kertaa peräkkäin. A[i]C[A[i]]C ${\displaystyle j\in \{0,...,k\))$ AC[j]

SimpleCountingSort: kun i = 0 - k C[i] = 0; kun i = 0 - n - 1 C[A[i]] = C[A[i]] + 1; b = 0; kun j = 0 - k kun i = 0 - C[j] - 1 A[b] = j; b = b + 1;

Toteutus C :ssä :

//array - osoitin taulukon alkuun //n - taulukon koko //k - taulukon enimmäismäärä void countingSort ( int * array , int n , int k ) { int * c = ( int * ) malloc (( k + 1 ) * koko ( * array )); memset ( c , 0 , koko ( * array ) * ( k + 1 )); for ( int i = 0 ; i < n ; ++ i ) { ++ c [ taulukko [ i ]]; } int b = 0 ; for ( int i = 0 ; i < k + 1 ; ++ i ){ for ( int j = 0 ; j < c [ i ]; ++ j ) { taulukko [ b ++ ] = i ; } } vapaa ( c ); }

Toteutus C++ :ssa :

#sisällytä <vektori> #include <type_traits> #include <algoritmi> malli < typename std :: enable_if_t < std :: is_integral_v < T > , T >> void countingSort ( std :: vektori < T >& array ) { T max = std :: max_element ( array .begin (), array .end ( ) ); automaattinen laskenta = std :: vektori < T > ( max + 1 , T ( 0 )); for ( T elem : array ) ++ c [ elem ]; Tb = 0 ; _ for ( koko_t i = 0 ; i < max + 1 ; ++ i ) { for ( T j = 0 ; j < count [ i ]; ++ j ) { taulukko [ b ++ ] = i ; } } }

Listaalgoritmi

Tätä muunnelmaa ( kyyhkynenreiän lajittelu, count sort ) käytetään, kun syöte on joukko tietorakenteita, jotka tulee lajitella avainten ( key) mukaan. Sinun on luotava aputaulukko C[0..k - 1], joka C[i]sisältää myöhemmin luettelon syöttötaulukon elementeistä. Lue sitten peräkkäin syöttötaulukon elementit ja lisää Ajokainen luetteloon . Lopuksi käy taulukon läpi ja kirjoita luettelon elementit peräkkäin jokaiselle taulukolle . Algoritmi on vakaa . A[i]C[A[i].key]C $j \in \{0, ..., k - 1\}$ AC[j]

ListCountingSort kun i = 0 - k - 1 C[i] = NULL; kun i = 0 - n - 1 C[A[i].avain].add(A[i]); b = 0; kun j = 0 - k - 1 p = C[j]; kun taas p != NULL A[b] = p.data; p = p.seuraava(); b = b + 1;

Vankka algoritmi

Tässä versiossa syöttötaulukon lisäksi Atarvitaan kaksi aputaulukkoa - C[0..k - 1]laskuria ja B[0..n - 1]lajiteltua taulukkoa varten. Täytä ensin matriisi Cnollalla ja jokaisella A[i]lisäyksellä C[A[i]]1. Seuraavaksi lasketaan elementtien määrä, joka on pienempi tai yhtä suuri kuin . Tätä varten kutakin , alkaen arvosta , suurennetaan . Siten viimeinen solu sisältää syöttötaulukossa olevien elementtien määrän välillä - . Algoritmin viimeisessä vaiheessa syöttötaulukko luetaan lopusta, arvoa pienennetään yhdellä ja . Algoritmi on vakaa. $k-1$ C[j]C[1]C[j - 1] $0$ $k-1$ C[A[i]]B[C[A[i]]]A[i]

StableCountingSort kun i = 0 - k - 1 C[i] = 0; kun i = 0 - n - 1 C[A[i]] = C[A[i]] + 1; kun j = 1 - k - 1 C[j] = C[j] + C[j-1]; kun i = n - 1 - 0 C[A[i]] = C[A[i]] - 1; B[C[A[i]]] = A[i];

Yleistys mielivaltaiseen kokonaislukualueeseen

Useita kysymyksiä herää. Entä jos arvoaluetta (min ja max) ei tiedetä etukäteen? Entä jos minimiarvo on suurempi kuin nolla tai lajitetussa datassa on negatiivisia lukuja? Ensimmäinen kysymys voidaan ratkaista lineaarisella haulla min ja max, mikä ei vaikuta algoritmin asymptotiikkaan. Toinen kysymys on hieman vaikeampi. Jos min on suurempi kuin nolla, vähennä min taulukosta, kun työskentelet taulukon kanssa, ja lisää min, kun kirjoitat takaisin C. A[i]Jos on negatiivisia lukuja, sinun on Clisättävä A[i]taulukkoon työskennellessäsi |min|ja vähennettävä, kun kirjoitat takaisin.

Analyysi

Kahdessa ensimmäisessä algoritmissa kaksi ensimmäistä silmukkaa toimivat ja vastaavasti; kaksinkertainen sykli . Kolmannessa algoritmissa syklit ottavat vastaavasti , , ja . Kaiken kaikkiaan kaikilla kolmella algoritmilla on lineaarinen aikakompleksisuus . Kahdessa ensimmäisessä algoritmissa käytetty muisti on , ja kolmannessa . $\Theta(k)$ $\Theta(n)$ $\Theta(n+k)$ $\Theta(k)$ $\Theta(n)$ $\Theta(k)$ $\Theta(n)$ $\Theta(n+k)$ $\Theta(k)$ $\Theta(n+k)$

Quadratic Counting Lajittelualgoritmi

Laskentalajittelua kutsutaan myös hieman erilaiseksi algoritmiksi. Se käyttää syöttötaulukkoa Aja aputaulukkoa Blajiteltuun joukkoon. Laske algoritmissa kullekin syötetaulukon A[i]elementille sitä pienempien alkioiden määrä ja sitä yhtä suurien, mutta aikaisempien elementtien lukumäärä ( ). antaa . Algoritmi on vakaa. $c_{1}$ $c_{2}$ $c = c_1 + c_2$ B[c]A[i]

SquareCountingSort kun i = 0 - n - 1 c = 0; kun j = 0 - i - 1 jos A[j] <= A[i] c = c + 1; kun j = i + 1 - n - 1 jos A[j] < A[i] c = c + 1; B[c] = A[i];

Analyysi

Ilmeisesti algoritmin aikaestimaatti on , muisti . $\Theta (n^{2})$ $\Theta(n)$

Toteutusesimerkkejä

Komponentti Pascal

Yksinkertainen algoritmi.

TOIMENPITEET CountingSort ( VAR a : JOHDON KOKONAISLUKU ; min , max : INTEGER ) ; _ VAR i , j , c : INTEGER ; b : KOHDISTIN KOKONAISLUKUJÄRJESTELMÄÄN ; _ _ _ BEGIN ASSERT ( min <= max ) ; UUSI ( b , max - min + 1 ) ; FOR i := 0 TO LEN ( a ) - 1 DO INC ( b [ a [ i ] - min ]) LOPPU ; i := 0 ; KOHTA j := min TO max DO c := b [ j - min ] ; WHILE C > 0 TEEE a [ i ] := j ; INC ( i ) ; DEC ( c ) END END END CountingSort ;

Toteutus PascalABC.Netissä

konst n = 20_ _ alkaa var a := ArrRandomInteger ( n , 0 , 100 ) ; a . Println ; var max := a . Max ; var c := | 0 | * ( max + 1 ) ; var i : = 0 - a . Pituus - 1 do c [ a [ i ]] += 1 ; var j := 0 ; var i : = 0 - max do var k : = 1 - c [ i ] do alkaa a [ j ] := i ; j += 1 ; loppu ; a . Println ; loppua .

Toteutus Pythonissa

a = lista ( map ( int , input () . split ())) # lue lista cnt = [ 0 ] * ( max ( a ) + 1 ) # luo nollaluettelo , jonka pituus on luettelon maksimielementti a kohteelle a : ssa : cnt [ item ] += 1 # kun kohtaamme numeron luettelossa, lisää sen arvoa yhdellä # lisää tulokseen count times num tulos = [ num for num , count in enumerate ( cnt ) for i in range ( count )] tulosta ( tulos ) # tulosta lajiteltu luettelo

Katso myös

Muistiinpanot

↑ Kormen. Laskennan lajittelu // Algoritmit: Alkukurssi. - Williams, 2014. - S. 71. - 208 s. — ISBN 978-5-8459-1868-0 .
↑ Cormen, Thomas H. ; Leiserson, Charles E .; Rivest, Ronald L. & Stein, Clifford (2001), 8.2 Counting Sort, Introduction to Algorithms (2. painos), MIT Press ja McGraw-Hill , s. 168–170, ISBN 0-262-03293-7 .
↑ Piiska. Lajittelu laskemalla // Ohjelmoinnin taito. - T. 3. - S. 77.
↑ Knuth, D.E. (1998), jakso 5.2, Lajittelu laskemalla, The Art of Computer Programming , Volume 3: Sorting and Searching (2. painos), Addison-Wesley, s. 75-80, ISBN 0-201-89685-0 .

Kirjallisuus

Levitin A. V. Luku 7. Avaruus-ajallinen kompromissi: Laskennan lajittelu // Algoritmit. Johdatus kehitykseen ja analyysiin - M . : Williams , 2006. - S. 331-339. — 576 s. — ISBN 978-5-8459-0987-9
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Luku 8 Lajittelu lineaarisessa ajassa // Algoritmit: Rakentaminen ja analyysi = Algoritmien johdatus. – 2. painos. - M . : "Williams" , 2005. - S. 224 - 226. - ISBN 5-8459-0857-4 .

Linkit

Visualizer1 on Java-sovelma.
Visualizer2 on Java-sovelma.

Lajittelualgoritmit
Teoria	Monimutkaisuus O merkintä Tilaussuhde Lajittele tyypit kestävää Sisäinen Ulkoinen
Vaihto	kupla Sekoitetaan Kääpiöt Nopeasti Kampa Lajittelu parillinen-pariton Bitittain
Valinta	Valinta Pyramidin muotoinen Sileä
insertit	insertit shella puu
fuusio	fuusio
Ei vertailuja	Laskenta lohko
hybridi	introsort Timsort
muu	Topologinen verkkoja bitonia
epäkäytännöllistä	Bogosort Stooge lajittelu pannukakku hidas