quicksort_without_recursion.cpp

#include <vector>
#include <iostream>

using namespace std;

void swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int partition(vector<int>& arr, int l, int r) {
	int pivot = arr[r];
	int i = l - 1;

	for (int j = l; j < r; j++) {
		if (pivot > arr[j]) {
			i++;
			swap(arr[i], arr[j]);
		}
	}

	swap(&arr[i + 1], &arr[r]);
	return (i + 1);
}

void quicksort(vector<int>& arr, int l, int r) {
	int st[1000];
	int top = -1;
	st[++top] = l;
	st[++top] = r;

	while (top >= 0) {		
		int tr = st[top--];
		int tl = st[top--];
		
		int p = partition(arr, tl, tr);
		if (p - 1 > tl) {
			st[++top] = tl;
			st[++top] = p - 1;
		}

		if (p + 1 < tr) {
			st[++top] = p + 1;
			st[++top] = tr;
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	vector<int> a(n);

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	quicksort(a, 0, n - 1);
	
	for (int i = 0; i < n; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';

	return 0;
}