Quick Sort

Section 26.12 Quick Sort

With our partition algorithm in place, we can now implement . Here is the pseudocode:

QuickSort(list, start, end):
  if start >= end:
    return list  // size 0/1 already sorted
  else:
    pivotLocation = Partition(list)
    QuickSort(0 to pivotLocation - 1)  // Sort the first half
    QuickSort(pivotLocation to end)    // Sort the second half

Implemented in C++ for a vector, it looks like this:

🔗

Listing 26.12.1.

🔗

#include <iostream>
#include <vector>
using namespace std;

#include "vector-helpers.h"

// Other helpers (defined below main)
template<typename T>
int partition(vector<T>& vec, int start, int end);

string spaces(bool add = true, bool remove = false);

// Recursive quick sort function
template<typename T>
void quickSort(vector<T>& vec, int start, int end) {
    if (start >= end) {
        return; // Base case: 0-1 items are already sorted
    }
    // Debug output
    cout << spaces() << "quickSort called with start=" << start << ", end=" << end << endl;
    cout << spaces(false) << vectorToString(vec, start, end) << endl;
    
    int pivotIndex = partition(vec, start, end);           // Partition the two halves

quickSort(vec, start, pivotIndex - 1);       // Sort left half
    quickSort(vec, pivotIndex + 1, end);     // Sort right half
    
    // Debug output
    cout << spaces(false) << "quickSort ending start=" << start << ", end=" << end << endl;
    cout << spaces(false) << vectorToString(vec, start, end) << endl;
    spaces(false, true);
}

// Wrapper function to initiate quick sort
template<typename T>
void quickSort(vector<T>& vec) {
    // Do the sort
    quickSort(vec, 0, vec.size() - 1);
}

int main() {
    vector<int> numbers = {8, 3, 7, 1, 9, 12, 20, 6, 11, 14, 2, 16, 4, 10, 5, 15};
    quickSort(numbers);
    cout << "Sorted array: " << endl;
    cout << vectorToString(numbers) << endl;
}

// Partition the vector segment from start to end
// returns the final index of the pivot
template<typename T>
int partition(vector<T>& vec, int start, int end) {
    T pivotValue = vec.at(start);
    int i = start + 1;
    int j = end;
    while (i <= j) {
        // Move i right until it finds something that belongs on the right
        while (i <= end && vec.at(i) <= pivotValue) {
            i++;
        }
        // Move j left until it finds something that belongs on the left
        while (j >= start && vec.at(j) > pivotValue) {
            j--;
        }
        // Swap items at i and j if i < j
        if (i < j) {
            swap(vec.at(i), vec.at(j));
            // advance i and retreat j since those items are fixed
            i++;
            j--;
        }
    }
    // j will always have the final pivot position
    swap(vec.at(start), vec.at(j));
    return j;
}

// Manage indentation for debug output
string spaces(bool add, bool remove) {
  static string spaces = "";
  if (add) {
      string curSpaces = spaces;
      spaces += " ";
      return curSpaces;
  }
  if (remove) {
      spaces.pop_back();
  }
  return spaces;
}

Again we use a wrapper function quickSort(vector<T>& vec) to start the recursive quick sort function. It means that main does not have to provide the start and end indices.

🔗

Try running this interactive to see how the process plays out. As you do so, pay attention to when elements turn white. Those elements are in their final sorted position. Each partition step places one element (the pivot) into its final sorted position. Quick sort then recursively sorts the left and right partitions around that pivot.

🔗

Activity 26.12.1. QuickSort.

Instructions.

Click "Step" to advance once step or "Play" to run continuously.

🔗

At the top, you can see a description of the current step. On the right, you can see the current call stack.

🔗

This process is not stable. Say you had the partition:

🔗

5 1(A) 1(B) 10 15

The first swap would produce:

🔗

5 15 1(B) 10 1(A)

This reverses the order of the two 1s. Recall that any time elements are swapping across large distance without consideration for other “equal” elements, an algorithm is going to almost certainly be unstable. This is the case for quick sort.

🔗

Checkpoint 26.12.1.

Which statements are true about quick sort?

🔗

Quick sort is a divide-and-conquer algorithm.
Quick sort uses a partitioning step to divide the list into two parts.
Quick sort always partitions the list into two equal sized parts.
Quick sort recursively sorts the left and right partitions around the pivot.
Quick sort is stable.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next