Quick Sort

This page provides introduction to Quick Sort.

Overview

Quick Sort is a divide-and-conquer algorithm that partitions the array into two halves around a pivot element. Elements smaller than the pivot go to its left, and larger ones go to its right. It then recursively sorts the left and right subarrays.

Let's sort array below, with quick sort:

$$[1, 8, 3, 9, 4, 5, 7]$$

Partition the whole array using the last element, $7$, as the pivot. After partitioning, all elements smaller than $7$ will be positioned on its left, and all elements greater than $7$ will be on its right.

Assign pointer lt, gt and pivot pointers.

In above array image, element $1$ at gt pointer is less than pivot element $7$:

• Increment lt pointer.
• Swap elements at lt and gt pointers, which is same in this case.

Increment gt pointer.

In above array image, element $8$ at gt pointer is greater than pivot element $7$:

• lt pointer remains the same.
• No swap is needed.
• Increment gt pointer.

In above array image, element $3$ at gt pointer is less than pivot element $7$:

• Increment lt pointer
• Swap elements at lt and gt pointers.

Increment gt pointer.

In above array image, element $9$ at gt pointer is greater than pivot element $7$:

• lt pointer remains the same.
• No swap is needed.
• Increment gt pointer.

In above array image, element $4$ at gt pointer is less than pivot element $7$:

• Increment lt pointer
• Swap elements at lt and gt pointers.

Increment gt pointer.

In above array image, element $9$ at gt pointer is greater than pivot $7$:

• lt pointer remains the same.
• No swap is needed.
• Increment gt pointer.

Since now, gt equals pivot pointer we exit the for loop and swap elements at lt + 1 and pivot pointers to place pivot element $7$ at it's correct position.

This concludes the partitioning of the whole array around the pivot element $7$. We apply the same partitioning process recursively on the left and right subarrays of the pivot element $7$ to get the sorted array as below:

Java

public void quickSort(int[] arr, int lo, int hi) {
  if(lo < hi) {
    int pivot = partition(arr, lo, hi);
    quickSort(arr, lo, pivot);
    quickSort(arr, pivot + 1, hi);
  }
}

public int partition(int[] arr, int lo, int hi) {
  pivot = arr[hi];

  int lt = lo - 1; // pointer to elements smaller than pivot
  for(int gt = lo; gt < hi; gt++) { // pointer to elements greater than pivot
    if(arr[gt] < pivot) {
      lt = lt + 1;
      int temp = arr[lt];
      arr[lt] = arr[gt];
      arr[gt] = temp;
    }
  }

  int temp = arr[lt + 1];
  arr[lt + 1] = arr[hi];
  arr[hi] = temp;

  return lt + 1;
}

Complexity

Let's say there are $\text{N}$ elements in an array.

Time Complexity

The average case time complexity of Quicksort is:

$$\text{O}(\text{N} \log \text{N})$$

However, when the pivot choice consistently results in unbalanced partitions complexity becomes:

$$\text{O}(\text{N}^2)$$

info

To mitigate this, randomized pivot selection is commonly used.

Space Complexity

The average case space complexity of quicksort is:

$$\text{O}(\text{N} \log \text{N})$$

Leetcode Problem Set