Example: Quick Sort using Recursion in C++

// Quick Sort using Recursion
#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

// Function to print the array
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

// Function to partition the array
// It takes the last element as pivot, places the pivot element at its correct
// position in sorted array, and places all smaller (than pivot) to left of
// pivot and all greater elements to right of pivot
int partition(std::vector<int>& arr, int low, int high) {
    // Step 1: Choose the pivot (last element in this case)
    int pivot = arr[high];
    // Index of smaller element and indicates the right position of the pivot found so far
    int i = (low - 1);

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

// The main function that implements QuickSort
// arr[] --> Array to be sorted, low --> Starting index, high --> Ending index
void quickSort(std::vector<int>& arr, int low, int high) {
    // Step 1: Base case for recursion: if low >= high, the sub-array has 0 or 1 elements, so it's already sorted.
    if (low < high) {
        // Step 2: Partitioning index, arr[pi] is now at right place
        int pi = partition(arr, low, high);

        // Step 3: Recursively sort elements before partition and after partition
        quickSort(arr, low, pi - 1);  // Sort the left sub-array
        quickSort(arr, pi + 1, high); // Sort the right sub-array
    }
}

int main() {
    // Step 1: Define an unsorted array
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();

    std::cout << "Original array: ";
    printArray(arr);

    // Step 2: Call quickSort function to sort the array
    quickSort(arr, 0, n - 1);

    std::cout << "Sorted array: ";
    printArray(arr);

    return 0;
}