We know that Quicksort, Mergesort and Heapsort are three top sorting algorithms use to sort an array. They all have a time complexity of O(nlogn).
While in mergesort, the problem was in its ground details. It actually takes extra space in the memory during merge operation.
Randomization
Randomization is a technique which has been frequently used to handle the worst case inputs. The idea behind is to randomize our choices so that as the program proceeds none of the input remains worst case.
We hope that we get good luck with randomization and that it happens with high probability.
Expectation
Let’s revise some concepts about probability and random variables.
Let x be a random variable(i.e., a function to map experiment results to real numbers), and E[x] be its expectation defined by
E[x]=SUM(xi*P[x=xi])
where xi is a indicator random variable and P[x=xi] denotes the probability of x to be equal to xi. Function SUM denotes sum over all such indicator variables.
Let’s consider some examples:
Expectation of rolling a dice= E[x]=SUM(xi*P[x=xi])=1*(1/6)+2*(1/6)…=3.5
Expectation for sum of two dice rolled simultaneously…
Let x=sum of the two dice
for x=5….. Possibilities: {(1,4),(4,1),(2,3),(3,2)}
Hence P[x=5]=4(1/36)=1/9 and E[x=5]=5*P[x=5]=5/9
So for all x we can do likely same. But we do it using a property that expectation is continuous over sums, hence
If x=x1+x2; so E[x]=E[x1]+E[x2]; where x1 is the outcome of dice 1 and x2 is for dice 2
Hence E[x]=E[x1](=3.5)+E[x2](=3.5); => E[x]=7
Hat Checking Problem
N people leave their hats in a place and after some time they return and pick a hat at random. What is the expected number of persons who will get back their own hats?
Let x be the number of persons who get back their own hats. So ‘0≤x≤N’
Indicator variable xi will be 1 if person ‘i’ gets his/her hat back otherwise 0.
Probability for a person to choose his/her own hat= 1/N
Hence, E[xi]=1*P[correct choice]+0*P[incorrect choice]=1*(1/N)
E[xi] is hence the expectation of person ‘i’ to get the hat back. So the expected number of persons to get their hats back will be sum over all such xi’s.
E[x]=E[x1]+E[x2]+E[x3]……E[xN]
Hence, E[x]=N*(1/N)=1
So we expect exactly one person to get his/her hat back.
Quicksort
Quicksort although has a very good performance in expectation, it can be really unlucky sometimes leading to O(n²). Also it completes sorting without taking extra space.
We introduce randomization in algorithm during pivot selection. Pivot is any random value in the array about which it is partitioned keeping the larger elements on right and smaller ones on left. We then recurse over the two parts to sorted array.
Partition takes n steps at most since it has to compare elements to the pivot. Hence, for partition, time complexity=O(n).
Let k be the kth smallest element in the array. If T(n) represents the time taken to sort n elements, then after partition,
T(n)=T(k)+T(n-k-1)+O(n)
Now, in the worst case k=0 or k=n(Unequal partition).
So T(n)=T(n-1)+O(n). which is same as insertion sort = O(n²)
And in the best case, k=n/2(equal partition).
So T(n)=2T(n/2)+O(n). which is same as merge sort = O(nlogn)
Now how does the algorithm perform in expectation?
Since the pivot is chosen completely at random, we have to average over all the possible choices of pivot. Moreover, in each partition comparison between two elements is only possible when one of them is pivot and also, no two elements are compared to each other more than once.
Let,
kth smallest element in the array be ek.
Random variable x shows the total number of comparisons performed, and
Indicator variable xij be 1 when ei is compared to ej otherwise 0. Here, 1≤i<j≤N for simplicity
Since x shows total number of comparisons and xij simply counts the number of comparisons, x is sum of xij over all the possible combinations of i and j. Also,
E[x]=SUM(E[xij]); for all 1≤i≤N-1 and i+1≤j≤N
E[xij]=1*P[xij=1] i.e., Probability of comparison to happen between ith smallest and the jth smallest element.
If we note, there are three ranges of pivot:
Left of both i and j: Here we do not guarantee immediate comparison, it may however occur in future.
Right of both i and j: same as above..
In between i and j: Here no comparison is assured.
Also, during one partition, ei and ej can only be compared if one of it is a pivot.
To be compared within a partition process, total elements=j-i+1
For ei to be compared with ej, i.e., P[xij=1]=2/(j-i+1) for the two choices (ei and ej)
Now, Expectation of total number of comparisons=SUM(E[xij]) for 1≤i≤N-1 and i+1≤j≤N
= SUM[2/(j-i+1)]
With Euler’s approximation it can be shown that E[x]≤2nlogn
Which shows that time complexity=O(nlogn)
So, quick sort in expectation has the same behavior as merge sort. However in some cases( mostly the worst cases for merge sort) Quicksort gives much better performance than Mergesort despite of the space advantage. However we can never be assured of its performance due to randomization.
Quick select
What if you intend to find the kth smallest element from a given array?
Basic idea that comes to us is sorting the array. But that will of course lead to O(nlogn). We have a better performing algorithm like Quick sort which provides a best case solution in O(n) time complexity.
Algorithm proceeds similar to quick sort,
It first selects a pivot at random and partition the array in linear time=O(n)
Next it takes either the left or the right part of the array based on the pivot’s position and value of k
It proceeds to recurse the chosen part until ‘pivot’s position=k’
Analyzing the algorithm, we proceed similarly,
ek shows the kth smallest element; Random variable x shows total number of comparisons and Indicator variable xij shows the count for each comparison to occur between ith and jth smallest elements.
Proceeding this calculation in three cases:
Case 1: when i<j≤k:
Case 2: when k≤i<j: This will be similar to case above, hence linear time.
Case 3: when i<k<j:
This again proves to be linear time, i.e., O(n).
If we proceed as above, we can show that the expected(or average) complexity of quick select is O(n) time.
However, Quick select is still randomized with worst case complexity being O(n²).
