Iterative Quicksort (C++)

Iterative Quicksort

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

int partition(int a[], int start, int end)
{
    int pivot = a[end]; //오른쪽 끝을 피벗으로

    int pIndex = start; //작은 수는 pindex 왼쪽, 큰 수는 오른쪽, 같은 건 어느쪽이든 상관없음

    // 원소가 피벗과 같거나 작으면 pindex 증가 후 피벗 앞에(왼쪽) 놓임
    for (int i = start; i < end; i++)
    {
        if (a[i] <= pivot)
        {
            swap(a[i], a[pIndex]); //왼쪽으로 보냄 (정확히는 a[0+i]으로
            pIndex++;
        }
    }

    swap(a[pIndex], a[end]); //pindex와 pivot을 스왑

    return pIndex;
}

// Iterative Quicksort routine
void iterativeQuicksort(int a[], int n)
{
    stack<pair<int, int>> s; //pair(int, int)가 들어가는 스택 s

    int start = 0;
    int end = n - 1;

    s.push(make_pair(start, end)); //(0, n-1)

    while (!s.empty()) //스택이 빌 때까지 루프
    {
        start = s.top().first, end = s.top().second;
        s.pop();

        // rearrange elements across pivot
        int pivot = partition(a, start, end);

        // push subarray indices containing elements that are
        // less than the current pivot to stack
        if (pivot - 1 > start) {
            s.push(make_pair(start, pivot - 1));
        }

        // push subarray indices containing elements that are
        // more than the current pivot to stack
        if (pivot + 1 < end) {
            s.push(make_pair(pivot + 1, end));
        }
    }
}

// Iterative Implementation of Quicksort
int main()
{
    int a[] = { 2, 5, 10, 8, 13, 6, 3 };
    int n = sizeof(a) / sizeof(a[0]);

    iterativeQuicksort(a, n);

    // print the sorted array
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }

    return 0;
}