Intro to Quicksort Algorithm - NY Comdori Computer Science Note

Quicksort is one of the most popular sorting algorithms.
Although there are quite a few sorting algorithms such as mergesort, heapsort quicksort has a unique property that is noteworthy.
In general, quicksort performs better than others due to its property under a certain condition.

Let’s take a look at the basics of quicksort!

How does quicksort work?

Quicksort sorts the array by partitioning the array recursively which is one of divide and conquer sorting algorithms.
Quicksort first selects a random element and partitions the elements based on the selected element which is called a pivot.
All the elements that are less than the pivot are placed on the left side of the pivot and the others placed on the right side.
However, placing the elements to the left side is enough because all the leftovers will be on the right side of the pivot.
It means you need to keep track of the index to place the next item during partitioning.

Let’s take a look at an example first which I believe will help understand much better than just words.
Here is the unsorted array.

Quicksort partitioning Algorithm

The core of quicksort is partitioning as quicksort is done by performing partitioning recursively.
Here are the partitioning algorithm steps.

Selects a random element for the pivot
Iterate the array from low to the high boundary and place the element to the left side of the partition
Place the pivot element to the next partition index after the iteration is done
Now you have two partitions
- Left partition has elements that are less than the pivot value
- Right partition has elements that are greater than or equal to the pivot value

Partitioning Algorithm Example

25 is selected as the pivot value.
Please note that I have to keep track of the index to place the next item which is called partition index in this example.
The iterator index is literally an iterator that will visit every single node here.

Now we need to do the following operations.

Is 10 < 25 true?
- Swap the element with the one at the partition index. In this case, 10 is staying at the same place
- Increment the partition index by 1 since it’s filled
- Increment the iterator index by 1 to check next item
If not true
- Increment the iterator index by 1 to check the next item

We perform the same operation as the above.

Is 3 < 25 true?
- Swap the element with the one at the partition index. In this case, 3 is staying at the same place
- Increment the partition index by 1 since it’s filled
- Increment the iterator index by 1 to check next item
If not true
- Increment the iterator index by 1 to check the next item

Is 200 < 25 true?
- Swap the element with the one at the partition index
- Increment the partition index by 1 since it’s filled
- Increment the iterator index by 1 to check next item
If not true
- Increment the iterator index by 1 to check the next item. Please note that we are only placing elements that are less than the pivot value.

Is 55 < 25 true?
- Swap the element with the one at the partition index
- Increment the partition index by 1 since it’s filled
- Increment the iterator index by 1 to check next item
If not true
- Increment the iterator index by 1 to check the next item

Is 1 < 25 true?
- Swap the element with the one at the partition index
- Increment the partition index by 1 since it’s filled
- Increment the iterator index by 1 to check next item
If not true
- Increment the iterator index by 1 to check the next item

Is 2 < 25 true?
- Swap the element with the one at the partition index
- Increment the partition index by 1 since it’s filled
- Increment the iterator index by 1 to check next item
If not true
- Increment the iterator index by 1 to check the next item

Is 3 < 25 true?
- Swap the element with the one at the partition index
- Increment the partition index by 1 since it’s filled
- Increment the iterator index by 1 to check next item
If not true
- Increment the iterator index by 1 to check the next item

Is 88 < 25 true?
- Swap the element with the one at the partition index
- Increment the partition index by 1 since it’s filled
- Increment the iterator index by 1 to check next item
If not true
- Increment the iterator index by 1 to check the next item

Is 71 < 25 true?
- Swap the element with the one at the partition index
- Increment the partition index by 1 since it’s filled
- Increment the iterator index by 1 to check next item
If not true
- Increment the iterator index by 1 to check the next item

After the iteration, you need to make sure the pivot is swapped with the partition index.
Now we have partitioned the array.
The left partition has all the elements that are smaller than the pivot (25) and the right partition has all the elements that are greater than or equal to the pivot.

Quicksort Algorithm

Quicksort becomes very easy once partitioning is done.
You just need to recursively apply partitioning to both left and right partitions.
This is why quicksort is a divide and conquer algorithm since it divides the problem to each subset (partitions) to solve the problem.
It will be clear once you see the code example.

Code Example

/**
 * @brief  partition the array from low to high index
 * 
 * @param  array  array to partition
 * @param  low    lower boundary index
 * @param  high   upper boundary index
 * 
 * @return index of the pivot after partitioning
 */
int partition(vector<int> &array, int low, int high)
{
    int partitionIdx = low;

    // here I just chose the last element but it really should be random 
    // or some other method not to make quicksort to run worst case of O(n^2)
    int pivot = high;
    
    for (int i = low; i < high; ++i)
    {
        // current value < array[pivot], swap
        if (array[i] < array[pivot])
        {
            swap(array[i], array[partitionIdx++]);
        }
    }
    
    // place pivot to correct place. this value will never be moved now
    swap(array[partitionIdx], array[pivot]);
    
    return partitionIdx;
}

/**
 * @brief  quicksort
 * 
 * @param  array  array to sort
 * @param  low    lower boundary index
 * @param  high   upper boundary index
 * 
 * @return index of the pivot after partitioning
 */
void quicksort(vector<int> &array, int low, int high)
{
    if (low < high)
    {
        int partitionIdx = partition(array, low, high);
        quicksort(array, low, partitionIdx - 1);
        quicksort(array, partitionIdx + 1, high);
    }
}

Performance

The key of the quicksort is partitioning and the key of partitioning is how well you can select a pivot element.
Do you remember I mentioned that quicksort performs better than others under certain conditions?
That really depends on selecting a pivot element.
If the random pivot is selected than it is likely to have balanced partitions and quicksort will perform better than many others because it sorts all the elements in place.
(Think about mergesort which requires extra buffer and copy)
Average case performance is, therefore, O(n log n)

However, in a worst-case scenario where the pivot is selected in incremental or decremental order, the performance will be O(n^2) which is not better than bubble sort.
It happens because there will be extremely unbalanced partitions where the size will be (n – 1) and 1 respectively.
That’s why the performance of the worst-case scenario is O(n^2).
For that reason, there are some algorithms for random pivot selection.

Conclusion

The key to the quicksort is balanced partitioning based on a good pivot.
The partitioning algorithm itself is quite useful for cases such as finding the median. (Please note that finding median doesn’t require the entire array to be sorted)