Kasutaja:Kmkmmkmmm/lk1

Bogosort

Bogosort on arvutiteaduses (tuntud ka kui permutatsioon sorteerimine) sorteerimisalgoritm, mis on väga eba efektiivne. Bogosort põhineb katse-eksitus 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 nimi tuleb ingliskeelsete sõnade bogus (eesti keeles lollus) ja sort (eesti keeles sorteerimine) kombineerimisel.

Sellest algoritmist eksisteerib 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 bogosoridi 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# bogosort programm:

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# bogosort programm:

//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.

Kvant bogosort

Kvant bogosort on humoorne hüpoteetiline bogosordi edasiarendus, kus erinevalt bogosordist mitte ei segata elementide hulk vaid hävitatakse universum. Oletades, et igale tegevuse tulemusele eksisteerib eraldi universum, kus see tulemus toimus, jooksutades kvant bogosorti hävinevad kõik universumid, kus elemendid ei ole sorteeritud. Seega jääb alles vaid universum, kus kvant bogosort sorteeris elemendid ühe segamise abil. Teoreetiliselt on kvant bogosoridi 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 sorteermisalgoritm. 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.