Sorted in one pass
A single bubble-sort pass scans a list from left to right and swaps each adjacent pair that is out of order. A uniformly random permutation of gets one pass. What is the probability that the list is fully sorted afterwards? Give a decimal to four places.
Show hints (2)+
- How far left can a single element move during one left-to-right pass?
- For each value, count how many larger values stand in front of it.
Answer
Reveal answer →Final answer
0.0444 (± 0.0005)
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading