Strukture podataka i algoritmi: Bin Sort

Strukture podataka i algoritmi

7.4 Bin Sort

Pretpostavimo

da se kljucevi objekata koje zelimo da sortiramo nalaze u malom fiksiranom opsegu i
da ne postoje dva objekta sa istom vrednoscu kljuca.

Tada mozemo da sortiramo pomocu sledece procedure:

Postavimo niz "kutija" - svaka za jednu vrednost kljuca - u red,
Proverimo svaki objekat i iskoristimo vrednost kljuca da objekat stavimo u odgovarajucu kutiju.

Sada je nas skup sortiran i za to je trebalo samo n operacija, tako da je ovo O(n) algoritam. Medjutim, primetimo da je njega moguce primeniti samo pod veoma ogranicenim uslovima.

Ogranicenja Bin Sort-a

Da bi razumeli ova ogranicenja, budimo malo precizniji sa specifikacijom problema i pretpostavimo da postoji m vrednosti kljuca. Za dobijanje sortiranog skupa, moramo da ispitamo svaku kutiju. Ovo dodaje treci korak u gornji algoritam,

Proverimo svaku kutiju da vidimo postoji li objekat u njoj,

koji zahteva m operacija. Tako vreme izvrsavanja algoritma postaje: T(n) = c₁n + c₂m i ono je, u stvari, O(n + m). Ako je m <= n, ovo je ocigledno O(n). Medjutim, ako je m >> n, tada je vreme jednako O(m).

Na primer, ako zelimo da sortiramo 10⁴ 32-bitnih celih brojeva, tada je m = 2³², pa nam je potrebno 2³² operacija (i veoma velika memorija!).
Za n = 10⁴:

nlogn ~ 10⁴ x 13 ~ 2¹³ x 2⁴ ~ 2¹⁷ Jasno je da bi u ovom slucaju Quick Sort i Heap Sort bili mnogo bolji izbor.

Implementacija Bin Sort-a bi mogla da izgleda ovako:

#define EMPTY	-1 /* Neka nekoriscena vrednost */
void bin_sort( int *a, int *bin, int n ) {
    int i;
    /* Pre-uslov: za 0<=i<n : 0 <= a[i] < M */
    /* Oznaci sve kutije kao prazne */
    for(i=0;i<M;i++) bin[i] = EMPTY;
    for(i=0;i<n;i++)
        bin[ a[i] ] = a[i];
    }

main() {
    int a[N], bin[M];    /* za sve i: 0 <= a[i] < M */
    .... /* Smesti objekte u niz a */
    bin_sort( a, bin, N );

Ako postoje objekti sa istim kljucevima, tada se svaka kutija moze zameniti sa povezanom listom. Treci korak tada postaje:

Povezimo sve liste u jednu listu.

Objekat mozemo da dodamo u povezanu listu u O(1) koraka. Postoji n objekata koji zahtevaju O(n) koraka. Povezivanje liste na drugu listu jednostavno znaci postavljanje repa jedne liste da pokazuje na drugu listu, pa je to O(1) operacija. Povezivanje m takvih listi ocigledno traje O(m) koraka, pa je algoritam jos uvek O(n+m).

Za razliku od drugih metoda za sortiranje, koji sortiraju u mestu i zahtevaju dodatnu memoriju, Bin Sort zahteva dodatnu memoriju za kutije i dobar je primer trampe prostora zbog performansi.

Iako memorija tezi da bude jeftina kod modernih racunara -
tako da bi memoriju mogli da koristimo veoma raskalasno da bi dobili na performansama,
memorija trosi energiju
i u nekim slucajevima, npr. racunara u kosmickim letelicama,
energija bi mogla da bude vaznija stavka od performansi.

Posto smo naglasili ovo ogranicenje, pokazimo verziju Bin Sort-a koja sortira u mestu:

#define EMPTY	-1 /* Neka nekoriscena vrednost */
void bin_sort( int *a, int n ) {
    int i;
    /* Pre-uslov: for 0<=i<n : 0 <= a[i] < n */
    for(i=0;i<n;i++)
	if ( a[i] != i )
            SWAP( a[i], a[a[i]] );
    }

Medjutim, ovde se pretpostavlja da postoji n razlicitih kljuceva u opsegu 0 .. n-1. Pored ovog ogranicenja, operacija zamene (swap) je relativno skupa, tako da ova verzija dobija na prostoru u zamenu za duze vreme izvrsavanja.

Strategija Bin Sort-a mozda izgleda prilicno ogranicena, ali se moze uopstiti u strategiju poznatu kao Radix sortiranje.

Animacija Bin Sort-a
Ovu animaciju je napisao Woi Ang.

Posaljite komentare na adresu
morris@ee.uwa.edu.au