Skip to content
Get started

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 1,2,…,61,2,\dots,6 gets one pass. What is the probability that the list is fully sorted afterwards? Give a decimal to four places.

Show hints (2)+
  1. How far left can a single element move during one left-to-right pass?
  2. For each value, count how many larger values stand in front of it.

Answer

Reveal answer →

0.0444 (± 0.0005)

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions