List Partitioning and Quicksort →
Before we try to come up with a better solution for the problem in the previous post, let us look at another familiar problem - Quicksort. A quick refresher of mergesort from one of the earlier posts will make this exercise much simpler. In mergesort, we essentially wrote a split
function to split an input list into two lists and recursively called the mergesort algorithm on each of the sub-lists produced by split
and eventually merged them using a merge
function that merges two lists by comparing the element at the head of the sub-lists.
The idea behind quicksort is similar. Instead of just splitting the list into two sub-lists, we are going to choose a pivot element (a fancy name for just an element from our input list) and split the list into two sub-lists in such a way that all the elements in the input list that are less than the pivot element would fall into one sub-list and the rest of the elements will fall into the other. Now that we are very much comfortable with writing recursive functions using accumulators, let us go ahead and write one for partitioning the list into a pair of lists (two sub-lists) given a pivot element. So, the inputs to our function are a list lst
(to split) and a pivot
element.
Let’s go ahead and see what it does on a sample list lst1
which contains [1; 11; 9; 3; 6; 7; 2; 29]
. Let’s pick 7
to be our pivot element.
As we see, all the elements less than our pivot element, 7
in this case, are in one of the sub-lists generated by partition
function.
Now, quicksort is just choosing the head element as the pivot, generating two sub-lists l1
and l2
and calling quicksort recursively on each of the sub-lists. Since each recursive call pushes the smaller element further towards the left, eventually when all recursive calls return, the list would be sorted in acsending order.
And let us try it on lst1
:
This exercise will help us find a better solution to the problem of finding the minimum missing natural number from an unsorted list. Does this ring any bell?