Mali, manji, najmanji...

Postoji mnogo načina da se niz podataka uredi, od najelementarnijih do veoma kompleksnih metoda. Izbor metode, odnosno algoritma, zavisi od procene "početnih uslova": ako se sortira kratak niz podataka, lakše je izabrati elementarni metod koji ćete lako implementirati. Međutim, ako se sortiranje ponavlja veliki broj puta ili se radi o ogromnim nizovima, brzina postaje jako bitan, čak odlučujući faktor.

Efikasnost nekih algoritama zavisi od početne "sortiranosti" elemenata: algoritam koji je najbolji kada su brojevi nasumično raspoređeni može da se pokaže veoma sporim ako su brojevi već gotovo sortirani, a važi i obrnuto. Zbog toga ćemo pri predstavljanju metoda sortiranja njihovu efikasnost pratiti sa tri aspekta: nad slučajno generisanim nizom elemenata, nad potpuno sortiranim i nad "inverzno" sortiranim nizom elemenata, pri čemu je ovaj poslednji redosled "noćna mora" mnogih algoritama.

Takođe, značajan podatak je i količina dodatne memorije, neophodna za pojedine metode sortiranja. Ovde je moguće izdvojiti tri slučaja. U prvom, sortiranje se odvija na "licu mesta", odnosno dodatna memorija je neophodna za neki vrlo mali stek ili tabelu. Drugi slučaj je karakterističan za algoritme koji koriste povezanu listu, pa im je, shodno tome, potrebna memorija za još N (broj elemenata koji se sortiraju) pointera, a treći, memorijski najzahtevniji, za algoritme kojima je neophodna kompletna kopija niza elemenata koji se sortiraju.

Poslednja karakteristika je stabilnost, tj. mogućnost očuvanja relativnog poretka elemenata pri sortiranju. Recimo da treba prikazati spisak finalistkinja za Mis sveta, pri čemu je početni redosled formiran po abecedi. Ako postoji više podjednako lepih devojaka (čitati: sa istim brojem poena), stabilno sortiranje će, kao prvu, na spisak postaviti lepoticu čije ime počinje slovom A, B ili C.

Često se javlja i potreba za sortiranjem slogova u okviru velikih datoteka. Slogovi, pored ostalih podataka, imaju i ključeve - podatke na osnovu kojih se vrši pristup, pa i sortiranje. U bazi podataka o studentima, ključevi za sortiranje mogu biti brojevi indeksa. Pošto se i sortira po ključevima koji su najčešće alfanumerički podaci, algoritmi će biti predstavljeni generalizovano, na primeru nizova celih brojeva.

Metoda selekcije

Jedan od najjednostavnijih algoritama je sortiranje metodom selekcije (selection sort). Treba pronaći najmanji element i zameniti ga sa elementom na prvoj poziciji, zatim pronaći sledeći najmanji element i zameniti ga sa drugim itd. Program je dat na slici 1: a[i] je niz celih brojeva, a n predstavlja broj elemenata niza. Ovaj metod je pogodan za datoteke sa manjim brojem jako velikih zapisa, pošto se svaki slog premešta najviše jednom.

Ne upuštajući se u matematičko dokazivanje postavljene teoreme, navedimo da se metodom selekcije, u prosečnom slučaju, izvrši oko n2/2 poređenja i n zamena. Na vreme izvršavanja utiče samo broj promene vrednosti indeksa min - u većini slučajeva reč je o O(n*log(n)) zavisnosti, pa se može smatrati da je metod spor, ali uglavnom "neosetljiv" na redosled ulaznih podataka.

Metoda umetanja

Za nijansu komplikovanija, metoda umetanja (insertion sort) je već pomenuta kao efikasno oružje strastvenih kartaroša. Svaka "karta" se posebno posmatra i umeće na mesto među već sortirane (npr. žandar između desetke i dame, kralj posle dame itd), sve dok se sve karte ne srede. Element se umeće na taj način što se svi veći pomeraju za jednu poziciju udesno. Postupak je prikazan na slici 2, a odgovarajući kod na slici 3.

Pri sortiranju elemenata ovom metodom izvrši se prosečno n2/4 poređenja i n2/8 zamena, a u najgorem slučaju duplo više. Metod umetanja je efikasan ako se sortira već uglavnom sortiran niz (tada teži linearnom), pošto broj poređenja i zamena zavisi od strukture ulaznih podataka.

Metoda mehurića

Bubble sort je kombinacija prethodna dva metoda, a izgleda ovako: polazi se od prvog elementa i ide, redom, do kraja niza. Svaki element se poredi sa prvim i ako je veći od njega, dalje poređenje se vrši sa novim elementom. U prvom prolazu se, dakle, pronalazi najveći element koji će se na kraju prolaza naći na poslednjem mestu u nizu. U sledećem prolazu se opet kreće od prvog elementa, ali se završava sa pretposlednjim. Za razliku od metode selekcije gde se niz sortira "sleva", odnosno prvo se sortiraju najmanji elementi, kod bubble sorta prvo se sortiraju najveći (slika 4).

I u prosečnom i u najlošijem slučaju, broj poređenja je reda n2/2, kao i broj zamena. I ova metoda je efikasna ukoliko su podaci već sortirani: tada je potreban samo jedan prolaz kroz niz.

Shell sortiranje

