Urejanje s štetjem

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsebina


Urejanje s štetjem (angl. count sort ali counting sort) je algoritem za urejanje podatkov, ki deluje v linearnem času O(n). Uporaben je za urejanje naravnih števil ali drugih podatkov, ki jih lahko neposredno preslikamo v naravna števila, na primer znakov. Ker delujejo najbolj učinkoviti splošni algoritmi za urejanje podatkov v času O(nlog(n)), je urejanje s štetjem v primerjavi z njimi zelo učinkovito.

Glavni slabosti algoritma sta omejena uporabnost in dejstvo, da porabi več prostora kot običajni algoritmi za urejanje, saj naredi pomožno tabelo.


Algoritem opišemo s psvedokodo, pri čemer uporabimo naslednje oznake:

  • A je začetna neurejena tabela
  • B je končna urejena tabela
  • k je največji element tabele A
  • C je dodatna tabela velikosti k+1
COUNTING SORT(A,B,k)
//najprej napolnimo dodatno tabelo C s samimi ničlami
for i = 0 to k do C[i] = 0 done
// Preštejemo frekvence elementov iz A in jih shranimo v C
for j = 0 to length[A] do C[A[j]] = C[A[j]] + 1 done
// Izračunamo kumulativne frekvence elementov
for i = 1 to k do C[i] = C[i] + C[i-1] done
// C[i] sedaj pomeni število elementov tabele A, ki so manjši ali enaki i
// V tabelo B prepišemo elemente A na prava mesta
for j = length[A] downto 0 do
  B[C[A[j]]] = A[j]
  C[A[j]] = C[A[j]] - 1
done

Zgled

Za lažje razumevanje algoritma si za začetek poglejmo konkreten primer.

  1. Na začetku imamo neurejeno tabelo celih števil.
    7 3 7 9 3 7 1 9
  2. Poiščemo največji element tabele. Skonstruiramo novo dodatno tabelo velikosti tega maksimalnega elementa + 1. V našem primeru je največji element prvotne tabele enak 9, zato je dodatna tabela velikosti 9 + 1 = 10. Pri tej dodatni tabeli označimo tudi indekse elementov v tabeli, začnemo jih šteti pri 0. Ti indeksi so pri urejanju s štetjem zelo pomembni. Vsem elementom dodatne tabele določimo začetno vrednost 0.
    0 0 0 0 0 0 0 0 0 0
    0 1 2 3 4 5 6 7 8 9
  3. Nato preštejemo koliko je posameznih števil začetne tabele. To lahko naredimo na več načinov. V našem primeru, ko imamo zelo kratko začetno tabelo števil, lahko že na oko vidimo, da imamo eno 1, dve 3, tri 7 ter dve 9. Zato ta števila, ki predstavljajo količino določenega števila, vnesemo v tabelo, in sicer na mesta z indeksom števila, ki smo ga prešteli. Torej, ker imamo tri sedmice, bomo vnesli število 3 na mesto tabele z indeksom 7,... Zadeve pa seveda lotimo drugače, ko imamo večjo tabelo. Za vsako število začetne tabele, povečamo vrednost dodatne tabele za 1 na mestu z indeksom tega števila. Ko se sprehodimo čez celo začetno tabelo, dobimo isti rezultat kot v prvem primeru reševanja in sicer dodatna tabela po tem postopku izgleda takole:
    0 1 0 2 0 0 0 3 0 2
    0 1 2 3 4 5 6 7 8 9
  4. Sedaj se lotimo preurejanja te dodatne tabele, in sicer tako, da i-temu elementu dodatne tabele dodamo vrednost i-1. (torej predhodnega) elementa. Z ničtim elementom nič ne naredimo, potem pa prvemu elementu dodamo vrednost ničtega, drugemu vrednost prvega (vendar POZOR, upoštevati moramo, da je vrednost prvega elementa že spremenjena, torej dodamo drugemu elementu že novo (spremenjeno) vrednost prvega) ,... Na koncu po tem preurejanju dobimo spodnjo tabelo. V tej tabeli se na i-tem mestu nahaja število, ki nam pove, koliko je takih elementov začetne tabele, ki so manjši ali enaki i.
    0 1 1 3 3 3 3 6 6 8
    0 1 2 3 4 5 6 7 8 9
  5. Sedaj ustvarimo še eno tabelo (končno tabelo velikosti začetne tabele), ki bo na začetku še prazna, kasneje pa bodo v njej urejeni vsi elementi začetne tabele po vrsti. Prepišimo še enkrat začetno tabelo in preurejeno dodatno tabelo in prazno končno tabelo. Indeksi končne tabele gredo od 1 naprej. Nato se lotimo postopka. Vzamemo zadnji element začetne tabele (v našem primeru je to 9). V dodatni tabeli pogledamo kateri element leži na mestu z indeksom številka 9. Vidimo, da je to 8, zato na 8.mesto v končni tabeli postavimo element 9. Nato pa še element 8 iz dodatne tabele zmanjšamo za 1. To pomeni, da je v dodatni tabeli sedaj na mestu z indeksom 9 namesto 8 število 7. In če bi imeli še kak element 9 v začetni tabeli, bi ta šel na mesto 7 končne tabele, število 7 v dodatni tabeli pa bi se zmanjšalo za 1 in bi tam na mestu z indeksom 9 imeli število 6.
    Začetna tabela
    7 3 7 9 3 7 1 9
    Dodatna tabela
    0 1 1 3 3 3 3 6 6 8
    0 1 2 3 4 5 6 7 8 9
    Končna tabela
    9
    1 2 3 4 5 6 7 8
  6. Ko smo število 9 že vstavili v končno tabelo, ga v začetni več ni, zato ga lahko prečrtamo in vzamemo naslednji element (ki je spet zadnji v začetni tabeli). Celoten postopek ponovimo na vseh preostalih elementih začetne tabele. Tako dobimo v končni tabeli urejene elemente po naraščajočem vrstnem redu in s tem smo prišli do konca algoritma.
    1 3 3 4 7 7 9 9
    1 2 3 4 5 6 7 8

    Dodatna tabela pa ob koncu algoritma izgleda takole:

    0 0 1 1 3 3 3 3 6 6
    0 1 2 3 4 5 6 7 8 9

