[알고리즘] 퀵정렬 Quick Sort (C++ 구현)

📌 퀵정렬

퀵정렬은 가장 널리 쓰이는 정렬 알고리즘으로 말 그대로 빠른 정렬이 가능하다. 퀵 정렬도 병합정렬과 마찬가지로 분할정복기법을 이용한 알고리즘이다. 퀵 정렬의 핵심 아이디어는 특정 원소를 기준으로 작은 데이터와 큰 데이터를 분류한다는 것이다. 이렇게 되면 특정 원소를 기준으로 순서가 결정되며 분류된 작은 데이터와 큰 데이터 안에서 각각 기준 원소를 다시 정해 재귀적으로 쪼개나가면서 정렬해나간다. 병합정렬과 마찬가지로 단위를 쪼개나가는 아이디어이므로 분할정복기법이라고 할 수 있다.

---

이때 생각해봐야 할 것은 기준이 되는 원소(pivot)를 어떻게 정하느냐 인데, 

1) 첫번째 원소를 기준으로 하거나

2) 랜덤으로 원소를 선택한다

 

첫번째 원소를 기준으로 할 경우 이미 정렬된 리스트의 경우 피봇의 한쪽에만 원소가 몰려있어 성능에 영향을 미치므로 일반적으로 무작위로 원소를 선택한다. c++에서는 <random> 라이브러리의 random_device를 사용해 중복없이 랜덤값을 뽑아낼 수 있다. (C의 rand에 비해 낫다고 하는데 잘 모르겠다)

쉬운 구현을 위해 랜덤값이 리스트에서의 피봇 인덱스이며, 그 피봇 값을 따로 인덱싱해 구해놓는다.

// 기준이 될 pivot 값 랜덤으로 정함
random_device rd;
mt19937_64 random(rd());
uniform_int_distribution<int> range(0, L.size() - 1);
int index = range(random);
int pivot = L[index];

이후 기준 원소를 중심으로 작은 것은 왼쪽에, 큰 것은 오른쪽으로 위치를 바꿔야 하며, 왼쪽과 오른쪽으로 분류된 원소들 내에서 또 다시 퀵정렬을 적용해 작은 단위로 분할해(divide)나간다. 병합정렬과 마찬가지로 Divide-Delegate-Combine 의 과정을 거친다.

// pivot값을 제외한 벡터를 left, right으로 나눔
L.erase(L.begin() + index);

vector<int> left, right;
for (int i = 0; i < L.size(); i++) {
	if (L[i] > pivot) {
		right.push_back(L[i]);
	}
	else {
		left.push_back(L[i]);
	}
}

// left, right에 퀵정렬 재귀 적용
vector<int> p = quicksort(left);
vector<int> q = quicksort(right);

vector<int> target = p;
target.push_back(pivot);
target.insert(end(target), begin(q), end(q));

📌시간복잡도

퀵정렬의 시간복잡도는 병합정렬과 마찬가지로 nlogn 시간을 가진다. 최악의 경우 기준 원소의 한쪽에만 원소가 쏠리면 O(n^2) 시간도 가능하지만 평균적으로는 nlogn 시간이다. 병합정렬은 언제나 nlogn 시간을 보장한다는 점에서 장단점이 있다.

 

merge sort와 quick sort는 모두 분할정복기법! 이것만 기억하면 될 거 같다