[자료구조] 퀵 정렬

퀵 정렬 알고리즘에서 분할은 매우 중요하다.

분할

퀵 정렬 알고리즘은 아래와 같이 동작한다.

1. 배열을 분할한다. 피벗은 이제 올바른 위치에 있다.
2. 피벗의 왼쪽과 오른쪽에 있는 하위 배열을 각각 또 다른 배열로 보고 1단계와 2단계를 재귀적으로 반복한다.
3. 하위 배열이 원소를 0개 또는 1개 포함하면 기저 조건이므로 아무것도 하지 않는다.

#include <vector>
#include <iostream>
using namespace std;

class CSortArray
{
public:
	CSortArray() = default;
	CSortArray(vector<int>& arr)
	{
		array = arr;
	}

	int partition(int lptr, int rptr)
	{
		int pivot_pos = rptr;
		int pivot = array[pivot_pos];
		rptr--;

		while (true)
		{
			while (array[lptr] < pivot)
				lptr++;
			while (array[rptr] > pivot)
				rptr--;

			if (lptr >= rptr)
				break;
			else
				swap(lptr, rptr);
		}

		swap(lptr, pivot_pos);
		return lptr;
	}

	void swap(int ptr1, int ptr2)
	{
		int tmp_value = array[ptr1];
		array[ptr1] = array[ptr2];
		array[ptr2] = tmp_value;
	}

	vector<int> array;
};

class CQuickSort : public CSortArray
{
public:
	CQuickSort() = default;
	CQuickSort(vector<int>& arr) : CSortArray(arr) {};

	void quicksort(int leftIndex, int rightIndex)
	{
		if (rightIndex - leftIndex <= 0)
			return;

		int pivot_pos = partition(leftIndex, rightIndex);
		quicksort(leftIndex, pivot_pos - 1);
		quicksort(pivot_pos + 1, rightIndex);
	}
};

int main()
{
	vector<int> testArr = { 0, 5, 2, 1, 6, 3 };
	CQuickSort quickSort(testArr);
	quickSort.quicksort(0, testArr.size() - 1);

	for (int i = 0; i < (int)testArr.size(); i++)
		cout << testArr[i] << "\t";
	cout << endl;
	for (int i = 0; i < (int)quickSort.array.size(); i++)
		cout << quickSort.array[i] << "\t";
	cout << endl;

	return 0;
}

분할을 했을 때에는 pivot의 위치의 정확성만 보았다면, 퀵 정렬에서는 정렬까지 이뤄졌다. 

 

퀵 정렬의 효율성을 알아내려면 먼저 분할의 효율성을 밝혀야 한다. 분할에 필요한 단계를 분류해 보면 단계가 두 종류임을 알 수 있다.

• 비교 : 각 값과 피벗을 비교한다.
• 교환 : 적절한 때에 왼쪽과 오른쪽 포인터가 가리키고 있는 값을 교환한다.

각 분할마다 배열 내 각 원소를 피벗과 비교하므로 최소 N번 비교한다. 분할을 한 번 할 때마다 왼쪽과 오른쪽 포인터가 서로 만날 때까지 각 셀을 이동하기 때문이다. 교환 횟수는 최대 N/2번 교환한다.

 

평균적인 상황에서 퀵 정렬이 우수하기 때문에 내부적으로 퀵 정렬을 사용해 자신만의 정렬 함수를 구현하는 언어가 많다. 따라서 퀵 정렬을 직접 구현할 일은 거의 없다. 하지만 퀵 셀렉트라 불리는 매우 유사한 알고리즘이 실용적으로 쓸모가 있을 수 있다.