Smutsort

Smutsort

Namena Algoritam za sortiranje Struktura podataka niz Vremenska kompl. O(nlogn) Srednja VK O(nlogn) Memorijska kompl. O(n)

Smutsort (engl. Smoothsort - glatko sortiranje) je algoritam za sortiranje koji je zasnovan na poređenju elemenata. To je oblik hipsorta koji je razvio Edsger Dijkstra

Kao i hipsort, glatki sort je složenosti O(nlogn). Prednost smutsorta je što je bliži složenosti O(n) ako je ulaz do neke mere već sortiran, a hipsort je prosečne složenosti O(nlogn) bez obzira na to koliko je ulaz sortiran.

Pregled

Kao i hipsort, smutsort gradi strukturu podataka koja se naziva hip za niz koji treba da se sortira, zatim sortira niz stalnim vađenjem najvećeg elementa iz hipa. Za razliku od hipsorta, smutsort ne koristi binarni hip, već onaj koji je zasnovan na Leonardovim brojevima.

Struktura hip se sastoji od niza u kome su svi članovi veličine Leonardovih brojeva i čiji su koreni u rastućem redosledu. Prednost ovakvog hipa u odnosu na binarni je, ako je niz već sortiran, onda je složenost konstruisanja i dekonstruisanja hipa O(n). Razbijanje ulaza u niz je jednostavno-krajnje levi član se postavlja u mogući hip i ostatak je takođe podeljen. Može se dokazati da:

1. Bilo koji niz, bilo koje dužine može biti podeljen u delove veličine L(x).
2. Nikoja dva hipa neće imati istu veličinu, zbog toga će niz biti strogo niz hipova opadajuće veličine.
3. Nikoja dva hipa neće biti veličine dva uzastopna Leonardova broja, osim možda poslednja dva.

Svaki hip koji je veličine L(x) je građen s leva na desno kao sub-hip veličine L(x-2) i koren. Izuzeci su hipovi veličine L(1) i L(0) koji imaju po jedan čvor. Svaki hip održava svojstvo da je koren uvek veći ili jednak od sinova. Posledica ovoga je da je čvor koji je na desnom kraju niza uvek najveći od svih i, što je važno, da niz koji je već sortiran ne mora ponovo da se sortira. Ovo je razlog dobre složenosti algoritma.

Algoritam je jednostavan. Počinje se tako što se nesortirani niz deli na hipove od jednog elementa. Niz od jednog elementa je trivijalan hip. Ovaj niz raste tako sto se sa desne strane dodaje po jedan element i ujedno se vrši zamena mesta elemenata ukoliko nije zadovoljeno svojstvo hipa sve dok se ne popuni niz.

Od ovog tenutka element na desnom kraju niza biće najveći i biće na svom mestu. Zatim smanjujemo serije hipa nazad do jednog elementa uklanjajući čvor koji je na desnom kraju i praveći novi raspored kako bi se održao uslov hipa. Kada smo stigli do poslednjeg hipa, niz je sortiran.

Operacije

Operacije koje su neophodne su povećanje niza dodavanjem jednog elementa sa desne strane i smanjenje niza uklanjanjem desnog elementa (korena poslednjeg hipa) čuvajući uslove hipa i niza.

Uvećavanje niza dodavanjem elementa zdesna

1. Ako su poslednja dva hipa veličine L(x+1) i L(x), novi element postaje koren većeg hipa veličine L(x+2); ovaj hip ne mora nužno imati svojstva hipa.
2. Ako poslednja dva hipa nisu uzastopni Leonardovi brojevi, onda element koji je na desnom kraju postaje novi hip veličine 1,ova 1 je uzeta iz L(1), osim ako je hip na desnom kraju veličine L(1), onda je novi element hipa veličine L(0).

Posle ovoga, svojstva hipa i niza moraju da se vrate što se uglavnom radi sortiranjem umetanjem. To se radi na ovaj način:

1. Hip na desnom kraju (koji je upravo kreiran) postaje trenutni hip
2. Dok postoji hip sa leve strane trenutnog hipa i njegov koren je veći od trenutnog korena i oba njegova sina onda se zamene novi koren i koren hipa sa leve strane; ovakav hip postaje trenutni
3. Izvršava se "filtriranje" na trenutnim hipu dok se ne utvrdi svojstvo hipa

Dok je trenutni hip veći od 1 ili sin tretnutnog hipa ima veci koren od korena trenutnog hipa: menja se veći sin sa trenutnim korenom, taj sin postaje trenutni hip. Filtriranje je uveliko pojednostavljeno korišćenjem Leonardovih brojeva tako što će hip imati ili jedan čvor ili dva sina. Ne mora se voditi računa da li postoje oba sina.

