It works by first selecting a ‘pivot’ element, then re-ordering either side of the list so that everything before the pivot is less than the pivot and everything after is greater. Quicksort is then called recursively on either side of the pivot.

Despite quicksort having a worst-case performance of O(n^2), it is sometimes regarded at the same level performance-wise as O(n \log n) sorts like merge sort or heapsort. This is due to its average case being O(n \log n), it will often perform even better in practice than the O(n \log n) sorts.

Complexity

Time			Space
Worst case	Best case	Average case	Worst case
O(n^2)	O(n \log n)	O(n \log n)	O(\log n) auxiliary

Partition

The partition function is where the actual sorting happens. The image illustrates the function in action, using the right-most value as the pivot (5).

The function tracks three variables; i, m and p. Here is what each variable does:

• i - controlled by the for loop, it indicates the current index being considered.
• m - short for middle, represents the index in which all values to the left of it are less than the pivot.
• p - short for pivot, this is swapped at the end of the procedure with the item in the index m+1. This ensures that all values to the left of the pivot are less than the pivot and all to the right are greater

The pivot

The choice of the pivot can have a great impact on the worst-case running time, particularly when using very unimaginative pivots like the left-most and right-most items in the list. If the pivot chosen ends up being either the highest or lowest value in the list, this will lead to worst case behaviour. More specifically, worst-case behaviour occurs when each partition returns two sub-lists, containing n-1 and 0 items. To achieve best case the pivot needs to lie in the middle of the list, so the median value would be the best choice.

A simple method to have a much better shot at the average case of O(n \log n), is to randomise the pivot value. The randomised pivot function typically swaps a random element with the last element and then proceeds to run the regular partition procedure. This is demonstrated in the code section below in the randomSort function.

Parallelisation

The chosen pivot has a great impact of how well quicksort can be parallelised. Consider the list [1,2,3,4,5], if the right-most value is chosen as the pivot every time, then the sub-list to the right of the pivot will always be the empty set. This is where a random pivots help, or using some other method of choosing a value close to the median as the pivot.

Visualisation

Use the controls to playback quicksort on the data set.

See the Sorting Visualiser page for more visualisations.

Code

public class Quicksort<T> : IGenericSortingAlgorithm<T> where T : IComparable
{
    private Random _random;
    private PartitionDelegate _partitionFunction;

    public delegate int PartitionDelegate(IList<T> list, int left, int right);

    public Quicksort(bool randomPartition) {
        if (randomPartition) {
            _random = new Random();
            _partitionFunction = PartitionRandom;
        } else {
            _partitionFunction = PartitionRight;
        }
    }

    public void Sort(IList<T> list) {
        Sort(list, 0, list.Count - 1);
    }
        
    private void Sort(IList<T> list, int left, int right) {
        if (left < right) {
            int pivot = _partitionFunction(list, left, right);
            Sort(list, left, pivot - 1);
            Sort(list, pivot + 1, right);
        }
    }

    private int PartitionRandom(IList<T> list, int left, int right) {
        int pivot = left + _random.Next(right - left);
        Swap(list, right, pivot);
        return PartitionRight(list, left, right);
    }

    private int PartitionRight(IList<T> list, int left, int right) {
        T pivot = list[right];
        int mid = left;
        for (int i = mid; i < right; i++) {
            if (list[i].CompareTo(pivot) <= 0) {
                Swap(list, i, mid++);
            }
        }
        Swap(list, right, mid);
        return mid;
    }

    private void Swap(IList<T> list, int a, int b)
    {
        if (a != b) {
            T temp = list[a];
            list[a] = list[b];
            list[b] = temp;
        }
    }
}

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

    private static <T extends Comparable<T>> void sort(
            T[] array, int left, int right) {
        if (left < right) {
            int pivot = partition(array, left, right);
            sort(array, left, pivot - 1);
            sort(array, pivot + 1, right);
        }
    }

    private static <T extends Comparable<T>> int partition(
            T[] array, int left, int right) {
        T pivot = array[right];
        int mid = left;
        for (int i = mid; i < right; i++) {
            if (array[i].compareTo(pivot) <= 0) {
                swap(array, i, mid++);
            }
        }
        swap(array, right, mid);
        return mid;
    }

    private static <T extends Comparable<T>> void swap(
            T[] array, int a, int b) {
        if (a != b) {
            T temp = array[a];
            array[a] = array[b];
            array[b] = temp;
        }
    }



    // Random pivot implementation below

    private static Random random = new Random();

    public static <T extends Comparable<T>> void randomSort(T[] array) {
        randomSort(array, 0, array.length - 1);
    }

    private static <T extends Comparable<T>> void randomSort(
            T[] array, int left, int right) {
        if (left < right) {
            int pivot = randomPartition(array, left, right);
            randomSort(array, left, pivot - 1);
            randomSort(array, pivot + 1, right);
        }
    }

    private static <T extends Comparable<T>> int randomPartition(
            T[] array, int left, int right) {
        int pivot = left + random.nextInt(right - left);
        swap(array, right, pivot);
        return partition(array, left, right);
    }
}

