undefined | Better HN

0 pointsbtilly14y ago0 comments

Bogosort terminates with probability 1. Is it really reasonable to say it doesn’t guarantee termination?

Yes.

Particularly when done on real machines that use pseudo-random numbers that will repeat in finite time. For instance many use http://en.wikipedia.org/wiki/Mersenne_twister with a version that will repeat after 2^19937-1 steps. With a random array of 2500 elements, the odds are very good that bogosort will fall into a loop before it has successfully sorted the array.

0 comments

Retric14y ago

I think that depends on how you cycle the numbers. If you use the new positions as part of the randomization process then the average cycle time becomes much larger than 2^19937-1.

AKA: (Ignoring the fact it takes more than one number to shuffle a deck). After the first cycle of 2^19937-1 you have ~1 in (2500!) that you repeat the initial position. After the second cycle it's ~2 in (2500!) etc. It may be possible that your odds of success are around (2^19937-2)/(2^19937-1).

btillyOP14y ago

Of course how you cycle the numbers matters. I assumed that you take the original deck and keep on coming up with random shuffles of it. If so, then your cycle time will be the cycle time of the algorithm times (worst case) the length of the array. However if you do the obvious trick of doing each random shuffle to the previously shuffled deck, then the cycle time for the permutations to repeat becomes much, much longer - long enough that you are very, very likely to hit sorted at some point. But it is possible that you won't. And if you hit the case where you won't, then you'll absolutely never terminate.

j / k navigate · click thread line to collapse