[알고리즘] 정렬 - 퀵 정렬, O(NlogN)

  평균적인 상황에서 높은 성능을 발휘하는 퀵 정렬이다. C++ STL 자료구조의 정렬에서 사용되는 것으로 알고 있다. 퀵 정렬은 최악의 상황 (후술)에서는 O(N^2)까지 시간 복잡도가 증가할 수도 있지만 대부분의 상황에서는 O(NlogN) 안에서 해결된다. O(NlogN)이라는 것은 MergeSort와 비슷한 구조의 알고리즘이라는 것이고, 실제로 동작 방식에 차이는 있지만 더 작은 문제로 쪼개서 해결한다는 점은 동일하다. MergeSort와의 큰 차이점에는 1. 문제가 쪼개지는 균형이 보장되지 않는다, 2. MergeSort는 작은 문제를 해결한 뒤 합치는 방식 (bottom-up)이라면 QuickSort는 큰 문제부터 해결하면서 정렬되는 방식 (top-down)이다. 가 있다.

 

 

    퀵 정렬 (Quick Sort) 소개                

  퀵 정렬은 pivot을 기준으로 pivot보다 작은 데이터 묶음과, pivot보다 큰 데이터 묶음으로 나눠서 작은 문제로 만들어 분할 정복하는 알고리즘이다. 이러한 과정을 Partition이라고 한다. Partition을 완료하면 pivot을 기준으로 왼쪽은 pivot보다 작은 값들만 존재하고, pivot보다 오른쪽은 큰 값들만 존재한다. 즉, partition 과정을 거치고 나면 pivot은 전체 데이터에서 알맞은 위치에 정렬된다는 뜻이다. 점점 작은 문제를 동일한 방식으로 해결하면서 모든 원소가 제자리를 찾으면서 정렬되는 것이 quicksort 알고리즘의 원리이다. Pivot을 정하는 방식은 소소하게 차이가 있을 수 있지만 나는 가장 마지막에 있는 원소를 pivot으로 하겠다. 

 

  우선 Partition 과정을 알아보자.

  우선 partition 과정에는 2개의 인덱스 포인터가 필요하다. 하나의 포인터(보라색)는 데이터가 시작하는 인덱스 - 1에서 시작하여 pivot보다 작은 원소들 중 가장 마지막 원소를 가리키는 포인터이다. 이 포인터를 경계로 데이터가 나뉜다고 볼 수 있다. 두 번째 포인터(초록색)은 데이터를 순서대로 순회하는 포인터로, 이 포인터가 가리키는 값과 pivot 값을 비교한다. 

 

  위 그림을 보면서 설명하겠다. 첫 번째 원소를 pivot과 비교하게 된다. 1과 5 중에 1이 더 작으므로 보라색 포인터를 한 칸 오른쪽으로 옮겨 pivot 보다 작다고 판정이 종료된 값 중 가장 오른쪽인 1을 가리키게 된다. 이후 초록색 포인터가 가리키던 값과 swap 하는데, 여기서는 보라색 포인터와 초록색 포인터가 동일한 값을 가리키므로 결국 그대로이다. 초록색 포인터는 매 단계 자동으로 한 칸씩 오른쪽으로 옮겨가면서 비교하는 포인터이므로 이에 대한 설명은 생략하겠다. 두 번째 단계에서 두 번째 원소와 pivot을 비교한다. 8은 5보다 크므로 pivot의 오른쪽에 위치해야 하는 원소이다. 바로 다음 단계로 넘어가게 된다. 세 번째 원소와 pivot을 비교한다. 2는 5보다 작으므로 pivot의 왼쪽에 위치해야 하는 원소이다. 보라색 포인터를 1 증가시키면서  초록색 포인터가 가리키던 값 (현재 비교하던 값) 과 swap 한다. 교체된 원소를 보라색으로 표시했다. 이러한 swap 과정이 있어야 pivot보다 작은 값이 왼쪽에 모일 수 있게 된다. 이어서 6은 5보다 큰 값이므로 다음 단계로 넘어간다. 4는 5보다 작은 값이므로 보라색 포인터를 한 칸 올린 후 초록색 포인터가 가리키는 4와 swap하고 다음 단계로 넘어간다. 3은 5보다 작은 값이므로 보라색 포인터를 한 칸 올린 후  초록색 포인터가 가리키는 3과 swap하고 다음 단계로 넘어간다. 마지막으로, 초록색 포인터가 pivot (마지막 원소)을 가리키게 되면 보라색 포인터가 가리키는 값의 다음 원소와 pivot 원소를 swap 한다.

 

  과정을 일반적으로 정리하면 다음과 같다.