Ovo je poboljšana verzija Bubble algoritma. Bubble sortiranje je sporo kada mu "podmetnete" niz inverzno sortiranih elemenata, odnosno kada se najmanji element nalazi na kraju niza - pošto se razmenjuju samo susedni elementi, biće potrebno mnogo zamena da on dođe na početak. Shell sortiranje dozvoljava zamenu međusobno udaljenih elemenata, a bazira se na ideji da se podaci preurede na takav način da, počevši od bilo kog elementa, uzimanje svakog h-tog dovodi do sortiranog niza. Ovakav niz se naziva h-sortiranim, a postepeno smanjujući vrednost h, dolazi se do potpuno sortiranog niza. Postupak je prikazan na slici 5, a kod je dat na listingu 6.

Analiza performasi ovog metoda nije jednostavna, jer vrednosti h i vrednosti za koju se ona umanjuje pri svakom prolazu nisu striktno utvrđene. Štaviše, efikasnost zavisi od izbora ovih vrednosti (npr. može se početi sa h = n i u svakom prolazu umanjivati h za 2/3h), ali je prilično neosetljiva na početnu sortiranost elemenata. Pokazalo se da je ovo metod koji se u opštem slučaju može preporučiti - upoznaćemo i kompleksnije metode koji daju bolje rezlutate, ali njihova implementacija nije ovako jednostavna.

Metoda brojanja raspodele

Za kraj, predstavimo zgodan algoritam koji efikasno rešava konkretan problem sortiranja niza od ukupno n brojeva, koga čine celi brojevi iz opsega [0, m-1]. Ako su m i n jednaki, a na raspolaganju je dovoljna memorija, rešenje je vrlo jednostavno:

for( i = 0; i = n; i++ )
   b[a[i] = a[i];

Algoritam se zasniva na pronalaženju broja elemenata koji imaju istu vrednost. Formira se niz Count od m elemenata (slika 7). i-ti član predstavlja broj elemenata originalnog niza koji su manji ili jednaki od vrednosti i. Ako se vrednost 0 u originalnom nizu podataka pojavljuje tri, a vrednost 1 šest puta, Count[0] će imati vrednost 3 a Count[1] vrednost 3 + 6 = 9. Niz Count služi kao kontrola mesta umetanja odgovarajućeg elementa u novi niz b i to na sledeći način: kada se naiđe na vrednost 0, ona će biti smeštena na mesto Count[0] - 1 (oduzima se jedan jer indeksi niza počinju od nule), a sama vrednost Count[0] biće dekrementirana, da bi se sledeća nula smestila na mesto 1 u novom nizu b. Postupak se ponavlja za svaki element niza koji se sortira, uz dekrementiranje odgovarajuće Count vrednosti.

Ovaj metod, sa odgovarajućim proširenjem, predstavljaće osnovu za kompleksniji algoritam kojim ćemo se baviti u sledećim nastavcima. Takođe, ovaj put su elementarne metode samo predstavljene, a poređenje njihove efikasnosti je dato samo u grubim crtama. Analiza rezultata, poređenje vremena izvršavanja algoritama sortiranja u različitim uslovima i priča o kompleksnijim metodama nas očekuju u jednom od sledećih brojeva "PC"-ja...

Slika 1: Selection sort

SelectionSort (int n) {
   int i, j, Min;
   for (i = 0; i  n; i++) {
      Min = i;
      for (j = i + 1; j  n; j++) 
         if (a[Min] > a[j]) 
            Min = j;
         j = a[Min];
         a[Min] = a[i];
         a[i] = j; }
}

Slika 3: Insertion sort

InsertionSort (int n) {
   int i, j, b;
   for (i = 0; i  n; i++) {
       b = a[i];
       for (j = i; j  > 0; j--) 
           if (a[j-1] > b) 
              a[j] = a[j-1];
           else
              break;
       a[j] = b; }
}

Slika 4: Bubble sort

BubbleSort (int n) {
   int i, j, b;
   for (i = n - 1; i > 0; i--) {
      for (j = 1; j  = i; j++) 
          if (a[j-1] > a[j]) {
             b = a[j-1];
             a[j-1] = a[j];
             a[j] = b; }
   }
}

Slika 6: Shell sort

ShellSort (int n) {
   int i, j, h, s, b;
   h =  (n + 1)  / 2;
   while (h) {
      j = n - h;
      do {
         s = 0;
         for (i = 0; i = j; i++) {
             if (a[i] > a[i+h]) {
                b = a[i];
                a[i] = a[i+h];
                a[i+h] = b;
                s = i; }
         }
         j = s - h;
      } while (s) ;
   h = h / 2; }  
}

Slika 7: Sort brojanjem

DistributionCounting (int n, int m) {
   int i, j;
   for (i = 0; i  m; i++) 
       Count[i] = 0;
   for (i = 0; i  n; i++) 
       Count[a[i]]++;
   for (i = 1; i  m; i++) 
       Count[i] = Count[i-1] + Count[i];
   for (i = n - 1; i >= 0; i--) {
       b[Count[a[i]]-1] = a[i];
       Count[a[i]]--; }
   for (i = 0; i  n; i++) 
       a[i] = b[i]; }

Prilozi:

pc025alg.zip (0,59 kB)

© 1995-2024 PC Press. Sva prava zadržana.