Quick sort

Overview

Quick sort, often simply referred to as “quick”, was developed by Sir Tony Hoare in 1959. It has since become one of the most widely used and studied algorithms due to its efficiency and simplicity.

At its core, quick sort is a comparison-based sorting algorithm that operates on the divide-and-conquer principle. It involves selecting a ‘pivot’ element from the list and partitioning the other elements into two sublists according to whether they are less than or greater than the pivot. The same process is then repeated recursively on each sublist until it is empty or contains only one element.

Characteristics

  • Divide and conquer algorithm

  • Comparison based (general purpose)

  • Recursive

  • In-place

  • Efficient

  • Unstable - relative order of equal elements is not preserved

Algorithm Details

  • We employs the zyBook’s version. There are many other implementations!

  • Quick partition algorithm

    • The core of quick sort

    • Steps

      1. Pick an element, called a pivot, from the list.

      2. Use the pivot to partition the list into two sublists.

      3. Reorder the list in the process so that all elements less than the pivot come before the pivot, and all elements greater than the pivot come after it.

      4. Return the location of the partition.

    • Partition the list

      • Lomuto’s partition scheme (FYI)

      • Hoare’s partition scheme

        1. Let two cursor indices to point to the first - 1 and last + 1 positions of the list respectively.

        2. Keep moving the left cursor to the right until it points to an element greater and equal than the pivot.

        3. Keep moving the right cursor to the left until it points to an element less and equal than the pivot.

        4. If the left cursor meets or passes the right cursor, the partition is complete. Return the right cursor.

        5. Swap the elements pointed by the two cursors.

        6. Move both cursors one more step

        7. Repeat steps 2-6 until the partition is complete (step 4 returns).

    • Example algorithm

      • Hoare’s partition scheme

      • Middle element as pivot

      int quickPartition(int *arr, int low, int high) {
  int mid = (high + low) / 2;
  // int mid = low + (high - low) / 2;
  int pivot = arr[mid];
  while (true) {
    while (arr[low] < pivot) ++low;
    while (arr[high] > pivot) --high;
    if (low >= high) break;
    swap(arr[low], arr[high]);
    ++low;
    --high;
  }
  return high;
}

  • Quick sort algorithm (recursive, in-place)

    1. If the list contains only one element or is empty, return.

    2. Call quick partition algorithm to partition the list into two sublists.

    3. Recursively call quick sort on both sublists.

    void quicksort(int *arr, int size) {
  quicksortHelper(arr, 0, size - 1);
}

void quicksortHelper(int *arr, int low, int high) {
  if (low >= high) return;
  int part = quickPartition(arr, low, high);
  quicksortHelper(arr, low, part);
  quicksortHelper(arr, part + 1, high);
}

  • Variations of quick sort

    • Select a pivot

      • First element as pivot

      • Last element as pivot

      • Median of first, middle, and last element as pivot (State of art)

      • Median of several random elements as pivot

      • Random element as pivot

    • Moving the cursor

      • Lomuto’s partition scheme - i and j move in the same direction

      • Hoare’s partition scheme - i and j move in opposite directions

Example

This example demonstrates the quick sort algorithm using the zybook’s variation of Hoare’s partition scheme. You may try to use this format in the quiz or exam.

  • Given an int array {42, 7, 85, 23, 64, 91, 9, 73, 18, 56}

  • First round of partitioning

// low is 0, high is 9 initially
middle = (low + high) / 2 = 4
pivot = arr[middle] = 64

{42, 7, 85, 23, 64, 91, 9, 73, 18, 56} find position
        l                          h
{42, 7, 56, 23, 64, 91, 9, 73, 18, 85} swap 85, 56, and move by 1
            l                  h
{42, 7, 56, 23, 64, 91, 9, 73, 18, 85} find position (hit pivot)
                l              h
{42, 7, 56, 23, 18, 91, 9, 73, 64, 85} swap 64, 18, and move by 1
                    l      h
{42, 7, 56, 23, 18, 91, 9, 73, 64, 85} find position
                    l   h
{42, 7, 56, 23, 18, 9, 91, 91, 64, 85} swap 91, 9, and move by 1
                    h  l
h <= l, return h
left section: index low to h
right section: index h + 1 to high

Complexity

  • Time

    • \(\Theta(n \log n)\) average case

    • \(\Theta(n^2)\) worst case

  • Space

    • \(\Theta(\log n)\) average case

    • \(\Theta(n)\) worst case

  • Improvement attempts

    • Pivot selection

      • Randomized quick sort

      • Median of three

    • Shuffling the list before sorting

Visualization Website

Unfortunately, the visualization websites are all using different configurations and are not compatible with our demonstration.