Gróf rendezés

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. január 18-án felülvizsgált verziótól ; az ellenőrzések 29 szerkesztést igényelnek .

A Counting sort [1] ( eng. counting sort [2] ; rendezés számlálással [3] eng. sorting by counting [4] ) egy rendezési algoritmus , amely egy rendezett tömb ( lista ) számtartományát használja az egyező elemek megszámlálására . A számláló rendezés használata csak akkor hasznos, ha a rendezett számoknak olyan lehetséges értéktartománya van (vagy leképezhető), amely elég kicsi a rendezett halmazhoz képest, például millió természetes szám 1000-nél kisebb.

Tegyük fel, hogy a bemeneti tömb egész számokból áll a -tól -ig terjedő tartományban , ahol . Továbbá az algoritmust egy tetszőleges egész tartományra általánosítjuk. A számlálási rendezésnek számos módosítása létezik, az alábbiakban három lineáris és egy kvadratikus, amely más megközelítést használ, de ugyanaz a neve. $n$ $0$ $k-1$ $k \in \mathbb N$

Egy egyszerű algoritmus

Ez az algoritmus legegyszerűbb változata. Hozzon létre egy C[0..k]nullákból álló segédtömböt, majd olvassa be egymás után a bemeneti tömb elemeit, Amindegyikhez eggyel A[i]növelve C[A[i]]. Most elég végigmenni a tömbön C, mindegyik tömbbe egymás után írja be a j számot . $j\in \{0,...,k\}$ AC[j]

SimpleCountingSort: ha i = 0-tól k-ig C[i] = 0; ha i = 0 - n - 1 C[A[i]] = C[A[i]] + 1; b = 0; j = 0-tól k-ig ha i = 0 - C[j] - 1 A[b] = j; b = b + 1;

Megvalósítás C nyelven :

//tömb - mutató a tömb elejére //n - tömb mérete //k - maximális szám a tömbben void countingSort ( int * array , int n , int k ) { int * c = ( int * ) malloc (( k + 1 ) * sizeof ( * array )); memset ( c , 0 , sizeof ( * array ) * ( k + 1 )); for ( int i = 0 ; i < n ; ++ i ) { ++ c [ tömb [ i ]]; } int b = 0 ; for ( int i = 0 ; i < k + 1 ; ++ i ){ for ( int j = 0 ; j < c [ i ]; ++ j ) { tömb [ b ++ ] = i ; } } szabad ( c ); }

Megvalósítás C++ nyelven :

#include <vektor> #include <type_traits> #include <algoritmus> sablon < típusnév std :: enable_if_t < std :: is_integral_v < T > , T >> void countingSort ( std :: vektor < T >& array ) { T max = std :: max_element ( array .begin (), array .end ( ) ); auto count = std :: vektor < T > ( max + 1 , T ( 0 )); for ( T elem : tömb ) ++ c [ elem ]; Tb = 0 ; _ for ( méret_t i = 0 ; i < max + 1 ; ++ i ) { for ( T j = 0 ; j < count [ i ]; ++ j ) { tömb [ b ++ ] = i ; } } }

Lista algoritmus

Ezt a változatot ( galamblyuk rendezés, számlálás rendezés ) akkor használjuk, ha a bemenet adatszerkezetek tömbje, amelyeket kulcsok ( key) szerint kell rendezni. Létre kell hoznia egy segédtömböt C[0..k - 1], C[i]amely később mindegyik tartalmazni fogja a bemeneti tömb elemeinek listáját. Ezután sorban olvassa be a bemeneti tömb elemeit , és Amindegyiket A[i]hozzáadja a listához C[A[i].key]. Végezetül menjen végig a tömbön C, minden tömbhöz írja be egymás után a lista elemeit . Az algoritmus stabil . $j \in \{0, ..., k - 1\}$ AC[j]

ListCountingSort ha i = 0 - k - 1 C[i] = NULL; ha i = 0 - n - 1 C[A[i].key].add(A[i]); b = 0; j = 0 és k - 1 között p = C[j]; míg p != NULL A[b] = p.adatok; p = p.next(); b = b + 1;

Robusztus algoritmus

Ebben a változatban a bemeneti tömbön kívül Akét segédtömbre van szükség - C[0..k - 1]a számlálóhoz és B[0..n - 1]a rendezett tömbhöz. Először töltse fel a tömböt Cnullákkal, és minden egyes A[i]növelésnél C[A[i]]1-gyel. Ezután a -val kisebb vagy egyenlő elemek számát számolja a rendszer . Ehhez mindegyik , -tól kezdődően -val megnövelve . Így az utolsó cella a bemeneti tömbben lévő elemek számát tartalmazza majd . Az algoritmus utolsó lépésében a bemeneti tömb végétől beolvasásra kerül, az értéket 1-gyel csökkentjük, és . Az algoritmus stabil. $k-1$ C[j]C[1]C[j - 1] $0$ $k-1$ C[A[i]]B[C[A[i]]]A[i]

StableCountingSort ha i = 0 - k - 1 C[i] = 0; ha i = 0 - n - 1 C[A[i]] = C[A[i]] + 1; j = 1 és k - 1 között C[j] = C[j] + C[j-1]; ha i = n - 1-től 0-ig C[A[i]] = C[A[i]]-1; B[C[A[i]]] = A[i];

Általánosítás tetszőleges egész tartományra

