Изворни код странице Глупи сорт

{{Алгоритам
| намена=неефикасно сортирање
| вкомплексност=''неограничена''<ref name="gruberetal" />
| средња вк=<math>O(n \cdot n!)</math><ref name="gruberetal" />
| мкомплексност=<math>O(n)</math>
| стабилан=не
}}

'''Глупи сорт''' ({{јез-енг|bogosort, bogo-sort, stupid sort}})<ref name="gruberetal">{{citation
 | last = Gruber | first = H.
 | last2 = Holzer | first2 = M.
 | last3 = Ruepp | first3 = O.
 | contribution = Sorting the slow way: an analysis of perversely awful randomized sorting algorithms
 | doi = 10.1007/978-3-540-72914-3_17
 | pages = 183–197
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007
 | url = http://www.hermann-gruber.com/pdf/fun07-final.pdf
 | volume = 4475}}</ref> је непрактичан [[алгоритам]] [[сортирање|сортирања]], који се углавном користи у [[образовање|едукативне]] сврхе, као контраст бржим алгоритмима. Овај алгоритам сортира низ елемената тако што случајно бира њихове размештаје док се не деси да низ буде сортиран. Ово чини да његова временска сложеност у најгорем случају буде [[бесконачност|бесконачна]] то јест да се овим случајним размештањем низ никада не сортира. Његова средња временска сложеност се процењује на ''-{O(n · n!)}-'' јер свака комбинација ''-{n}-'' елемената без понављања има шансу ''-{1/n!}-'' да погоди сортирано стање (па отуда ''-{O(n!)}-''), а између провера се врши комплетно мешање низа, што је у домену ''-{O(n)}-''.<ref>-{''Fun with Algorithms''; Crescenzi, Prencipe, Pucci. {{ISBN|978-3-540-72913-6}}.}-, pp. 191</ref>

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

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

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

Исти овај алгоритам се у [[Јава (програмски језик)|Јави]] може написати овако:

<source lang="java">
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);
}
</source>

== Референце ==
{{reflist}}

{{клица-информатика}}

{{нормативна контрола}}

[[Категорија:Алгоритми сортирања]]