퀵 소트 재귀 호출없이 구현하기

재귀의 장점은 프로그램이 간결하다는 장점이 있지만, 스택 메모리 오버플로우 가능성이 존재한다는 점과 프로그램 가독성이 떨어진다는 단점이 있다

 

[참고] https://www.geeksforgeeks.org/iterative-quick-sort/

 

재귀함수는 비재귀함수는 for, while 반복문으로 짤 수 있다. 퀵 소트를 구현하기 위해서는 quicksort 함수를 재귀함수로 이용했는데 stack 자료구조를 이용해 partition의 반환값을 비교해 아직 부분집합의 크기가 1보다 크다면 stack에 넣어 반복문을 수행시킬 수 있다

 

stack STL을 사용하는 것은 느리다. 배열로 대체하도록 한다

 

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

view raw quicksort_without_recursion.cpp hosted with ❤ by GitHub