/*
Quick Sort
퀵 소트
*/
#include <iostream>
#include <stack>
using namespace std;
//재귀 퀵소트
template <class T>
void QuickSort(T *a, const int left, const int right)
{
//a[left:right]를 오름차순으로 정렬
//a[left]는 pivot이다.
if (left < right)
{
int i = left, j = right + 1, pivot = a[left];
do
{
do
{
i++;
} while (a[i] < pivot);
do
{
j--;
} while (a[j] > pivot);
if (i < j)
swap(a[i], a[j]);
} while (i < j);
swap(a[left], a[j]);
QuickSort(a, left, j - 1);
QuickSort(a, j + 1, right);
}
}
/*
//비재귀 퀵소트(right가 pivot)
template <class T>
void NonRecurQuickSort(T *a, int left, int right)
{
stack<int> s;
s.push(right);
s.push(left);
while (!s.empty())
{
left = s.top();
s.pop();
right = s.top();
s.pop();
if (right>left)
{
int pivot = a[right];
int start = left - 1;
int end = right;
while (1)
{
do
{
start++;
} while (a[start] < pivot);
do
{
end--;
} while (a[end] > pivot);
if (start >= end)
break;
swap(a[start], a[end]);
}
swap(a[start], a[right]);
s.push(right);
s.push(start + 1); //여기까지 한 partition
s.push(start - 1);
s.push(left); //여기까지 나머지 partition
}
}
}
*/
//비재귀 퀵소트(left가 pivot)
template <class T>
void NonRecurQuickSort(T *a, int left, int right)
{
stack<int> s;
s.push(right);
s.push(left);
while (!s.empty())
{
left = s.top();
s.pop();
right = s.top();
s.pop();
if (right>left)
{
int pivot = a[left];
int start = left;
int end = right + 1;
while (1)
{
do
{
start++;
} while (a[start] < pivot);
do
{
end--;
} while (a[end] > pivot);
if (start >= end)
break;
swap(a[start], a[end]);
}
swap(a[left], a[end]);
s.push(end - 1);
s.push(left); //여기까지 나머지 partition
s.push(right);
s.push(end + 1); //여기까지 한 partition
}
}
}
int main(void)
{
int length;
int *arr;
cout << "배열의 길이는? ";
cin >> length;
arr = new int[length + 1];
for (int i = 1; i < length + 1; i++)
{
cout << i << "번째 배열 값 입력: ";
cin >> arr[i];
}
//QuickSort(arr, 1, 10);
NonRecurQuickSort(arr, 1, 10);
for (int i = 1; i < length + 1; i++)
cout << arr[i] << " ";
cout << endl;
delete[]arr;
return 0;
}
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.