Skip to main content

Quick Sort in C++

This section explains how the "divide and conquer" strategy of Quick Sort is implemented in C++. The logic is split into two primary functions: quickSort() which handles the recursive division, and partition() which rearranges the array around a pivot.

The C++ Code Implementation

Here is the complete code for a Quick Sort implementation using std::vector.

#include <iostream>
#include <vector>
#include <utility> // For std::swap

// Utility function to print a vector
void printVector(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// This function takes the last element as pivot, places the pivot element
// at its correct position in the sorted array, and places all smaller
// elements to the left of the pivot and all greater elements to the right.
int partition(std::vector<int>& arr, int low, int high) {
    // Choose the last element as the pivot
    int pivot = arr[high]; 
    
    // Index of the smaller element
    int i = (low - 1); 

    for (int j = low; j <= high - 1; j++) {
        // If the current element is smaller than the pivot
        if (arr[j] < pivot) {
            i++; // Increment index of smaller element
            std::swap(arr[i], arr[j]);
        }
    }
    // Place the pivot in its correct position
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// The main recursive function that implements Quick Sort
void quickSort(std::vector<int>& arr, int low, int high) {
    // Base case: if the array has 1 or 0 elements, it's already sorted
    if (low < high) {
        // pi is the partitioning index, arr[pi] is now at the right place
        int pi = partition(arr, low, high);

        // Separately sort elements before partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Main driver function
int main() {
    std::vector<int> data = {6, 5, 3, 1, 8, 7, 2, 4};
    std::cout << "Original array: ";
    printVector(data);

    quickSort(data, 0, data.size() - 1);

    std::cout << "Sorted array:   ";
    printVector(data);

    return 0;
}

Output

Original array: 6 5 3 1 8 7 2 4 
Sorted array:   1 2 3 4 5 6 7 8

Code Breakdown

The quickSort() Function: The Recursive Driver

This function orchestrates the "Divide" phase of the algorithm.

  1. Base Case: The recursion continues as long as low < high. If low >= high, it means the sub-array has one or zero elements, which is inherently sorted.
  2. Partition: It calls the partition() function. This function rearranges the sub-array and returns the index pi where the pivot element is now correctly placed.
  3. Recurse: It calls itself twice for the two sub-arrays created by the partition: one for the elements to the left of the pivot (low to pi - 1) and one for the elements to the right (pi + 1 to high). Note that the pivot at index pi is excluded from the recursive calls because it's already in its final sorted position.

The partition() Function: The Rearranger

This function is where the key logic of rearranging elements occurs. It implements the "Conquer" step by sorting one element (the pivot) at a time.

  1. Pivot Selection: It selects the last element of the sub-array (arr[high]) as the pivot.
  2. Rearranging Loop: It maintains an index i which represents the boundary between elements smaller than the pivot and elements larger than it. It iterates through the sub-array with another index j. If it finds an element arr[j] that is smaller than the pivot, it swaps arr[j] with the element at the boundary arr[i + 1], effectively expanding the "smaller than pivot" section.
  3. Final Pivot Placement: After the loop finishes, all elements smaller than the pivot are at the beginning of the sub-array. The pivot (still at arr[high]) is then swapped with the element at arr[i + 1]. This places the pivot exactly where it belongs in the sorted array.
  4. Return Index: The function returns the new index of the pivot (i + 1), so the quickSort function knows where to split the array for its next recursive calls.
Back to top