Smanjenje niza uklanjanjem desnog hipa

Ako je desni hip veličine 1 (npr. L(1), L(0)), onda ne treba nisšta da se radi. Samo se ukloni taj hip. Ako desni hip nije veličine 1, onda se uklanja koren i vraća se svojstvo niza, prvo levog pa desnog.

Iskorišćenost memorije

Smutsort mora da čuva u memoriji sve hipove u nizu. S obzirom da su sve ove vrednosti različite, ovo se postiže korišćenjem bitskih vektora.

Java implementacija

// odrzavanjem ovih konstanti, izbegava se zamoran posao
 // cuvanja Dijkstrinih a i b. Umesto njih, indekse cuvamo
 // u ovom nizu.

 static final int LP[] = { 1, 1, 3, 5, 9, 15, 25, 41, 67, 109,
     177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,
     35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457,
     1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703,
     48315633, 78176337, 126491971, 204668309, 331160281, 535828591,
     866988873 // the next number is > 31 bits.
 };

 public static <C extends Comparable<? super C>> void sort(C[] m,
     int lo, int hi) {
   int head = lo; // the offset of the first element of the prefix into m

   // Ove promenljive zahtevaju malo objasnjenja. Ako je niz hipova velicine
   // 38, onda ce hip biti velicine 25+9+3+1, sto su Leonardovi brojevi
   // 6, 4, 2, 1. 
   // Pretvaranjem ovih u binarne brojeve, dobija se b01010110 = 0x56. Predstavljamo
   // ove brojeve kao par brojeva desno popunjenim nulama i 
   // skladistenjem mantise i eksponenta kao "p" i "pshift".
   // Ovo je zgodno, jer eskponent indeks  L[] daje velicinu desnog hipa
   // i zato sto se odmah moze znati da li su poslednja dva hipa uzastopni Leonardovi
   // brojevi proveravanjem (p&3)==3
    

   int p = 1;
   int pshift = 1;

   while (head < hi) {
     if ((p & 3) == 3) {
       sift(m, pshift, head);
       p >>>= 2;
       pshift += 2;
     } else {
      
       if (LP[pshift - 1] >= hi - head) {
        
         trinkle(m, p, pshift, head, false);
       } else {
        
         sift(m, pshift, head);
       }

       if (pshift == 1) {
         
         p <<= 1;
         pshift--;
       } else {
        
         p <<= (pshift - 1);
         pshift = 1;
       }
     }
     p |= 1;
     head++;
   }

   trinkle(m, p, pshift, head, false);

   while (pshift != 1 || p != 1) {
     if (pshift <= 1) {
     
       int trail = Integer.numberOfTrailingZeros(p & ~1);
       p >>>= trail;
       pshift += trail;
     } else {
       p <<= 2;
       p ^= 7;
       pshift -= 2;

       // Ovaj blok se razbija na binarno drvo. Bit na desnom kraju
       // je blok suzine 1. Levi deo je podeljen na dva: blok duzine LP[pshift+1]
       // i LP[shift].
       

       trinkle(m, p >>> 1, pshift + 1, head - LP[pshift] - 1, true);
       trinkle(m, p, pshift, head - 1, true);
     }

     head--;
   }
 }

 private static <C extends Comparable<? super C>> void sift(C[] m, int pshift,
     int head) {
   
   C val = m[head];

   while (pshift > 1) {
     int rt = head - 1;
     int lf = head - 1 - LP[pshift - 2];

     if (val.compareTo(m[lf]) >= 0 && val.compareTo(m[rt]) >= 0)
       break;
     if (m[lf].compareTo(m[rt]) >= 0) {
       m[head] = m[lf];
       head = lf;
       pshift -= 1;
     } else {
       m[head] = m[rt];
       head = rt;
       pshift -= 2;
     }
   }

   m[head] = val;
 }

 private static <C extends Comparable<? super C>> void trinkle(C[] m, int p,
     int pshift, int head, boolean isTrusty) {

   C val = m[head];

   while (p != 1) {
     int stepson = head - LP[pshift];

     if (m[stepson].compareTo(val) <= 0)
       break; // current node is greater than head. Sift.

    
     if (!isTrusty && pshift > 1) {
       int rt = head - 1;
       int lf = head - 1 - LP[pshift - 2];
       if (m[rt].compareTo(m[stepson]) >= 0
           || m[lf].compareTo(m[stepson]) >= 0)
         break;
     }

     m[head] = m[stepson];

     head = stepson;
     int trail = Integer.numberOfTrailingZeros(p & ~1);
     p >>>= trail;
     pshift += trail;
     isTrusty = false;
   }

   if (!isTrusty) {
     m[head] = val;
     sift(m, pshift, head);
   }
 }