[알고리즘] 정렬(6) - 퀵 정렬(Quick Sort)

 원리 

1. 배열 리스트 중 하나를 선택한다. 이 원소를 피벗이라고 함.

2. 피벗을 기준으로 피벗 앞에는 피벗보다 작은 모든 원소들이 오고 피벗 뒤에는 피벗보다 큰 원소가 옴

3. 분할 : 리스틀 피벗을 기준으로 두 리스트로 나눈다. 

4. 분할된 리스트들에서 1-3번 과정을 반복한다.

 

위와 같은 과정을 반복한다면 매번 분할시 피벗으로 한 원소의 위치를 정할 수 있으므로 모든 수를 정렬할 수 있는 것은 자명합니다.

 

앞서 포스팅한 병합정렬에서와 마찬가지로 분할 정복(Divide and conquer)을 이해하고 있어야합니다. 분할 정복을 모른다면 공부하고 읽는 것을 권장드립니다. 하지만 포스트를 통해서 이해는 할 수 있습니다.

 

[ 16, 11, 6, 19, 12, 2, 2, 10 ]

pivot값은 맨앞의 값을 편의상 잡아줍니다. 그리고 16을 기준으로 작은건 왼쪽으로 큰건 오른쪽으로 이동시킵니다. 이 때, 아래와 같은 로직으로 수행합니다.

 

• 리스트의 가장처음에서 시작하는 인덱스 i(피벗 제외)를 피벗보다 큰 것이 나올 때까지 1씩 증가시킵니다.
• 리스트의 가장끝에서 시작하는 인덱스 j를 1씩 감소시키면서 만약 피벗보다 작은 것이 나온다면 j와 스왑합니다.
• i가 j보다 커질때까지 위의 두 과정을 반복하고 i가 j보다 커진다면 j와 pivot과 스왑합니다.

Cycle 1

Cycle 2

이번 원소보다 큰것은 '19' 하나로 과정이 종료되었습니다. 그리고 피벗 기준으로 왼쪽리스트와 오른쪽리스트에 동일한 과정을 수행합니다.

 

분할

 구현 

#include <bits/stdc++.h>
using namespace std;

__inline void swap(int& a, int& b) { int t = a; a = b; b = t; }
const int MAX_N = 60000;

template <typename T>
void QuickSort(vector<T>& data, int low, int high)
{
	// base condition
	if (low >= high) return;

	// divide process
	int j = high + 1, i = high;
	int& pivot = data[low];

	// pivot 보다 작은건 왼쪽으로 모는 작업
	// swap하기전에 j값을 줄여주는 이유 :
	// i < j 이고 data[i] > pivot일 때 스왑하기 때문에 
	// data[j] < pivot은 자명하다 (단 i != j)
	for (; i > low; --i)
		if (data[i] > pivot)
			swap(data[--j], data[i]);

	swap(pivot, data[--j]);

	QuickSort(data, low, j - 1);
	QuickSort(data, j + 1, high);
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	clock_t s, e;
	vector<int> arr(MAX_N);
	srand((unsigned int)time(NULL));

	for (int t = 0; t < 5; ++t)
	{
		for (int i = 0; i < MAX_N; ++i)
			arr[i] = rand() % MAX_N;

		s = clock();
		QuickSort(arr, 0, MAX_N - 1);
		e = clock();

		cout << (double)(e - s) / CLOCKS_PER_SEC << "s\n";
	}

}

 

 

 시간복잡도 

퀵소트는 병합정렬처럼 정확히 반으로 나누어서 정렬을 진행하지 않기때문에 최악의 경우가 존재합니다. 먼저 최선의 경우 병합정렬과 같이 모든 피벗이 n/2의 위치에 있을 때 시간복잡도는 O(nlogn)입니다.

 

https://imgur.com/

즉 원소의 개수 8개일 때, 8 -> 4 -> 2 -> 1 순으로 나눌 수 있습니다. 반면에 배열의 개수는 1 -> 2 -> 4 -> 8 으로 증가하므로  [8 * 1 = 8 ] [4 * 2 = 8] [2 * 4 = 8] [1 * 8 = 8] 이고, 모두 8번 비교하게 됩니다. 즉, [8 * n/2 1쌍] [4 * n/2 2쌍] [2 * n/2 3쌍] [1 * n/2 4쌍] 순으로 진행됩니다. 따라서 O(n * logn)의 시간복잡도를 가지게됩니다.

 

이를 일반화 하면 2^(진행 횟수) = 배열의 개수(나뉜 개수)

2^3 = 8 --> 2^k = n --> k = logn --> O(logn) 이고,

또한 각 단계마다 리스트의 전체를 순회하기때문에 O(n), 따라서 총 O(nlogn)이 됩니다! 

 

반면에 최악의 경우, 정렬되어 있기때문에 피벗이 움직이지 않을 때입니다. 최선의 경우와 달리 재귀 호출의 수가 증가합니다.

 

최악의 시간복잡도

위 그림과 같이 재귀호출( == 재귀 호출의 깊이)을 총 N번하고 있습니다. 최선의 경우에서의 이분탐색의 경우 2^2 = 4 로 2번의 호출로 처리 할 수 있는 상황입니다. 만약 총 N이 4가 아니라 2^30 이라고 한다면 이분탐색의 경우 30번의 호출만 하면되지만, 최악의 경우 2^30번 해야합니다. 즉 시간 복잡도 O(n)을 가지고 기존에 리스트를 순회하기 때문에 총 O(n^2)의 시간복잡도를 가지게됩니다.

 정리 

이름	BEST	AVG	WORST	RUN TIME(정수 60,000)
버블 정렬	n^2	n^2	n^2	확인
선택 정렬	n^2	n^2	n^2	확인
삽입 정렬	n	n^2	n^2	확인
계수 정렬	n	n	n	확인
병합 정렬	nlogn	nlogn	nlogn	확인
퀵 정렬	nlogn	nlogn	n^2	사진 참고

퀵 정렬 런타임 (랜덤 정수 60,000개)

약 15ms ~ 30ms가 측정된 것을 확인할 수 있습니다. 퀵정렬을 메모리 참조가 지역화되어 있기 때문에 매우 빠릅니다. 또한 최악의 경우의 n^2의 시간복잡도가 나오지 않도록 설계가 가능해서 많이 사용되어집니다.

 

실행 환경 :

- windows 10 WSL2 - ubuntu 18.04

- gcc 7.4.0

- cpu : i3

- ram : 8G

 참조 

- 위키백과

퀵 정렬 - 위키백과, 우리 모두의 백과사전