Bogosort
Van Wikipedia
Bogosort 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:
- genereer een willekeurige permutatie van de elementen van het te sorteren array (gooi ze op willekeurige wijze door elkaar);
- controleer of deze in de juiste volgorde staan;
- 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 (tenzij je uitzonderlijk veel geluk hebt).