[06. 정렬 알고리즘] 퀵 정렬(Quick Sort)

Recursion

#include <iostream>
using namespace std;

// std::swap() 함수보다 빠르다.
#define swap2(type, x, y) do { type t = x; x = y; y = t; } while (false)

void Partition(int arr[], const int left, const int right) {
	if (left >= right)
		return;

	int pl = left;
	int pr = right;
	int pivot = arr[(pl + pr) / 2];
	while (true) {
		while (arr[pl] < pivot) pl++;
		while (arr[pr] > pivot) pr--;
		if (pl >= pr)
			break;

		swap2(int, arr[pl], arr[pr]);
		pl++, pr--;
	}
	if (pl == pr)
		pl++, pr--;

	Partition(arr, left, pr);
	Partition(arr, pl, right);
}

void QuickSortRecur(int arr[], const int N) {
	Partition(arr, 0, N - 1);
}

Stack

#include <stack>

void QuickSortStack(int arr[], const int N) {
	class StackPair {
		struct Pair { int first, second; };	// 5, 6 ms
		//typedef pair<int, int> Pair;		// 5, 6, 7 ms
		Pair buf[20];
		int pos = 0;

	public:
		void emplace(int a, int b)	{ buf[pos++] = { a, b }; }
		Pair& top() const			{ return buf[pos - 1]; }
		void pop()					{ if (pos > 0) pos--; }
		bool empty() const			{ return pos == 0; }
	};

	StackPair st;					// 5, 6 ms
	//stack<pair<int, int>> st;		// 44 ms

	st.emplace(0, N-1);
	
	while (!st.empty()) {
		const int left = st.top().first;
		const int right = st.top().second;
		st.pop();

		int pl = left;
		int pr = right;
		const int pivot = arr[(pl + pr) / 2];

		while (true) {
			while (arr[pl] < pivot) pl++;
			while (arr[pr] > pivot) pr--;
			if (pl >= pr)
				break;

			swap2(int, arr[pl], arr[pr]);
			pl++, pr--;
		}
		if (pl == pr)
			pl++, pr--;

		if (left < pr)	st.emplace(left, pr);
		if (pl < right)	st.emplace(pl, right);
	}
}

int comp(const void* a, const void* b) { return *(int*)a - *(int*)b; };

int main(int argc, const char* argv[]) {
	const int N = RAND_MAX;
	int arr[N];
	for (int i = 0; i < N; ++i)
		arr[i] = rand();

	int start = clock();
	QuickSortRecur(arr, N);						// 4 ms
    //QuickSortStack(arr, N);					// 5, 6 ms
    //std::sort(arr, end(arr));					// 32 ms: 퀵 정렬
	//std::qsort(arr, N, sizeof *arr, comp);	// 19 ms: 퀵 정렬 (C-style)
    
	cout << clock() - start << endl;
}

• 함수 QuickSortStack() 안에서 std::stack을 사용하면 속도가 현저히 떨어짐(44 ms)을 확인할 수 있다.

pivot 선택과 알고리즘 개선

void Partition(int arr[], const int left, const int right) {
	if (left >= right)
		return;

	int pl = left;
	int pr = right;

    // 변경된 부분
	int pm = (pl + pr) / 2;
	if (arr[pl] > arr[pm])	swap2(int, arr[pl], arr[pm]);
	if (arr[pm] > arr[pr])	swap2(int, arr[pm], arr[pr]);
	if (arr[pl] > arr[pm])	swap2(int, arr[pl], arr[pm]);
	const int pivot = arr[pm];
	swap2(int, arr[pm], arr[right - 1]);
	pl++, pr -= 2;
    // 여기 까지
    
    
	while (true) {
		while (arr[pl] < pivot) pl++;
		while (arr[pr] > pivot) pr--;
		if (pl >= pr)
			break;

		swap2(int, arr[pl], arr[pr]);
		pl++, pr--;
	}
	if (pl == pr)
		pl++, pr--;

	Partition(arr, left, pr);
	Partition(arr, pl, right);
}

• 함수 QuickSortRecur, QuickSortStack 둘 다 결과의 차이가 없다.
• 오차범위내에서 차이가 있는 것일지도 모른다.