Naar inhoud springen

Bogosort

Uit Wikipedia, de vrije encyclopedie

Bogosort (ook stupid sort of slowsort genoemd) is een voor de grap voorgesteld sorteeralgoritme dat extreem inefficiënt is, maar misschien nog enige waarde heeft als ijkpunt voor het theoretisch slechtste sorteeralgoritme.

Het algoritme gaat als volgt:

  1. genereer een willekeurige permutatie van de elementen van de te sorteren array (gooi ze op willekeurige wijze door elkaar);
  2. controleer of deze in de juiste volgorde staan;
  3. zo nee, ga terug naar stap 1.

Als een pseudo-randomgenerator wordt gebruikt, is het mogelijk dat dit algoritme niet eindigt. Als alle elementen van elkaar verschillen, is de verwachte complexiteitsgraad O(n × n!). Bogosort is niet stabiel.