Quicksort in C++

Below is an example of the Quicksort algorithm in C++. See the Quicksort page for more information and implementations.


quicksort in C++

#include <vector>
#include <iostream>

static int partition(std::vector<int> &arr, int startIndex, int endIndex) {
    int pivotIndex = (startIndex + endIndex) / 2;
    int pivotValue = arr[pivotIndex];

    while (true) {
        // start at the FIRST index of the sub-arr and increment
        // FORWARD until we find a value that is > pivotValue
        while (arr[startIndex] < pivotValue) {
            startIndex++;
        }

        // start at the LAST index of the sub-arr and increment
        // BACKWARD until we find a value that is < pivotValue
        while (arr[endIndex] > pivotValue) {
            endIndex--;
        }

        if (startIndex >= endIndex) {
            return endIndex;
        }

        // swap values at the startIndex and endIndex
        int temp = arr[startIndex];
        arr[startIndex] = arr[endIndex];
        arr[endIndex] = temp;
    }
}

void quickSort(std::vector<int> &arr, int startIndex, int endIndex) {
    // verify that the start and end index have not overlapped
    if (startIndex < endIndex) {
        // calculate the pivotIndex
        int pivotIndex = partition(arr, startIndex, endIndex);
        // sort the left sub-arr
        quickSort(arr, startIndex, pivotIndex);
        // sort the right sub-arr
        quickSort(arr, pivotIndex + 1, endIndex);
    }
}

int main() {
    std::vector<int> arr = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
    quickSort(arr, 0, static_cast<int>(arr.size() - 1));
    for (int i; i < arr.size(); i++) {
        std::cout << arr[i];
        if (i < arr.size() - 1) std::cout << ", ";
    }
}

Discussion