Quick Sort- Algorithm

Question

Let $0<α<.5$ be some constant (independent of the input array length $n$). What is the probability that, with a randomly chosen pivot element, the Partition subroutine produces a split in which the size of the smaller of the two subarrays is $≥α$ times the size of the original array?

1. $1 - 2*\alpha$

2. $\alpha$

3. $1 - \alpha$

4. $2 - 2*\alpha$

Answer 1

Take an example  α = 0.3 and the array be

A = {1,2,3,4,5,6,7,8,9,10}

So,according to the given question we have to choose pivot from the array A in such a way that the length of the smaller array after calling PARTITION subroutine would be >= (3/10) * 10 = 3

Now, the number of ways we can select a pivot from the array A = 10 (length of the array A)

So, the cardinality of the sample space = 10

Now, observe that if we choose a pivot from the numbers {4,5,6,7} then only the length of the smaller sub array would be greater than 3.  

So, the cardinality of the event space = 4

Hence the probability = 4/10 = 2/5.

Now, put  α = 3/10 in the given options

Option 1 : 1-2*(3/10) = 4/10 = 2/5

Option 2 : 3/10

Option 3 : 1-(3/10) = 7/10

Option 4 : 2 - 2*(3/10) = 7/5

So, we get that only Option 1 matches with our answer in the example.

Hence correct answer is option 1.

Now, generalize the problem

Take an arbitrary array { a1,a2,a3,.........,an }

The number of elements which can be chosen as pivot from the above array is n (length of the sub array)

So, the sample space = n

Now suppose we choose the mth smallest element in that array am (say) as pivot

Then the length of the left subarray = m-1 and the length of the right subarray = n-m-1

Note that according the problem the length of the two sub arrays must be >=  α*n

So, we can choose only from  (α*n +1)th smallest element to (n-α*n)th smallest element as pivot.

So, the number of elements we can choose as pivot is (n - 2 α*n)

So, the event space = (n - 2  α*n)

Thus the probability = (n - 2 α *n) / n = 1- 2 α (Answer)

Hence option A is the correct answer.