quick.cpp

#include <iostream>

/**
 * Output the contents of an array.
 *
 * @param array the array of integers to output.
 * @param last the size of the given array, or the "index" (1-based) of the last item in the array.
 * @param first the index (0-based) of the first item in the array.
 */
void print(int array[], int last, int first = 0)
{
    std::cout << "{ ";
    for (int i = first; i < last; i++)
    {
        std::cout << array[i] << (i == last - 1 ? "" : ", ");
    }
    std::cout << " }" << std::endl;
}

/**
 * Compare two integer values, either using greater than or less than.
 *
 * @param a the first integer to compare.
 * @param b the second integer to compare.
 * @param gt if the comparison should be greater than or less than.
 * @return the result of the comparison, as a boolean.
 */
bool compare(int a, int b, bool gt)
{
    if (gt)
        return a > b;
    return a < b;
}

/**
 * Perform an in-place quick sort of an array of integers.
 *
 * @param array the array of integers to sort in-place.
 * @param last the size of the given array, or the "index" (1-based) of the last item in the array.
 * @param first the index (0-based) of the first item in the array.
 * @param mid_pivot whether to use a middle pivot or the first item as the pivot.
 * @param asc whether to sort in ascending or descending order.
 */
void quick_sort(int array[], int last, int first = 0, bool mid_pivot = true, bool asc = true)
{
    std::cout << "Starting: ";
    print(array, last, first);

    // Don't do anything if only one elm, it must be sorted
    if (last - first <= 1)
        return;

    // Choose the pivot (middle of the array, or the first elm)
    int pivot = mid_pivot ? (last - first) / 2 + first : first, done = 0, pointer;
    std::cout << "Pivot initial: " << pivot << std::endl;

    // Swap elms around pivot until nothing to swap, so pivot must then be in the right place
    while (done == 0)
    {
        done = 0;

        // Find first elm on left of pivot that's larger (or smaller for desc) & swap
        pointer = first;
        std::cout << "Left pointer initial: " << pointer << std::endl;
        while (compare(array[pivot], array[pointer], asc) && pointer <= pivot)
        {
            pointer++;
        }
        std::cout << "Left pointer final: " << pointer << std::endl;
        if (pointer != pivot)
        {
            std::cout << "Swap " << pointer << "(" << array[pointer] << ") and "
                      << pivot << "(" << array[pivot] << ")" << std::endl;
            array[pointer] += array[pivot];
            array[pivot] = array[pointer] - array[pivot];
            array[pointer] -= array[pivot];
            pivot = pointer;
        } else {
            done++;
        }
        std::cout << "Pivot after left: " << pivot << std::endl;

        // Find the first elm on the right of the pivot that's smaller (or larger for desc) & swap
        pointer = last - 1;
        std::cout << "Right pointer initial: " << pointer << std::endl;
        while (compare(array[pointer], array[pivot], asc) && pointer >= pivot)
        {
            pointer--;
        }
        std::cout << "Right pointer final: " << pointer << std::endl;
        if (pointer != pivot)
        {
            std::cout << "Swap " << pointer << "(" << array[pointer] << ") and "
                      << pivot << "(" << array[pivot] << ")" << std::endl;
            array[pointer] += array[pivot];
            array[pivot] = array[pointer] - array[pivot];
            array[pointer] -= array[pivot];
            pivot = pointer;
        } else {
            done++;
        }
        std::cout << "Pivot after right: " << pivot << std::endl;
    }
    std::cout << "Ending: ";
    print(array, last, first);

    // Recursively quick sort the elms to the left & right of the pivot (pivot elm is now in the right place)
    quick_sort(array, pivot, 0, mid_pivot, asc);
    quick_sort(array, last, pivot + 1, mid_pivot, asc);

    std::cout << "Final: ";
    print(array, last, first);
}

/**
 * Runs the program.
 *
 * @return the exit code of the program, as an integer.
 */
int main()
{
    int test1[5] = {30, 400, 20, 12, 10};
    std::cout << std::endl << "Quick asc" << std::endl;
    print(test1, 5);
    quick_sort(test1, 5);
    print(test1, 5);

    int test2[5] = {10, 12, 20, 400, 30};
    std::cout << std::endl << "Quick desc" << std::endl;
    print(test2, 5);
    quick_sort(test2, 5, 0, true, false);
    print(test2, 5);

    return 0;
}