quicksort algorithm in C++

quick_sort.cc

#include <iostream>
#include <vector>

/**
 * Partitions the given vector of integers into two parts based on a pivot
 * value. The pivot value is chosen as the "first" element of the vector. Elements
 * greater than the pivot value are moved to the right side of the pivot, while
 * elements less than or equal to the pivot value are moved to the left side.
 *
 * @param nums The vector of integers to be partitioned.
 * @param low The starting index of the partition.
 * @param high The ending index of the partition.
 * @return The index of the pivot element after partitioning.
 */
int partition2(std::vector<int> &nums, int low, int high)
{
    // when pivot is the first item
    int pivot_val = nums[low];
    int pivot_idx = high + 1;

    for (int i = high; i >= low; --i)
    {
        if (nums[i] > pivot_val)
        {
            pivot_idx--;
            std::swap(nums[i], nums[pivot_idx]);
        }
    }

    pivot_idx--;
    std::swap(nums[pivot_idx], nums[low]);

    return pivot_idx;
}

/**
 * Partitions the given array around a pivot element.
 * The pivot element is chosen as the last element of the array.
 *
 * @param arr The array to be partitioned.
 * @param low The starting index of the partition.
 * @param high The ending index of the partition.
 * @return The index of the pivot element after partitioning.
 */
int partition(std::vector<int> &arr, int low, int high)
{
    // keeps track of where the pivot will eventually be placed
    int pivot_idx = low - 1;

    for (int i = low, pivot_val = arr[high]; i != high; ++i)
    {
        // place all elements less than pivot to the left
        if (arr[i] < pivot_val)
        {
            pivot_idx++;
            std::swap(arr[pivot_idx], arr[i]);
        }
    }

    // place pivot in the correct position
    pivot_idx++;
    std::swap(arr[pivot_idx], arr[high]);

    return pivot_idx;
}

/**
 * Sorts the given vector using the quicksort algorithm.
 *
 * @param arr The vector to be sorted.
 * @param low The starting index of the range to be sorted.
 * @param high The ending index of the range to be sorted.
 */
void quick_sort(std::vector<int> &arr, int low, int high)
{
    if (!(low < high))
    { // "low" should always be less than "high"
        return;
    }

    // calculate pivot's index
    int pivot = partition(arr, low, high);

    // place all elements less than pivot to the left
    quick_sort(arr, low, pivot - 1);

    // place all elements greater than pivot to the right
    quick_sort(arr, pivot + 1, high);
}

/**
 * @brief Entry point of the program.
 *
 * This function demonstrates the usage of the quick_sort algorithm by sorting
 * a vector of integers in ascending order.
 *
 * @return 0 on successful execution.
 */
int main(void)
{
    std::vector<int> arr = {2,  6, 6,  4,  8,  12, 3,  7,  1,  9,  5,  11, 10, 13, 15,
                            14, 0, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27};

    std::cout << "Original array: ";
    for (auto &c : arr)
    {
        std::cout << c << " ";
    }

    quick_sort(arr, 0, arr.size() - 1);

    std::cout << "\nSorted array: ";
    for (auto &c : arr)
    {
        std::cout << c << " ";
    }

    return 0;
}