Bubble Sort in One Go
An interesting quant interview question asked in Jump Trading this season
Calvin got an array of size n filled with a random permutation of {1,2,3,4,… n}. She does one pass of the bubble sort algorithm on it and after the first pass itself, the array becomes sorted. Can you tell the probability of this happening ?
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
.
Solution
There are 𝑛! possible permutations of n numbers. We want only permutations that end up in a sorted array after a single pass. A single pass runs 𝑛−1 operations that could be encoded as 0 (no swap) or 1 (swap). In total there are 2^(n-1) possible swap combinations for the last pass of the bubble sort.
So to get the probability you just divide it by the total number of permutations :
.
.
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!
My approach:
We take a sorted array and start to dearrange it from the last. Just the opposite of how bubble sort works.
Firstly, we go to the nth element and see that we have 2 options, either leave it as it is. Or swap it with the n-1th element.
Then we go to (n-1)th element and again we have 2 options.
This goes on until we reach the second element. For the first element there is no 0th element to swap.
So, we end up with required possible arrangements = 2*2*2*2*.... (n-1)times = 2^(n-1)
And as total possible arrangements= n!
We get to the 2^(n-1)/n!
My approach:
Denote the probability for sorting the n numbers in one go by Pr(n).
In the first pass of Bubble sort, we can definitely say that the largest number has reached the end position. So now there arises two cases:
1. Where the largest number 'n' is already at the last position. This means we are effectively solving the problem for (n - 1) numbers.
2. Where the largest number occurs somewhere in the middle. In this case, if the bubble sort has to sort the array in one go, the part of the array coming before n should also get sorted in one go and the part of the array after n should already be sorted.
Now, we create a summation.
Pr(n) = Summation ( Pr(x) * (x!/n!) ) where the summation index 'x' goes from 0 to n - 1. 'x' denotes the number of numbers on the left side of 'n' in the array.
How to arrive at this expression?
Consider 'n' at a position such that there are 'x' numbers on the left side of 'n'. Probability that the array gets sorted in one go should imply that the numbers on the right side should already be sorted and the numbers on the left side should get sorted in one go too. Note that all these 'x' numbers should be smaller than n and after the Bubble sort pass should get sorted themselves. So we are essentially solving Pr(x).
Pr(array gets sorted in one go provided 'x' numbers are there on the left side of n) = Pr(such permutation occurs) * Pr(x)
= (x!/n!) * Pr(x)
For Pr(n) we will have to iterate for all the positions where n can occur.
Pr(n) = (1/n) * Pr(n - 1) + Summation ( Pr(x) * (x!/n!) ) , where the summation index now goes from x = 0 to x = n - 2
Taking (1/n) common from the Summation above makes it nothing but Pr(n-1).
Pr(n) = (1/n) * Pr(n - 1) + (1/n) * Pr(n-1)
Pr(n) = (2/n) * Pr(n-1)
We now have a recursive solution. Just keep expanding the Pr() that occur till Pr(3). Note that Pr(0) = Pr(1) = Pr(2) = 1.
Pr(n) = (2/n) * (2/n-1) * (2/n-2) .... 2/3
Pr(n) = 2^(n-1) / n! [Multiply and divide by 2 to make the denominator n!]