Investigating quick sort partitioning

There were times in the past when I had discussions with my friends and colleagues regarding problem-solving and preparation for interviews. Many of them considered standard algorithms and problems as something which they learn and then forget after some time. This is true to some extent but not completely. This usually happens when concepts are not internalized into our systems properly. Once we learn an algorithm, it should become a part of our paraphernalia as software engineers. It should become a part of our thought process. This article is just an attempt to create that mindset.

Usually, when the majority of people start prepping for the interviews they start looking at various sorting algorithms and try to remember the steps. The agenda of this article is to create an impression of quicksort on your mind so that this algorithm becomes a way of solving a related problem rather than just an interview question. We will focus on the approach which quick sort takes and how it can be utilized in solving other problems.

So, what is the core idea behind quicksort? If I am given an array of 5 elements [3,1,4,5,2], quicksort will choose 1 pivot element and put all the elements less than it on one side and all elements greater on the other. In this case, if we choose 2 as the pivot.

The first step would be, [1,2,4,5,3]. Here all elements greater than 2 are on the right side and elements less than 2 on the left side. This process is called partitioning.

There are 2 key ideas in quicksort: Pivot and Partitioning.

Partitioning: Partitioning refers to a step where we logically divide a linear data structure such that in one part all elements are less than the pivot and all elements on the right side are greater.

We are now left with the question that how do we partition? We will take any simple logic for picking a pivot. For now, pick the last element. So, any partition in the real-world too will create a boundary. And to compare whether an element is less than the chosen pivot, we need to iterate through the array. So we know that comparison and iteration through the array are two key steps to the partitioning logic.

Imagine we have an array [1,2,3,4,5], to make a boundary in the array we need to have a variable bound which will keep track of the index of the element which is less than the pivot. So that we can place pivot next to it and all other elements can follow.

Resulting structure should be [e1,e2,e3,(bound/pivot), e4,e5,e6.....] where, e1,e2,e3 < pivot < e4,e5,e6.

We keep iterating by making comparisons,

is 1<5 true? bound++, index++; is 2<5 true? bound++, index++; is 3<5 true? bound++, index++, and we will reach the end. And the boundary is correct. 5 is the biggest element and all elements less than that are on the left side. Nothing to be done. But what happens when the array is like this [1,2,3,7,4,5]. Let's try to repeat the same process.

is 1<5 true? bound++, index++; is 2<5 true? bound++, index++; is 3<5 true? bound++, index++;

is 7<5 true? NO!! We cannot increment the bound as bound represents the end of elements that are less than the pivot. So what do we do now? Just like real life, we will move on with the iteration and skip incrementing the bound so that if we find some other element less than pivot in future we will swap 7 with that element. So that the smaller element comes here and this bigger element is thrown away.

The key is whenever we see a bigger element than the pivot, we freeze bound there and wait for an element which is smaller than the pivot, and as we encounter it we do a swap. If we do not encounter any smaller element then also we can safely swap it with the pivot as it is greater than pivot.

So, again, is 7<5 true? NO, so index++, bounds remain the same. is 4<5 true yes, so swap positions of 7 and 4, bounds++, index++.

Once the iteration is finished, we will have bounds pointing to the partition. Then we will just swap the positions of the pivot and the array[bound]. So pivot will end up in its proper position and the array will be partitioned.

public int partition(int[] array) {
    int pivot = array[array.length-1];
    int bound = 0; // tracks the boundary
    for(int index = 0 ; index<array.length-1 ; index++) {
        if(array[index] < pivot) {
            if(bound!=index) {
            swap(array,bound,index);
            }
            bound++;
        }
    }
    swap(array,bound,array.length-1);
    return bound;
}

The above snippet with partition an array[ 0, length -1] once wrt the last element as a pivot. In quick sort, divide the whole array into multiple small sub-arrays, and repeat this partitioning. Each time partitioning is done, pivot ends up in its correct position. How do we divide the array, we do it by marking low and high index for the array.

[1,2,3, 4,5] - We can divide this into 2 arrays by having lowIndex = 0, highIndex = 2 :: lowIndex = 3 , highIndex = 4. We have to modify the above snippet to accept low and high rather than using 0 and len-1 as bounds.

// Modified partitioning logic
public int partition(int[] array,int low, int high) {
    int pivot = array[high];
    int i = low;  // Keeps track of index at which we add an element less        than pivot.
    for(int j = low ; j<high ; j++) {
        if(array[j] < pivot) {
            swap(array,i,j);
            i++;
        }
    }
    swap(array,i,high);
    return i; // returns the index at which partition happened or correct pivot position.

}

Partitioning is what that does the heavy lifting in the sort. The actual sort is just repeated partitioning.

while(low < high) {
    int pi = partition(mArray,low,high);
    // This is how we divide the array by marking low and high indices.
    _internalSort(mArray,low,pi-1);  // high as one element before pi
    _internalSort(mArray,pi+1,high);  // low a one element after pi
}

Conclusions: We divide the whole array using indices and operate on the same array, and do no use any auxiliary space to do the sorting, so quick sort is an IN PLACE sort. An in-place sort does not make use of any additional data structure to complete the sort.

The swapping does not incorporate the relative position of the elements before swapping. Which is important for preserving the initial order of elements that are equal. It is not important in the case of primitives, because they do not have their identity. Example, [1,1,1,1], if we arrange the 1's in any order it is all same, but [ Integer(1), Integer(1), Integer(1) ], they all are separate identities and it is important to preserve the order of these elements in the post sort structure. So, quicksort is NOT STABLE.

Quick sorts are cache-efficient as the data is accessed linearly in an array and if the array fits the cache, then it will require less waiting on main memory lines. In terms of computers, it is called locality of reference, and merge sort will also have decent locality of reference but the cost is paid in terms of additional memory for the auxiliary array and access to it.

We saw that quicksort has lesser m/m requirements but still, we will find, the majority of real-life sorting is done using merge sort or some modified version of merge sort why?

1. The average performance of O(N log N) degrades to O(N^2) for pathological inputs. But merge sort has O(NlogN) as the worst case.
2. Quicksort is not stable. We are not always operating on primitive integers in real-life use cases. For example, I have an email page that needs to get sorted wrt to date and in that date wise sorted list, I have to display the emails in alphabetical order sorted wrt to sender's mail id. Using quick sort here might not preserve the original order which was created after sorting wrt date. Even in JDK, we if see the source code, Arrays.sort() uses quicksort for primitives and modified merge sort for objects.
3. Quicksort can be made stable by considering identities of the objects but, it would need O(n) additional space along with the recursive call stack memory. In that case, merge sort can be used as it is by default stable and simpler than stable quicksort.

But still, if we are solving a problem in an interview where we are given int array-based problems, quicksort is anytime better than merge sort.

The partitioning logic can help us solve a lot of problems in an efficient manner, eg: We are given an array of positive and negative numbers, we have to keep all negative numbers on one side and positive on the other. We can just take 0 as pivot here and do partitioning and we will be done in a linear time solution. Or problems related to moving a certain set of numbers to the beginning or end of the array, and many more.

Simplistic analysis for time and space complexity: When we do a partition, it is a linear operation as we have to iterate till the end of the array fragment so the order is O(n) simple. But how many times, do we have to do it? The answer is the number of times we divide the array into halves, which is in the order of log2n. So, in simple terms, the order is O(N log N) in the avg case.

We will deal with the pivot and how it impacts runtime performance in another article.

Cheers!