Quick Sort in Java

Introduction

This tutorial explains the Quick Sort algorithm with an example list of 7 numbers. It covers, in this order, what Quick Sort is, how partitioning works, a step-by-step walkthrough of the sort, its Java implementation with an explanation of the code, a second way of partitioning known as Hoare partitioning, how the choice of pivot decides between the best and the worst case, and the Big Oh complexity of the algorithm.

What is Quick Sort

Quick Sort is a divide-and-conquer sorting algorithm, like Merge SortClick to read: Merge Sort. It picks one item of the list, called the pivot, and rearranges the list so that all the items smaller than the pivot come before it and all the items greater than it come after it. This rearranging is called partitioning. Once the list is partitioned, the pivot is in its final sorted position and never moves again.

The items before the pivot and the items after the pivot now form two smaller sub-lists. Quick Sort sorts each of them in the same way, by calling itself recursively, until the sub-lists have just one item or no item at all. Quick Sort is an in-place sort, i.e. it rearranges the items inside the list itself and does not need a second list.

The idea of quick sort - the pivot 25 is picked from the list 10, 5, 100, 1, 10000, 50, 25; partitioning moves the smaller items 10, 5, 1 before the pivot and the greater items 10000, 50, 100 after it, which puts 25 in its final position; the two sub-lists are then sorted in the same way

How partitioning works

All the work of Quick Sort happens while partitioning. The simplest way to partition is the Lomuto partition scheme, which works as follows -
  1. The last item of the sub-list is taken as the pivot.
  2. A marker, called boundary, is kept at the start of the sub-list. All the items to the left of the boundary are smaller than the pivot.
  3. The items are read one by one from left to right. Whenever an item smaller than the pivot is found, it is swapped with the item at the boundary, and the boundary moves one place to the right.
  4. When all the items have been read, the pivot is swapped with the item at the boundary. The pivot is now in its correct place, with the smaller items on its left and the greater items on its right.
Lomuto partitioning of the list 10, 5, 100, 1, 10000, 50, 25 around the pivot 25 - the items 10 and 5 are smaller and stay where they are, 1 is swapped with 100, and at the end the pivot 25 is swapped with the item at the boundary, giving 10, 5, 1, 25, 10000, 50, 100

Quick Sort's working explained

Lets understand the working of Quick Sort using an example. Lets say the list to be sorted is [10, 5, 100, 1, 10000, 50, 25].

First partition
The last item, 25, is the pivot. Reading from the left, 10 and 5 are smaller than 25 and are already at the start of the list, so the boundary just moves past them. 100 is greater and is left alone. 1 is smaller, so it is swapped with the item at the boundary, which is 100. 10000 and 50 are greater and are left alone. Finally the pivot 25 is swapped with the item at the boundary. The list is now [10, 5, 1, 25, 10000, 50, 100]. 25 is at its correct place, with the sub-list [10, 5, 1] on its left and the sub-list [10000, 50, 100] on its right.

Partitioning the left sub-list
The left sub-list is [10, 5, 1] and its pivot is 1. No item is smaller than 1, so the pivot is swapped with the first item and the sub-list becomes [1, 5, 10]. Nothing is left on the left of 1. On its right is [5, 10], which is partitioned around the pivot 10 and stays as it is.

Partitioning the right sub-list
The right sub-list is [10000, 50, 100] and its pivot is 100. 50 is smaller, so it is swapped with 10000. The pivot is then swapped with the item at the boundary, giving [50, 100, 10000]. The sub-lists on both sides of 100 have a single item, so there is nothing more to do.

The list is now sorted - [1, 5, 10, 25, 50, 100, 10000] - after 4 partitions.

Quick Sort implemented in Java

Quick Sort Algorithm implemented in Java
package com.javabrahman.algorithms.sorts;
public class QuickSort {
  static int intArray[] = { 10, 5, 100, 1, 10000, 50, 25 };

  public static void doSort(int low, int high) {
    if (low < high) {
      int pivotIndex = partition(low, high);
      doSort(low, pivotIndex - 1);
      doSort(pivotIndex + 1, high);
    }
  }

  public static int partition(int low, int high) {
    int pivot = intArray[high];
    int boundary = low;
    for (int current = low; current < high; current++) {
      if (intArray[current] < pivot) {
        swap(current, boundary);
        boundary++;
      }//if condition ends
    }//loop ends
    swap(boundary, high);
    return boundary;
  }