1. 비교하는 값이 pivot보다 크면 다음 단계로 넘어간다. (초록색 포인터만 1 증가한다)
2. 비교하는 값이 pivot보다 작으면 보라색 포인터를 1 올리고 초록색 포인터가 가리키던 값과 swap한다. (이후 초록색 포인터를 1 증가시킨다)
3. 마지막에 초록색 포인터가 pivot을 가리키게 되면 보라색 포인터 +1 값과 pivot을 swap한다.

 

  퀵 정렬의 시간복잡도를 계산해보자. 만약 pivot 값이 데이터 전체의 중간값에 가깝다면, 데이터가 비슷한 크기로 나뉘게 된다. 이런 과정이 반복적으로 일어나면 partition이 대략 O(logN)의 단계로 이루어진다. 이 때 partition 과정은 초록색 포인터가 1씩 증가하면서 데이터 개수만큼 비교가 일어나고, swap이나 포인터 증가 같은 다른 연산은 상수 시간 안에 이루어지므로 M개의 데이터가 입력되면 O(M)의 시간이 걸린다. 나눠진 데이터의 개수를 합치면 O(N)에 비례하므로 각 단계에서 O(N)의 partition이 이루어지고, 총 O(NlogN)의 시간이 걸린다.

 

  다만 이 경우는 pivot이 잘 선택되어 데이터가 좋은 균형으로 나뉘어졌을 때의 경우이고, 이번에는 최악의 경우에 대해 생각해보자. 최악의 경우는 pivot이 데이터 중 가장 큰(작은) 값에 가깝게 계속 뽑히는 경우이다. 이 경우 단계가 O(logN)이 아닌 O(N)에 가깝게 나뉘게 되므로 O(N) 단계 * O(N) partition 시간복잡도로 계산되어 총 O(N^2)의 시간이 소모된다.

 

  이러한 문제를 이후에 선형시간 선택 알고리즘을 공부하면서 데이터가 적절한 균형으로 나눠지는 것을 보장하는 방법을 이용해서 개선할 수도 있을 것 같다.

 

    C++ 구현                

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

// Partition 과정 후 pivot이 위치하게 된 index 반환
int Partition(vector<int>& _arr, int _start, int _end)
{
	int p1 = _start - 1;
	int p2 = _start;

	int pivot = _arr[_end];

	// 마지막 전까지 반복
	for (; p2 < _end; ++p2)
	{
		// pivot보다 작은 값을 만나면 p1포인터를 1증가시키고 pivot과 swap
		if (_arr[p2] < pivot)
		{
			int temp = _arr[++p1];
			_arr[p1] = _arr[p2];
			_arr[p2] = temp;
		}
	}

	// 마지막에 _arr[p1+1] 과 _arr[_end] (pivot) 을 swap
	int temp = _arr[p1 + 1];
	_arr[p1 + 1] = _arr[_end];
	_arr[_end] = temp;

	return p1 + 1;
}

void QuickSort(vector<int>& _arr, int _start, int _end)
{
	if (_start >= _end)
		return;
	int pivotIndex = Partition(_arr, _start, _end);
	QuickSort(_arr, _start, pivotIndex-1);
	QuickSort(_arr, pivotIndex + 1, _end);
}

int main()
{
	vector<int> arr = { 5,1,2,3,9,8,4,6,10,7 };
	QuickSort(arr, 0, arr.size() - 1);

	return 0;
}