Quicksort

Quicksort is a divide-and-conquer algorithm that works by selecting a “pivot” element from the list. The pivot element is used to partition the list into a right and left sub-list. All the items in the right sub-list are less than the pivot, and all the items in the left sub-list are greater than the pivot. Structurally, the algorithm is driven by the partition subroutine which performs the pivot selection and reordering.

By recursively applying the Quicksort algorithm on the left and right sub-lists, we sort the entire list.

Time complexity analysis

As with most general divide-and-conquer algorithms, it becomes quite apparent that the expected time complexity of Quicksort is . This is because we split the list times, and each call to partition takes time.

However, the time complexity of Quicksort is actually dependent on the pivot selection strategy. The textbook method of selecting the pivot element is simply grabbing the last element in the list. This decision introduces a worst case scenario where the list is already sorted. The reason the expected time complexity grows to is because in the worst case scenario, the partition leaves us with one list of size , and the other list of size . This means it will require partitions to work through the entire list.

A better strategy is to randomly select the pivot element. For a sufficiently large list, this will reduce the chances of picking the worst case scenario as the pivot. Mathematically the probability of getting the worst case expressed by . This means that the expected time complexity of Quicksort is because the probablity of picking the worst case goes towards zero as grows (i.e., ).

Space complexity analysis

Because Quicksort doesn’t allocate any additional memory space, the space complexity is constant of .

Implementation

This first implementation uses the highest index as the pivot, possibly incurring the worst case scenario as described above. Below is the implementation using a randomized pivot.

Standard Quicksort in Java

package jun.codes.interviews.sort;

public class Quicksort {
  public static <T extends Comparable<T>> void sort(T[] xs) {
    sort(xs, 0, xs.length - 1);
  }

  public static <T extends Comparable<T>> void sort(T[] xs, int low, int high) {
    // If there are more elements to sort, then we need to recursively sort the
    // relevant sub-array
    if (low < high) {
      int pivot = partition(xs, low, high);
      // Recurse down on each side of the partition's pivot element index
      sort(xs, low, pivot - 1);
      sort(xs, pivot + 1, high);
    }
  }

  public static <T extends Comparable<T>> int partition(T[] xs, int low, int high) {
    // Pick a pivot element from the array, in this case the last element. We
    // will see how the pivot affects the performance of the algorithm.
    T pivot = xs[high];

    // We maintain an index to keep a track of the position the pivot element
    // should be moved to.
    int index = low - 1;

    // For each element in the array, compare it to the pivot. If the element is
    // less than the pivot, then we swap positions with the current index. This
    // effectively moves the element to the left of the pivot.
    for (int i = low; i < high; i++) {
      if (xs[i].compareTo(pivot) < 0) {
        index++;
        // Swap the current element with the element at the index
        T tmp = xs[i];
        xs[i] = xs[index];
        xs[index] = tmp;
      }
    }

    // Swap the pivot with the element at the index
    T tmp = xs[high];
    xs[high] = xs[index + 1];
    xs[index + 1] = tmp;

    // Return the index of the pivot element
    return index + 1;
  }
}

When picking the pivot randomly, we simply re-use the code for the first partition implementation. We just swap the randomly selected pivot with the last element in the list, effectively making the pivot the random element.

Randomized Quicksort in Java

package jun.codes.interviews.sort;

import java.util.Random;

public class RandomizedQuicksort {
  public static <T extends Comparable<T>> void sort(T[] xs) {
    sort(xs, 0, xs.length - 1);
  }

  public static <T extends Comparable<T>> void sort(T[] xs, int low, int high) {
    if (low < high) {
      int pivot = partition(xs, low, high);
      sort(xs, low, pivot - 1);
      sort(xs, pivot + 1, high);
    }
  }

  public static <T extends Comparable<T>> int partition(T[] xs, int low, int high) {
    // We now pick a completely random element as the pivot.
    int pivot = new Random().nextInt(low, high + 1);

    // Swap the pivot element with the last element in the array
    T temp = xs[high];
    xs[high] = xs[pivot];
    xs[pivot] = temp;

    return Quicksort.partition(xs, low, high);
  }
}

Further reading

The relevant material in Introduction to Algorithms 4th edition can be found starting on page 182.

• Wikipedia: Quicksort