Глупи сорт

Глупи сорт

Намена неефикасно сортирање Временска компл. неограничена Средња ВК $O(n\cdot n!)$ Меморијска компл. $O(n)$ Стабилан не

Глупи сорт (енгл. bogosort, bogo-sort, stupid sort) је непрактичан алгоритам сортирања, који се углавном користи у едукативне сврхе, као контраст бржим алгоритмима. Овај алгоритам сортира низ елемената тако што случајно бира њихове размештаје док се не деси да низ буде сортиран. Ово чини да његова временска сложеност у најгорем случају буде бесконачна то јест да се овим случајним размештањем низ никада не сортира. Његова средња временска сложеност се процењује на O(n · n!) јер свака комбинација n елемената без понављања има шансу 1/n! да погоди сортирано стање (па отуда O(n!)), а између провера се врши комплетно мешање низа, што је у домену O(n).

Као илустрација може да послужи шпил карата. Уколико овај шпил мешамо, а између мешања проверавамо да ли је сортиран, онда поступамо по алгоритму глупог сорта.

Опис алгоритма

У псеудокоду, алгоритам глупог сортирања би се могао изразити на следећи начин:

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

Исти овај алгоритам се у Јави може написати овако:

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