Több kérdés is felmerül. Mi van, ha az értéktartomány (min és max) nem ismert előre? Mi van akkor, ha a minimális érték nagyobb nullánál, vagy negatív számok vannak a rendezett adatokban? Az első kérdés megoldható a min és max lineáris keresésével, ami nem befolyásolja az algoritmus aszimptotikáját. A második kérdés valamivel nehezebb. Ha a min nagyobb, mint nulla, akkor vonja ki a min értéket a tömbből, amikor a tömbbel dolgozik, és adja hozzá a min értéket, amikor visszaírja C. A[i]Ha vannak negatív számok, akkor hozzá kell Cadni A[i], ha tömböt használunk |min|, és ki kell vonni, ha visszaírunk.

Elemzés

Az elsõ két algoritmusban az elsõ két hurok a és -nek dolgozik ; dupla ciklus a . A harmadik algoritmusban a ciklusok rendre , , és . Összességében mindhárom algoritmus lineáris időbonyolultságú . Az első két algoritmusban használt memória , a harmadikban pedig . $\Theta(k)$ $\Theta(n)$ $\Theta(n+k)$ $\Theta(k)$ $\Theta(n)$ $\Theta(k)$ $\Theta(n)$ $\Theta(n+k)$ $\Theta(k)$ $\Theta(n+k)$

Másodfokú számláló rendezési algoritmus

A számláló rendezést kissé eltérő algoritmusnak is nevezik. Egy bemeneti tömböt Aés egy segédtömböt Bhasznál a rendezett halmazhoz. Az algoritmusban a bemeneti tömb minden eleméhez A[i]számolja meg a nála kisebb elemek számát és a vele megegyező, de korábban álló elemek számát ( ). hozzárendelni . Az algoritmus stabil. $c_{1}$ $c_{2}$ $c = c_1 + c_2$ B[c]A[i]

SquareCountingSort ha i = 0 - n - 1 c = 0; j = 0-tól i-1-ig ha A[j] <= A[i] c = c + 1; ha j = i + 1 - n - 1 ha A[j] < A[i] c = c + 1; B[c] = A[i];

Elemzés

Nyilvánvaló, hogy az algoritmus időbecslése: memória . $\Theta (n^{2})$ $\Theta(n)$

Megvalósítási példák

Component Pascal

Egyszerű algoritmus.

ELJÁRÁS CountingSort ( VAR a : ARRAY OF INTEGER ; min , max : INTEGER ) ; VAR i , j , c : INTEGER ; b : POINTER AZ EGÉSZ SZÁM TÖMBRE ; BEGIN ASSERT ( min <= max ) ; ÚJ ( b , max - min + 1 ) ; FOR i := 0 TO LEN ( a ) - 1 DO INC ( b [ a [ i ] - min ]) VÉGE ; i := 0 ; FOR j := min TO max DO c := b [ j - min ] ; WHILE c > 0 DO a [ i ] := j ; INC ( i ) ; DEC ( c ) END END END CountingSort ;

Megvalósítás PascalABC.Netben

const n = 20_ _ kezdődik var a := ArrRandomInteger ( n , 0 , 100 ) ; a . Println ; var max := a . Max ; var c := | 0 | * ( max + 1 ) ; a var i := 0 -tól a -ig . Hossz - 1 do c [ a [ i ]] += 1 ; var j := 0 ; var i : = 0 -tól max do for var k := 1 - c [ i ] do kezdődik a [ j ] := i ; j += 1 ; vége ; a . Println ; vége .

Megvalósítás Pythonban

a = lista ( map ( int , input () . split ())) # olvassa el a listát cnt = [ 0 ] * ( max ( a ) + 1 ) # nullákból álló listát generál a lista maximális elemének hosszával az a tételhez : _ cnt [ item ] += 1 # Ha egy számmal találkozunk a listában, növeljük az értékét 1-gyel # add count times num az eredményhez eredmény = [ num for num , count in enumerate ( cnt ) for i in range ( count )] print ( eredmény ) # kinyomtatja a rendezett listát

Lásd még

Jegyzetek

↑ Kormen. Számláló rendezés // Algoritmusok: Bevezető tanfolyam. - Williams, 2014. - S. 71. - 208 p. — ISBN 978-5-8459-1868-0 .
↑ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. és Stein, Clifford (2001), 8.2 Counting Sort, Introduction to Algorithms (2. kiadás), MIT Press és McGraw-Hill , p. 168–170, ISBN 0-262-03293-7 .
↑ Ostor. Rendezés számolással // A programozás művészete. - T. 3. - S. 77.
↑ Knuth, D.E. (1998), 5.2. szakasz, Sorting by counting, The Art of Computer Programming , 3. kötet: Sorting and Searching (2. kiadás), Addison-Wesley, p. 75-80, ISBN 0-201-89685-0 .

Irodalom

Levitin A. V. 7. fejezet Tér-időbeli kompromisszum: Számlálási rendezés // Algoritmusok. Bevezetés a fejlesztésbe és elemzésbe - M . : Williams , 2006. - S. 331-339. — 576 p. — ISBN 978-5-8459-0987-9
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. 8. fejezet Rendezés lineáris időben // Algoritmusok: Konstrukció és elemzés = Bevezetés az algoritmusokba. — 2. kiadás. - M . : "Williams" , 2005. - S. 224 - 226. - ISBN 5-8459-0857-4 .

Linkek

A Visualizer1 egy Java kisalkalmazás.
A Visualizer2 egy Java kisalkalmazás.

Rendezési algoritmusok
Elmélet	Bonyolultság O jelölés Rendelési viszony Típusok rendezése fenntartható Belső Külső
Csere	buborék Keverés Törpék Gyors Fésű Rendezés páros-páratlan Bitenként
Választás	Választás Piramis alakú Sima
Betétek	Betétek shella fa
egyesülés	egyesülés
Nincs összehasonlítás	Számolás Blokk
hibrid	introsort Timsort
Egyéb	Topológiai hálózatok biton
nem praktikus	Bogosort Stooge fajta palacsinta lassú