  public static void swap(int first, int second) {
    int temp = intArray[first];
    intArray[first] = intArray[second];
    intArray[second] = temp;
  }

  public static void printArray() {
    for (int i = 0; i < intArray.length; i++) {
      System.out.print(" " + intArray[i]);
    }
  }

  public static void main(String args[]) {
    System.out.print("Array Before Sorting->");
    printArray();
    doSort(0, intArray.length - 1);
    System.out.print("\nArray After Sorting ->");
    printArray();
  }
}
 OUTPUT of the above code
Array Before Sorting-> 10 5 100 1 10000 50 25
Array After Sorting -> 1 5 10 25 50 100 10000

Explanation of the code

  • The doSort() method holds the recursive sorting logic. It is given the first index, low, and the last index, high, of the sub-list it has to sort. It partitions that sub-list, and then calls itself for the part before the pivot and for the part after the pivot.
  • The boundary condition for the recursion is low < high. A sub-list with a single item, or with no items, is already sorted and the method returns without doing anything.
  • The partition() method implements the Lomuto partition scheme. It takes the last item as the pivot, moves every item smaller than the pivot to the left of boundary, and at the end swaps the pivot into the boundary position. It returns the index at which the pivot was placed.
  • The swap() method exchanges the two items at the indexes passed to it.
  • The main() method orchestrates the sorting. It calls doSort() for the whole list, i.e. from index 0 to length - 1.
  • The instance element intArray[] holds the list to be sorted.

Quick Sort's partitions as printed by the program

To see the partitions which were described in the walkthrough above, the next program prints the list after every call to partition(). The sorting logic is the same as before.
Quick Sort printing every partition
package com.javabrahman.algorithms.sorts;
import java.util.Arrays;
public class QuickSortTrace {
  static int intArray[] = { 10, 5, 100, 1, 10000, 50, 25 };

  public static void doSort(int low, int high) {
    if (low < high) {
      int pivot = intArray[high];
      int pivotIndex = partition(low, high);
      System.out.println("Partitioned index " + low + " to " + high + " around pivot " + pivot
          + " -> " + Arrays.toString(intArray) + ", pivot is now at index " + pivotIndex);
      doSort(low, pivotIndex - 1);
      doSort(pivotIndex + 1, high);
    }
  }

  public static int partition(int low, int high) {
    int pivot = intArray[high];
    int boundary = low;
    for (int current = low; current < high; current++) {
      if (intArray[current] < pivot) {
        swap(current, boundary);
        boundary++;
      }
    }
    swap(boundary, high);
    return boundary;
  }

  public static void swap(int first, int second) {
    int temp = intArray[first];
    intArray[first] = intArray[second];
    intArray[second] = temp;
  }

  public static void main(String args[]) {
    System.out.println("Array Before Sorting -> " + Arrays.toString(intArray));
    doSort(0, intArray.length - 1);
    System.out.println("Array After Sorting  -> " + Arrays.toString(intArray));
  }
}
 OUTPUT of the above code
Array Before Sorting -> [10, 5, 100, 1, 10000, 50, 25]
Partitioned index 0 to 6 around pivot 25 -> [10, 5, 1, 25, 10000, 50, 100], pivot is now at index 3
Partitioned index 0 to 2 around pivot 1 -> [1, 5, 10, 25, 10000, 50, 100], pivot is now at index 0
Partitioned index 1 to 2 around pivot 10 -> [1, 5, 10, 25, 10000, 50, 100], pivot is now at index 2
Partitioned index 4 to 6 around pivot 100 -> [1, 5, 10, 25, 50, 100, 10000], pivot is now at index 5
Array After Sorting  -> [1, 5, 10, 25, 50, 100, 10000]
The output shows the same 4 partitions as the walkthrough. After each partition the pivot is at its final index, and the later partitions work only on the items to its left or to its right.

Hoare partitioning

The Lomuto scheme is easy to understand, but it is not the only way to partition. The original scheme, given by Tony Hoare who invented Quick Sort, uses two pointers which start at the two ends of the sub-list and move towards each other -
  1. A value is chosen as the pivot. The program below takes the middle item.
  2. The left pointer moves to the right until it finds an item which is not smaller than the pivot.
  3. The right pointer moves to the left until it finds an item which is not greater than the pivot.
  4. If the two pointers have not met, the two items are on the wrong sides, so they are swapped, and the pointers continue moving.
  5. When the pointers meet or cross, the partitioning is over. All the items up to the meeting point are less than or equal to the pivot, and all the items after it are greater than or equal to the pivot.