/**
 * Sorts an array using quicksort.
 * @param {Array} array The array to sort.
 * @param {number} left The index to sort from.
 * @param {number} right The index to sort to.
 * @param {function} compare The compare function.
 * @param {function} swapObserver A function to call when the swap operation is
 * performed. This can be used to listen in on internals of the algorithm.
 * @returns The sorted array.
 */
function sort(array, left, right, compare, swap) {
  if (left < right) {
    var pivot = partitionRandom(array, left, right, compare, swap);
    sort(array, left, pivot - 1, compare, swap);
    sort(array, pivot + 1, right, compare, swap);
  }
  return array;
}

/**
 * Partition the array by selecting a random pivot and moving all elements less
 * than the pivot to a lesser index and all elements greater than the pivot to a
 * greater index.
 * @param {Array} array The array to sort.
 * @param {number} left The index to sort from.
 * @param {number} right The index to sort to.
 * @param {function} compare The compare function.
 * @param {function} swapObserver A function to call when the swap operation is
 * performed. This can be used to listen in on internals of the algorithm.
 * @returns The pivot.
 */
function partitionRandom(array, left, right, compare, swap) {
  var pivot = left + Math.floor(Math.random() * (right - left));
  if (pivot !== right) {
    swap(array, right, pivot);
  }
  return partitionRight(array, left, right, compare, swap);
}

/**
 * Partition the array using the right most element as the pivot by moving all
 * elements less than the pivot to a lesser index and all elements greater than
 * the pivot to a greater index.
 * @param {Array} array The array to sort.
 * @param {number} left The index to sort from.
 * @param {number} right The index to sort to.
 * @param {function} compare The compare function.
 * @param {function} swapObserver A function to call when the swap operation is
 * performed. This can be used to listen in on internals of the algorithm.
 * @returns The pivot.
 */
function partitionRight(array, left, right, compare, swap) {
  var mid = left;

  for (var i = mid; i < right; i++) {
    if (compare(array, i, right) <= 0) {
      if (i !== mid) {
        swap(array, i, mid);
      }
      mid++;
    }
  }
  if (right !== mid) {
    swap(array, right, mid);
  }

  return mid;
}

def default_compare(a, b):
  if a < b:
    return -1
  elif a > b:
    return 1
  return 0

def sort(array, compare=default_compare):
  return inner_sort(array, 0, len(array) - 1, compare)

def inner_sort(array, left, right, compare=default_compare):
  if left < right:
    pivot = partition_random(array, left, right, compare)
    inner_sort(array, left, pivot - 1, compare)
    inner_sort(array, pivot + 1, right, compare)
  return array

def partition_random(array, left, right, compare):
  pivot = left + math.floor(random.random() * (right - left))
  if pivot != right:
    array[right], array[pivot] = array[pivot], array[right]
  return partition_right(array, left, right, compare)

def partition_right(array, left, right, compare):
  pivot = array[right]
  mid = left
  for i in range(mid, right):
    if compare(array[i], pivot) <= 0:
      if i != mid:
        array[i], array[mid] = array[mid], array[i]
      mid += 1
  if right != mid:
    array[right], array[mid] = array[mid], array[right]
  return mid

module Quicksort
  # Sorts an array using quicksort.
  def self.sort(array, compare = lambda { |a, b| a <=> b })
    self.inner_sort(array, 0, array.length - 1, compare)
  end

private

  # Sorts an array using quicksort.
  def self.inner_sort(array, left, right, compare)
    if left < right
      pivot = partition_random(array, left, right, compare)
      self.inner_sort(array, left, pivot - 1, compare)
      self.inner_sort(array, pivot + 1, right, compare)
    end
  end

  # Partition the array by selecting a random pivot and moving all elements less
  # than the pivot to a lesser index and all elements greater than the pivot to a
  # greater index.
  def self.partition_random(array, left, right, compare)
    pivot = left + (rand * (right - left)).floor
    if pivot != right
      array[right], array[pivot] = array[pivot], array[right]
    end
    return partition_right(array, left, right, compare)
  end

  # Partition the array using the right most element as the pivot by moving all
  # elements less than the pivot to a lesser index and all elements greater than
  # the pivot to a greater index.
  def self.partition_right(array, left, right, compare)
    pivot = array[right]
    mid = left
    (mid..right - 1).each do |i|
      if compare.call(array[i], pivot) <= 0
        if i != mid
          array[i], array[mid] = array[mid], array[i]
        end
        mid += 1
      end
    end
    if right != mid
      array[right], array[mid] = array[mid], array[right]
    end
    return mid
  end
end

Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.

 

More posts tagged Sorting