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;
}
