Skip to content
Get started

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)+
  1. How many scans are needed on average?
  2. A scan makes at least kk comparisons iff the first kk keys are increasing. Then use Wald's identity.

Answer

Reveal 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

Related questions