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:

Bogosort (elemendid) {
    käi läbi kõik elementide premutatsioonid {
        kui premutatsioon on sorteeritud siis lõpeta
        }
    }

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<Element[]> LeiaPremutatsioond (Element[] elemendid) {
    var element = elemendid.Take(1);
    var halvadElemendid = LeiaPremutatsioond(source.Skip(1));
    var headElemendid = halvadElemendid.Select(set => 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 < 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 > 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:

Bogosort (elemendid) {
    tee seni kuni mitte (OnSorteeritud(elemendid)) {
        Sega(elemendid)
        }
    }

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 > 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 < 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 > järgmineElement) {
                //Elemendid ei ole sorteeritud niiet sega ära ja proovi uuesti
                var suvalisus = new Random();
                elemendid = elemendid.OrderBy(c => 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) -> bool:
    """Kas elemendid on sorteeritud?"""
    return all(elemendid[i] <= elemendid[i + 1] for i in range(len(elemendid) - 1))

def bogosort(elemendid) -> 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 $n!$ 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).

Seotud algoritmid

• Gorosort on sorteerimisalgoritm, mis loodi Google Code Jam 2011 jaoks. Algoritm töötab nagu bogosort, ainult et terve elemendi hulga segamise asemel segatakse mingi suvaline alamhulk elementidest.

• Bozosort on sorteerimisalgoritm, mis töötab nagu bogosort, aga seni kui elemendid ei ole sorteeritud, valib suvaliselt kaks elementi ja vahetab need.

• Dropsort on kaduvusega sorteerimisalgoritm. See töötab, käies läbi elementide hulga ja eemaldades kõik elemendid, mis ei ole sorteeritud.

• Bogobogosort on algoritm, mis loodi nii, et kui seda praktikas jooksutada siis see ei saaks valmis enne universumi soojussurma. See töötab rekursiivselt kutsudes ennast välja aina väiksema elementide alamhulga peal. Kui elementide hulk sisaldab vaid ühte elementi, tagastab bogobogosort, et elemendid on sorteeritud, kui mitte siis teeb n-1 elementidest koopia, sorteerib need kasutades bogobogosorti ja siis kontrollib, et kas koopia viimane element ja n element on sorteeritud, kui jah siis tagastab, et elemendid on sorteeritud, kui ei siis segab elemendid laiali ja proovib uuesti.