Post Cover

Understanding Quick Sort - Comparison and Analysis

Algorithms Posted Oct 11, 2020

Quick Sort is an internal sorting technique which can be used to arrange a given set of unordered dataset into required order. It is the most efficient internal sorting technique, which doesn't use any auxiliary memory (or additional space to hold the dataset while processing) and uses a "divide and conquer" approach for its sorting.

How it works:

As mentioned before, the Quick Sort algorithm uses a "Divide and Conquer" approach to sort the elements. In this approach, the algorithm breaks the input dataset into working subsets based on a criteria and then recursively applies the same approach on the resultant subsets, while performing sorting on these subsets. All this operations happen "in-place" within the array and hence no additional memory is required for this algorithm.

The algorithm happens in four simple steps:

  1. Pick a Pivot element from the input dataset, which can generally be the median of the dataset
  2. Start from both the ends of the dataset and swap the elements such that all the elements in the left side of the chosen "pivot" are lesser than it and all the elements on the right side of the pivot are greater than it.
  3. Once the left and right pointers which are running from the opposite side run across each other, divide the dataset into smaller subsets based on the index where these indices collide.
  4. Repeat the steps from 1 to 3 recursively on the thus created subsets, until we have these left and right pointers point to the same index, which means that the dataset is now completely sorted.

The algorithm for this sorting looks like this:

function mergesort(array A, integer left, integer right)
begin
    if left >= right then
    begin
        return;
    end

    let pivotIndex = (left+right)/2;
    let pivot = A[pivotIndex];

    let partitionIndex = partition(A, left, right, pivot);
    mergesort(A, left, partitionIndex - 1);
    mergesort(A, partitionIndex, right);
end

function partition(A, left, right, pivot)
begin
    while left <= right do
    begin
        while A[left] < pivot do
            left = left + 1
        while A[right] > pivot do
            right = right - 1
        
        if left <= right then
        begin
            swap(A, left, right);
            left = left + 1;
            right = right - 1;
        end
    end
    return left;
end

And its implementation can look like below:

public void DoQuickSort(ref int[] arr, int left, int right)
{
    /*
        1. Find a Pivot
        2. Set Left and Right to Ends of Arrays
        3. Swap all the elements such that
            Elements to left of Pivot are smaller than Pivot
            Elements to right of Pivot are greater than Pivot
        4. If the Left and Right come across, partition the array into two parts
            from the start to left, from left+1 to right
            recursively work on the successive chunks
    */
    // array is now divided till the individual elements
    // no more the swapping function is needed
    
    if (left >= right) return;
    
    // set the median as the pivot
    int pivot = arr[(left + right) / 2]; 
    
    var partitionIndex = SwappingFunction(ref arr, left, right, pivot);
    
    // work on the left chunk of the array
    DoQuickSort(ref arr, left, partitionIndex - 1);
    
    // work on the right chunk of the array
    DoQuickSort(ref arr, partitionIndex, right);
}

public int SwappingFunction(ref int[] arr, int left, int right, int pivot)
{
    // all the elements to left of pivot are smaller
    // all the elements to the right of pivot are larger

    while (left <= right)
    {
        // move till the element which a[left] > pivot
        while (arr[left] < pivot)
        {
            left++;
        }
        //left now contains the element which is larger than pivot

        // move till the element which a[right] < pivot
        while (arr[right] > pivot)
        {
            right--;
        }
        // right now contains the element which is smaller than pivot

        // now swap left and right
        if (left <= right)
        {
            var temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    // now left is almost at the center of the array
    // which can now be used to break the array into sub arrays
    return left;
}

For an input dataset {5,9,2,4,7,8} the processing looks like below:

Input: 5,9,2,4,7,8

#Iteration 1:
PivotElement:2  Left: 0 Right: 5       
Processed Set: 2,9,5,4,7,8
#Result PartitionIndex: 1

PivotElement:4  Left: 1 Right: 5       
Processed Set: 2,4,5,9,7,8
#Result PartitionIndex: 2

PivotElement:9  Left: 2 Right: 5       
Processed Set: 2,4,5,8,7,9
#Result PartitionIndex: 5

PivotElement:8  Left: 2 Right: 4       
Processed Set: 2,4,5,7,8,9
#Result PartitionIndex: 4

PivotElement:5  Left: 2 Right: 3       
Processed Set: 2,4,5,7,8,9
#Result PartitionIndex: 3

Output: 2,4,5,7,8,9

Time and Space Complexity Analysis:

If we observe how the algorithm works, for every iteration of the dataset the subject dataset on which the algorithm works on is almost divided to half. For example, in the above dataset we have the first iteration run on the entire dataset with the PivotElement as 2 (index 2) with left and right pointers at the ends of the dataset. But in the second iteration, the subjective dataset is now between 1 and 5, later shrunk to 2 and 5, 2 and 4 and so on. At the final iteration, the subjective dataset was between 2 and 3 which is the set [5,7].

This way, for a typical dataset the algorithm works on about half of the input per iteration. Hence the time taken for this algorithm is logarithmic, and its an average of O(nlogn) for any given dataset.

# dataset working split #

        n
n/2         n/2 -> at every level, the total work done is always n

n/4 n/4     n/4 n/4
.
.
.
.
1 1 1 1 ... n (leaves of the call tree)

Here we have the logn part because the dataset is being divided as we proceed further down the iterations, forming a tree of recursive calls. The depth of this tree is logn. And at every level of this dataset, we have a constant O(n) work done, since no two recursive calls work on the same dataset. Hence the total is O(nlogn).

As for the space, apart from a few variables for storing the left, right and pivot pointers, we aren't using any variable memory parts. Hence the algorithm always takes a constant O(1) space.

Final Thoughts:

QuickSort is the fastest internal sorting technique, which does the operations "in-place" without requiring any additional space. It works based on the "Divide and Conquer" approach and uses a recursive approach for the operation, with a limited subset of elements at any time. The algorithm takes an efficient O(nlogn) time for the normal case, while at a worst case scenario the time is O(n2). Whereas on the memory front it still goes with an optimal O(1) space.

Author-Image

Ram

I'm a full-stack developer and a software enthusiast who likes to play around with cloud and tech stack out of curiosity.

You can now show your support. 😊

We use cookies to provide you with a great user experience, analyze traffic and serve targeted promotions.   Learn More   Accept