Glupi sort

Iz Vikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu
Glupi sort
Namena neefikasno sortiranje
Vremenska kompl. neograničena[1]
Srednja VK [1]
Memorijska kompl.
Stabilan ne

Glupi sort (engl. bogosort, bogo-sort, stupid sort)[1] je nepraktičan algoritam sortiranja, koji se uglavnom koristi u edukativne svrhe, kao kontrast bržim algoritmima. Ovaj algoritam sortira niz elemenata tako što slučajno bira njihove razmeštaje dok se ne desi da niz bude sortiran. Ovo čini da njegova vremenska složenost u najgorem slučaju bude beskonačna to jest da se ovim slučajnim razmeštanjem niz nikada ne sortira. Njegova srednja vremenska složenost se procenjuje na O(n · n!) jer svaka kombinacija n elemenata bez ponavljanja ima šansu 1/n! da pogodi sortirano stanje (pa otuda O(n!)), a između provera se vrši kompletno mešanje niza, što je u domenu O(n).[2]

Kao ilustracija može da posluži špil karata. Ukoliko ovaj špil mešamo, a između mešanja proveravamo da li je sortiran, onda postupamo po algoritmu glupog sorta.

Opis algoritma[uredi]

U pseudokodu, algoritam glupog sortiranja bi se mogao izraziti na sledeći način:

   док није сортиран(шпил):
       промешај(шпил)

Isti ovaj algoritam se u Javi može napisati ovako:

public void glupiSort(int[] n) {
  Random random = new Random();
 
  // Провера сортираности низа
  glavnaPetlja: do {
    for(int i = 0; i < n.length; i++) {
      // Уколико се дошло до краја низа, а није се наишло на
      // несортираност, главна петља се прекида. Низ је сортиран.
      if(i == n.length-1) {
        break glavnaPetlja;
      }

      // Уколико се наишло на два суседна а несортирана елемента,
      // прекинути проверу, и наставити са случајним распоређивањем.
      if(n[i] > n[i+1]) {
        break;
      }
    }
 
    // Прераспоређивање елемената низа. Сваки елемент низа замењује
    // место са случајно изабраним унутар интервала који још није
    // био измешан у овом пролазу.
    for(int i = n.length - 1; i > 0; i--) {
      int mestoSlucajnoIzabranog = random.nextInt(i + 1);
      int bafer = n[i];
      n[i] = n[mestoSlucajnoIzabranog];
      n[mestoSlucajnoIzabranog] = bafer;
    }
  } while(true);
}

Reference[uredi]

  1. 1,0 1,1 1,2 Gruber, H.; Holzer, M.; Ruepp, O., „Sorting the slow way: an analysis of perversely awful randomized sorting algorithms”, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007 (PDF), Lecture Notes in Computer Science, 4475, Springer-Verlag, str. 183—197, doi:10.1007/978-3-540-72914-3_17 .
  2. ^ Fun with Algorithms; Crescenzi, Prencipe, Pucci. ISBN 978-3-540-72913-6., pp. 191