Counting bogosort's comparisons
Bogosort sorts 5 distinct keys as follows. Shuffle the array uniformly at random, then compare adjacent pairs from left to right, stopping at the first pair that is out of order. If all 4 pairs are in order the array is sorted and the algorithm halts; otherwise it reshuffles and scans again. Counting every comparison, including those in the final successful scan, what is the expected total number of comparisons?
Show hints (2)+
- How many scans are needed on average?
- A scan makes at least comparisons iff the first keys are increasing. Then use Wald's identity.
Answer
Reveal answer →Final answer
205 (± 0.01)
Create a free account to see the full worked solution and track your progress.
Interview format: Trading Aptitude Tests, Prop Trading