Running Time and Termination
This sorting algorithm is probabilistic in nature. If all elements to be sorted are distinct, the expected number of comparisons in the average case is asymptotically equivalent to, and the expected number of swaps in the average case equals . The expected number of swaps grows faster than the expected number of comparisons, because if the elements are not in order, this will usually be discovered after only a few comparisons no matter how many elements there are, but the work of shuffling the collection is proportional to its size. In the worst case, the number of comparisons and swaps are both unbounded, for the same reason that a tossed coin might turn up heads any number of times in a row.
The best case occurs if the list as given is already sorted; in this case the expected number of comparisons is, and no swaps at all are carried out.
For any collection of fixed size, the expected running time of the algorithm is finite for much the same reason that the infinite monkey theorem holds: there is some probability of getting the right permutation, so given an unbounded number of tries it will almost surely eventually be chosen. However, if a pseudorandom number generator is used in place of a random source, it may never terminate, since these exhibit long-term cyclic behavior.
Read more about this topic: Bogosort
Famous quotes containing the words running, time and/or termination:
“Animals used to provide a lowlife way to kill and get away with it, as they do still, but, more intriguingly, for some people they are an aperture through which wounds drain. The scapegoat of olden times, driven off for the bystanders’ sins, has become a tender thing, a running injury. There, running away ... is me: hurt it and you are hurting me.”
—Edward Hoagland (b. 1932)
“We have not the motive to prepare ourselves for a “life-work” of teaching, of social work—we know that we would lay it down with hallelujah in the height of our success, to make a home for the right man. And all the time in the background of our consciousness rings the warning that perhaps the right man will never come. A great love is given to very few. Perhaps this make-shift time filler of a job is our life work after all.”
—Ruth Benedict (1887–1948)
“We hoped for a happy termination of this terrible war long before this; but God knows best, and has ruled otherwise.”
—Abraham Lincoln (1809–1865)