Quick Sort with Hoare partitioning
package com.javabrahman.algorithms.sorts;
public class QuickSortHoare {
  static int intArray[] = { 10, 5, 100, 1, 10000, 50, 25 };

  public static void doSort(int low, int high) {
    if (low < high) {
      int split = partition(low, high);
      doSort(low, split);
      doSort(split + 1, high);
    }
  }

  public static int partition(int low, int high) {
    int pivot = intArray[low + (high - low) / 2];
    int left = low - 1;
    int right = high + 1;
    while (true) {
      do {
        left++;
      } while (intArray[left] < pivot);
      do {
        right--;
      } while (intArray[right] > pivot);
      if (left >= right) {
        return right;
      }
      int temp = intArray[left];
      intArray[left] = intArray[right];
      intArray[right] = temp;
    }
  }

  public static void printArray() {
    for (int i = 0; i < intArray.length; i++) {
      System.out.print(" " + intArray[i]);
    }
  }

  public static void main(String args[]) {
    System.out.print("Array Before Sorting->");
    printArray();
    doSort(0, intArray.length - 1);
    System.out.print("\nArray After Sorting ->");
    printArray();
  }
}
 OUTPUT of the above code
Array Before Sorting-> 10 5 100 1 10000 50 25
Array After Sorting -> 1 5 10 25 50 100 10000

Explanation of the Hoare partitioning code

  • The partition() method starts left one place before the sub-list and right one place after it, because each pointer is moved first and compared afterwards.
  • The two do-while loops move the pointers inwards. The items they stop at are swapped, and the outer loop continues until left is no longer less than right.
  • The method returns right, which is the last index of the left part. Unlike in the Lomuto scheme, the pivot is not necessarily at this index. So doSort() makes its recursive calls for low to split and for split + 1 to high, i.e. the item at the returned index is included in the left part.
  • Hoare partitioning does fewer swaps than Lomuto partitioning on average, as it only swaps a pair of items when both are on the wrong side. It also does not swap anything when all the items are equal.

Choice of pivot and the worst case of Quick Sort

Quick Sort is fast when every partition divides the sub-list into two parts of nearly the same size. The list is then halved again and again, and only a few levels of recursion are needed. The opposite happens when the pivot is the smallest or the largest item of the sub-list. One part is then empty, the other part has all the remaining items, and the sub-list becomes smaller by just one item with every partition.

Best and worst case of quick sort - when the pivot divides the list into two halves the recursion is a balanced tree of only log n levels; when the pivot is always the smallest or the largest item each partition removes just one item and the recursion becomes a chain of n levels With the last item as the pivot, this worst case occurs for a list which is already sorted: the last item is always the largest. The common ways of choosing the pivot are -
  • Last (or first) item - the simplest choice, but it gives the worst case for sorted and reverse-sorted lists.
  • Middle item - works very well for sorted lists, as the middle item of a sorted list divides it exactly into halves.
  • Random item - no particular order of the input can cause the worst case every time.
  • Median-of-three - the first, the middle and the last item are looked at, and the one which is neither the smallest nor the largest of the three is taken as the pivot.
The next program sorts a list of 1000 numbers with each of these four choices, and counts the comparisons made while partitioning and the deepest level of recursion reached. It does this once for a shuffled list and once for an already sorted list.
Counting comparisons for different pivot choices
package com.javabrahman.algorithms.sorts;
import java.util.Random;
public class QuickSortPivots {
  static int intArray[];
  static long comparisons;
  static int maxDepth;
  static String pivotChoice;
  static Random random = new Random(42);

  public static void doSort(int low, int high, int depth) {
    if (low < high) {
      maxDepth = Math.max(maxDepth, depth);
      choosePivot(low, high);
      int pivotIndex = partition(low, high);
      doSort(low, pivotIndex - 1, depth + 1);
      doSort(pivotIndex + 1, high, depth + 1);
    }
  }

