Bogosort

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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