Bogosort

Bogosort, Monkeysort or Stupidsort refers to a non - stable sorting method, in which the elements are randomly shuffled so long until they are sorted. Because of the long duration bogosort is the prototype of a bad algorithm. Bogosort particular algorithms or data structures used in computer science education in the fields, in order to illustrate the properties of the sorting process is generally at one extreme example.

Runtime behavior

Bogosort is a ( randomized ) Las Vegas algorithm, so its running time is a random variable. The expected term is at best (given in the Landau notation) if the specified list is already sorted. On average, the running time. The Faculty is the number of possible arrangements ( permutations ) of various elements. The operation that is performed most frequently, and run-time behavior is determined, the number of permutations. Amazingly, the expected number of comparisons that strives for large lists against, much less. Herein, the Euler number.

In reality can be as long as the running time, but are extremely long running times due to the Markov inequality, correspondingly unlikely. The algorithm comes with the assumption of true random number generators and a finite number of elements to be sorted almost surely, ie with probability 1, after finitely many steps to a conclusion. This means that it is still possible that the algorithm never terminated. If a pseudorandom number generator is used, the period must be long enough so that any permutation is generated at least once before repeating the sequence.