  // moves the chosen pivot to the last position, where partition() expects it
  public static void choosePivot(int low, int high) {
    int middle = low + (high - low) / 2;
    if (pivotChoice.equals("middle")) {
      swap(middle, high);
    } else if (pivotChoice.equals("random")) {
      swap(low + random.nextInt(high - low + 1), high);
    } else if (pivotChoice.equals("median-of-three")) {
      if (intArray[middle] < intArray[low]) swap(middle, low);
      if (intArray[high] < intArray[low]) swap(high, low);
      if (intArray[middle] < intArray[high]) swap(middle, high);
    }
  }

  public static int partition(int low, int high) {
    int pivot = intArray[high];
    int boundary = low;
    for (int current = low; current < high; current++) {
      comparisons++;
      if (intArray[current] < pivot) {
        swap(current, boundary);
        boundary++;
      }
    }
    swap(boundary, high);
    return boundary;
  }

  public static void swap(int first, int second) {
    int temp = intArray[first];
    intArray[first] = intArray[second];
    intArray[second] = temp;
  }

  public static void measure(String input, String choice) {
    int size = 1000;
    intArray = new int[size];
    for (int i = 0; i < size; i++) {
      intArray[i] = i + 1;
    }
    if (input.equals("shuffled")) {
      Random shuffler = new Random(7);
      for (int i = size - 1; i > 0; i--) {
        swap(i, shuffler.nextInt(i + 1));
      }
    }
    pivotChoice = choice;
    comparisons = 0;
    maxDepth = 0;
    doSort(0, size - 1, 1);
    System.out.printf("%-9s %-16s comparisons: %7d   recursion depth: %4d%n", input, choice, comparisons, maxDepth);
  }

  public static void main(String args[]) {
    for (String input : new String[] { "shuffled", "sorted" }) {
      for (String choice : new String[] { "last", "middle", "random", "median-of-three" }) {
        measure(input, choice);
      }
    }
  }
}
 OUTPUT of the above code
shuffled  last             comparisons:   10942   recursion depth:   21
shuffled  middle           comparisons:   11724   recursion depth:   23
shuffled  random           comparisons:   10734   recursion depth:   19
shuffled  median-of-three  comparisons:    8892   recursion depth:   15
sorted    last             comparisons:  499500   recursion depth:  999
sorted    middle           comparisons:    7987   recursion depth:    9
sorted    random           comparisons:   13313   recursion depth:   24
sorted    median-of-three  comparisons:    7987   recursion depth:    9

Explanation of the output

  • For the shuffled list all four choices do well. They need around 9,000 to 12,000 comparisons, and the recursion goes 15 to 23 levels deep.
  • For the sorted list with the last item as the pivot, the number of comparisons jumps to 499,500 and the recursion goes 999 levels deep. This is the worst case: 999 + 998 + ... + 1 comparisons, which is n(n-1)/2 for n = 1000.
  • With the middle item or the median-of-three as the pivot, the sorted list becomes the best case. Every partition divides the sub-list exactly into halves, which needs 7,987 comparisons and only 9 levels of recursion.
  • The random pivot is not affected by the order of the input. Its numbers for the sorted list are close to those for the shuffled list.
  • The method choosePivot() only moves the chosen pivot to the last position, so that the same partition() method can be used for all four choices.

Big Oh Complexity of Quick Sort Algorithm

Every partition reads all the items of its sub-list once, so all the partitions at one level of the recursion together make about n comparisons. The complexity thus depends on the number of levels -
  • Best and average case - when the partitions are reasonably balanced there are about log n levels, and the complexity of Quick Sort is O(n log n).
  • Worst case - when every partition removes just one item there are n levels, and the complexity becomes O(n2). A good choice of pivot makes this case very unlikely.
  • Space - Quick Sort does not need a second list, but every level of recursion uses space on the call stack. This is O(log n) for balanced partitions and O(n) in the worst case.
  • Stability - Quick Sort is not a stable sort. Two items with equal values may not remain in their original order, as items are swapped across long distances.

Summary

In this tutorial on Quick Sort algorithm in Java we understood how the algorithm sorts by partitioning a list around a pivot, went through a step-by-step walkthrough of sorting a 7-number list, saw the Java code for Quick Sort with Lomuto partitioning and with Hoare partitioning along with their explanations, measured how the choice of pivot decides between the best and the worst case, and finally looked at the Big Oh complexity of the algorithm.