Glupi sort

Glupi sort

Namena neefikasno sortiranje Vremenska kompl. neograničena Srednja VK $O(n\cdot n!)$ Memorijska kompl. $O(n)$ Stabilan ne

Glupi sort (engl. bogosort, bogo-sort, stupid sort) 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).

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

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);
}