Opomba

Pri hitrem razmisleku bi se vsak vprašal, zakaj pa sploh potrebujemo preurejeno dodatno tabelo (točka 4 v zgledu zgoraj), ko pa lahko program napišemo enostavneje brez nje oziroma z uporabo nepreurejene dodatne tabele (točka 3 v zgledu zgoraj):

 
    indexKoncna = 0;
    for(int i = 0; i<= zacetna_maxElement; i++){
       for(int j = 1; j<= dodatna[i]; j++){
          koncna[indexKoncna] = i;
          indexKoncna++;
       }
    }

Takole gremo po zankah tega algoritma, če vzamemo začetno tabelo isto kot v zgledu zgoraj.

   i=0....j=1;j<=0....ne storimo nič
   i=1....j=1;j<=1....koncna[0] = 1;
   i=2....j=1;j<=0....ne storimo nič
   i=3....j=1;j<=2....koncna[1] = 3, koncna[2] = 3
   i=4....j=1;j<=0....ne storimo nič
   i=5....j=1;j<=0....ne storimo nič
   i=6....j=1;j<=0....ne storimo nič
   i=7....j=1;j<=3....koncna[3] = 7, koncna[4] = 7, koncna[5] = 7
   i=8....j=1;j<=0....ne storimo nič
   i=9....j=1;j<=2....koncna[6] = 9, koncna[7] = 9

Opazimo, da gredo pri tem algoritmu indeksi končne tabele lahko od 0 naprej (in ne od 1 kot pri pravem Count Sortu).

Na koncu seveda dobimo naslednji vrstni red elementov 1 3 3 7 7 7 9 9 . Seveda je rezultat pravilen, vendar ta algoritem ni stabilen, to pa pomeni, da relativni vrstni red elementov (z enakimi vrednostmi) ni enak kot v začetni tabeli. Poleg tega tukaj v končno tabelo vstavljamo kar števila i (indeksi dodatne tabele), torej števila, ki gredo od 0 pa do maximalnega elementa začetne tabele. Ta števila so sicer enaka številom začetne tabele, vendar pa niso ista, so nekakšna njihova kopija. Vendar pa vsa ta števila navadno sploh ne pridejo v poštev, saj ni nujno da začetna tabela vsebuje vsa števila od 0 pa do njenega maximalnega elementa. Če so "luknje" v začetni tabeli, gremo v for zanki po nepotrebnem tudi čez neobstoječa števila (s tem se časovna zahtevnost poveča). Pojavi pa se tudi problem, če želimo urejati tabelo kakih drugih primitivnih tipov ali pa objektov. Ker v tem spremenjenem algoritmu vstavljamo v bistvu kar indekse dodatne tabele v končno tabelo, nam to v primeru, ko želimo urediti druge objekte po nekem ključu, nič ne pomaga pri urejanju le-teh, saj moramo končno tabelo napolniti s temi objekti in ne s ključi.

Za primer vzemimo, da želimo urediti tabelo objektov, med katerimi je vsak sestavljen iz enega celega števila (Integer) in enega znaka (Character). Urediti jih želimo po vrsti glede na naravna števila, ki so v tem primeru naš ključ. Spremenjen algoritem nam v dodatni tabeli le prešteje koliko je posameznih ključev, vendar nam to pri končni urejeni tabeli ne pomaga prav dosti, saj jo moramo napolniti z objekti (naravno število + znak) in ne le s ključi (naravnimi števili).

Zato raje uporabimo pravi algoritem Count Sort, saj v končno tabelo vstavlja konkretne in prave elemente (objekte) začetne tabele, preurejena dodatna tabela pa mu omogoča stabilnost in pa da elemente, ki ne nastopajo v začetni tabeli kar preskoči in jih tako ne obravnava pri urejanju.

Takole pa zgleda pravi algoritem Counting Sort, če želimo urejati tudi druge objekte (ne le naravna števila) po nekem ključu:

     COUNTING SORT(A,B,k)
	  //najprej napolnimo dodatno tabelo C s samimi ničlami
	  for i = 0 to k do C[i] = 0 done
	  // Preštejemo frekvence elementov iz A in jih shranimo v C
	  for j = 0 to length[A] do C[A[j].kljuc] = C[A[j].kljuc] + 1 done
	  // Izračunamo kumulativne frekvence elementov
	  for i = 1 to k do C[i] = C[i] + C[i-1] done
	  // C[i] sedaj pomeni število elementov tabele A, ki so manjši ali enaki i
	  // V tabelo B prepišemo elemente A na prava mesta
	  for j = length[A] downto 0 do
	    B[C[A[j].kljuc]] = A[j]
	    C[A[j].kljuc] = C[A[j].kljuc] - 1
     done
    

Implementacija

Glej tudi

Viri in literatura

Osebna orodja