Bogosort

Bogosort on arvutiteaduses (tuntud ka kui permutatsioon sorteerimine) sorteerimisalgoritm, mis on väga ebaefektiivne. Bogosort põhineb katse ja eksituse meetodil, genereerides niikaua elementide permutatsioone, kuni leiab ühe, milles elemendid on õiges järjekorras ehk sorteeritud. Sellel algoritmil ei ole praktilist kasu arvutiteaduses, küll aga kasutatakse seda sorteerimisalgoritmide õpetamisel.
Bogosordi nimetus tuleb ingliskeelsete sõnade "bogus" (eesti keeles lollus) ja "sort" (eesti keeles sorteerimine) kombineerimisel.
Sellest algoritmist on kaks versiooni: determinismlik versioon, kus käiakse läbi kõik permutatsioonid kuni käesolev permutatsioon on sorteeritud ja suvalisust kasutav versioon, kus pannakse elemendid suvalisse järjekorda kuni juhtub, et need on sorteeritud.
Piltlikult võib suvalisust kasutavat bogosorti kirjeldada järgmiselt: bogosort on kaartide sorteerimine nii, et sa viskad need põrandale laiali ja korjad kokku seni kuni juhtub, et kaardid on sorteeritud järjekorras.
Algoritmi kirjeldus.
Determinismlik bogosort.
Järgnev on determinismliku bogosordi kirjeldus kasutades pseudokoodi:
&lt;syntaxhighlight&gt;
Bogosort (elemendid) {
 käi läbi kõik elementide premutatsioonid {
 kui premutatsioon on sorteeritud siis lõpeta
&lt;/syntaxhighlight&gt;
Järgnev on ülemise pseudokoodi järgi loodud C# bogosordiprogramm:
using System.Linq;
//Lühike premutatsioonide leidmise kood, autor: Amy B https://stackoverflow.com/a/999182
public IEnumerable&lt;Element[]&gt; LeiaPremutatsioond (Element[] elemendid) {
 var element = elemendid.Take(1);
 var halvadElemendid = LeiaPremutatsioond(source.Skip(1));
 var headElemendid = halvadElemendid.Select(set =&gt; element.Concat(set));
 return headElemendid.Concat(halvadElemendid);
public Element[] Bogosort (Element[] elemendid) {
 //Itereeri kõik premutatsioonid
 foreach(var premutatsioon in LeiaPremutatsioond(elemendid)) {
 //Kas elemendid on sorteeritud?
 var onSorteeritud = true;
 for(int i = 0; i &lt; premutatsioon.Length - 1; i++) {
 var varasemElement = premutatsioon[i];
 var järgmineElement = premutatsioon[i + 1];
 //Kui leidub element nii, et see on suurem kui järgmine element siis ei ole premutatsioon sorteeritud
 if(varasemElement &gt; järgmineElement) {
 onSorteeritud = false;
 break;
 //Kas elemendid olid sorteeritud?
 if(onSorteeritud) return premutatsioon;
Suvalisust kasutav bogosort.
Järgnev on suvalisust kasutava bogosordi kirjeldus kasutades pseudokoodi:
&lt;syntaxhighlight&gt;
Bogosort (elemendid) {
 tee seni kuni mitte (OnSorteeritud(elemendid)) {
 Sega(elemendid)
&lt;/syntaxhighlight&gt;
Järgnev on näide, kus ülemise pseudokoodi pealt on loodud C# bogosordiprogramm:
//Kasutame Linq raamatukogust .OrderBy ja .ToArray meetodeid
using System.Linq;
//Element on siinkohal igasugune klass millel on defineeritud &gt; operaator, näiteks kui vahetada klass Element int vastu siis kood töötab
public Element[] Bogosort (Element[] elemendid) {
 while(true) {
 //Kas elemendid on sorteeritud?
 for(int i = 0; i &lt; elemendid.Length - 1; i++) {
 var varasemElement = elemendid[i];
 var järgmineElement = elemendid[i + 1];
 //Kui leidub element nii, et see on suurem kui järgmine element siis ei ole elemendid sorteeritud
 if(varasemElement &gt; järgmineElement) {
 //Elemendid ei ole sorteeritud niiet sega ära ja proovi uuesti
 var suvalisus = new Random();
 elemendid = elemendid.OrderBy(c =&gt; suvalisus.Next()).ToArray();
 continue;
 //Elemendid on sorteeritud seega lõpeta
 return elemendid;
Järgnev on näide, kus ülemine pseudokood on implementeeritud programmeerimiskeeles Python3:
//Kastuame random raamatukogust shuffle meetodit mis segab elemendid
from random import shuffle
def on_sorteeritud(elemendid) -&gt; bool:
 """Kas elemendid on sorteeritud?"""
 return all(elemendid[i] &lt;= elemendid[i + 1] for i in range(len(elemendid) - 1))
def bogosort(elemendid) -&gt; list:
 """Sega elemente seni kuni need on sorteeritud"""
 while not on_sorteeritud(elemendid):
 shuffle(elemendid)
 return elemendid
Jõudlus.
Determinismliku bogosordi parim ajaline keerukus on O(n), keskmine on O((n+1)!) ja halvim on O((n+1)!).
Suvalisust kasutava bogosordi parim ajaline keerukus on O(n), keskmine O(n*n!) ja halvim O(∞).
Suure ajalise keerukuse tõttu bogosorti praktikas ei kasutata, küll aga kasutatakse seda sorteerimisalgoritmide õpetamisel.
Kvantbogosort.
 Kvantbogosort on humoorne hüpoteetiline bogosordi edasiarendus. Oletades, et kehtib kvantmehaanika paljude maailmade interpretatsioon, pannakse elemendid suvalisse järjekorda kasutades kvantmehaanikat. Selle tulemusena tekib formula_1 paralleeluniversumit. Kõik universumid kus hulk ei ole sorteeritud hävitatakse. Seega jääb alles vaid universum, kus kvantbogosort sorteeris elemendid ühe segamise abil. Teoreetiliselt on kvantbogosoridi parim, halvim ja keskmine ajaline keerukus O(n).