快速排序的递归和非递归实现

快速排序的递归和非递归实现

#include <iostream>

using namespace std;

int partition(int arr[], int low, int high) {
    /**
     * This function takes last element as pivot,
     * places the pivot element at its correct position
     * in sorted  array, and places all smaller
     * (smaller than pivot) to left of pivot and
     * all greater elements to right of pivot
     */
    int small_index = low - 1;
    // If current element is smaller than pivot
    for (int i = low; i < high; i++)
        if (arr[high] > arr[i])
            swap(arr[++small_index], arr[i]); // increment index of smaller element and swap
    swap(arr[++small_index], arr[high]);
    return small_index;
}

void quickSortRecursive(int arr[], int low, int high) {
    if (low < high) {
        /* pi is partitioning index, arr[p] is now
           at right place */
        int p = partition(arr, low, high);
        // Separately sort elements before
        // partition and after partition
        quickSortRecursive(arr, low, p - 1);
        quickSortRecursive(arr, p + 1, high);
    }
}

void quickSort(int arr[], int low, int high) {
    // Create an auxiliary stack
    int stack[high - low + 1];

    // initialize top of stack
    int top = -1;

    // push initial values of l and h to stack
    stack[++top] = low;
    stack[++top] = high;

    // Keep popping from stack while is not empty
    while (top >= 0) {
        // Pop high and low
        high = stack[top--];
        low = stack[top--];

        // Set pivot element at its correct position in sorted array
        int p = partition(arr, low, high);

        // If there are elements on left side of pivot, then push left side to stack
        if (p - 1 > low) {
            stack[++top] = low;
            stack[++top] = p - 1;
        }

        // If there are elements on right side of pivot, then push right side to stack
        if (p + 1 < high) {
            stack[++top] = p + 1;
            stack[++top] = high;
        }
    }
}

int main() {
    int arr[] = {3, 2, 1, 4, 5, 6, 7, 0, 9, 8};
    quickSort(arr, 0, 9);
    for (int i:arr) {
        cout << i << endl;
    }
    return 0;
}