Quick Sort

April 28, 2019 4 minutes

Before we discuss the actual algorithm, keep in mind that Quick Sort algorithm does not justifies its name and is not the quickest sorting algorithm that you may have expected it to be (from its name).

There are other algorithms like MergeSort which outrun quick sort for worst case scenarios.

Ok, so enough of the preface, let’s talk about the actual algorithm.

QuickSort (like MergeSort) is another divide and conquer based algorithm that considers one pivot element at a time and sorts the elements of the input dataset around this element. Unlike merge sort, it does not have a merge phase to combine the elements instead it sorts them in place by swapping the ones that are out of order.

The pivot element plays the role of a protagonist in this play of elements (in every iteration) and the entire sort operation revolves around this. The basic idea of quicksort algorithm states, that for a given pivot element:

  • All the elements smaller than it should come before the pivot element
  • And all the elements larger than it should come after the pivot element.

Consider the following example :

QuickSort

For given input {3,5,1,6,8,4,7,2}, following steps are performed :

  1. pivot: 3 : All the elements smaller than 3 are placed before it and all the elements larger than 3 are placed after 3. So after this iteration, 3 is in its sorted position and the input array is now updated to be {1,2,3,6,8,7,4,5}.
  2. pivot: 1 : As there was a swap made, the next iteration again starts from same index and as 1 is already in its sorted position, no change is made to the input array {1,2,3,6,8,7,4,5}. Sorted elements are 1 and 3.
  3. pivot: 2 : Similar to the previous iteration, 2 is also in its correct position and hence once again, no change is applicable in this iteration as well. input array remains {1,2,3,6,8,7,4,5}. Sorted elements are 1, 2 and 3.
  4. pivot: 3 : 3 being in its correct position leads to no change to the input array {1,2,3,6,8,7,4,5}. Sorted elements remain 1, 2 and 3.
  5. pivot: 6 : Next 6 becomes the pivot element. As it is not in its correct position, elements smaller than 6 are placed before it and elements larger than 6 are positioned after it. input array becomes {1,2,3,4,5,6,7,8}. Sorted elements are 1, 2 3 and 6.
  6. pivot: 4 : As a swap was made, the next iteration again starts from the same index and this time the pivot element is newly positioned element 4 which is already in its correct position. No new swaps are applicable and the input array remains {1,2,3,4,5,6,7,8}. Sorted elements are 1, 2, 3, 4 and 6.

The above mentioned steps are repeated until the entire array is sorted. The subsequent iterations does not see any swaps as all the elements are already positioned on their correct positions.

Considering the above mentioned example as a basis, let’s try to understand the pseudo code for quick sort algorithm. The logic is divided into two routines (sort and partition) with the partition rotuine being the backbone of the core logic.

Pseudo Code

  1. Initialize
    • input: input array to be sorted
    • length: number of elements in the array
    • start: start index of the array (i.e. 0)
    • end: last index of the array (length -1)
  2. Sort
    • while start < end:
      • pivot:= call partition with input, start, end
      • Recursively call Sort with input, start, end = pivot -1
      • Recursively call Sort with input, start, end = pivot -1
private void quickSort(int[] input, int start, int end) {
    if (start < end) {
        int pivot = partition(input, start, end); // pivot denotes the sorted location
        quickSort(input, start, pivot - 1); // first partition (one element before pivot)
        quickSort(input, pivot + 1, end); // second partition (after pivot)
    }
}

private int partition(int[] input, int start, int end) {
    int pivot = input[start];
    int i = start, j = end;
    while (i < j) {
        while (i < input.length && input[i] <= pivot) {
            i++;
        }
        while (j > 0 && input[j] > pivot) {
            j--;
        }
        if (i < j) {
            swap(input, i, j);
        }
    }
    swap(input, start, j);
    return j;
}

// a utility to swap two elements of an array denoted by from and to positions
private void swap(int[] input, int from, int to) {
    int temp = input[from];
    input[from] = input[to];
    input[to] = temp;
}

Complexity

The worst case complexity of quick sort is $O(n^2)$ which is comparable to other sorting algorithms like BubbleSort or SelectionSort. Also it has an additional space complexity associated with it that can range from $O(log n)$ to $O(n)$.

A working java example with test case can be found here.

comments powered by Disqus