[Algorithm] 정렬 - 빠른 정렬 (Quick Sort)

빠른 정렬(Quick Sort)이란?

- 피벗을 하나 정한 후 피벗을 기준으로 피벗보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 정렬하는 방식이다.

- 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

- 분할 정복 알고리즘의 하나이다.

- 불안정 정렬에 속한다.

 

* 안정 / 불안정 정렬

동일한 값에 대해 기존의 순서가 유지되는지 여부에 따라 안정 / 불안정 정렬로 구분된다.

 

 

작동 방식

1) 피벗을 정한다.

2) 데이터의 양쪽 끝 값과 피벗을 비교한다.

3) 왼쪽 값이 피벗보다 크고, 오른쪽 값이 피벗보다 작으면 두 값을 서로 교체한다.

4) 만약 왼쪽 값이 피벗보다 작거나, 오른쪽 값이 피벗보다 크면 교체하지 않는다.

5) 한차례 비교하게 되면, 피벗을 기준으로 피벗보다 작은 값들은 피벗 왼쪽에,

  피벗보다 큰 값들은 피벗 오른쪽에 오게 된다.

6) 피벗을 기준으로 양쪽이 정렬되었으므로,

   피벗의 왼쪽 부분 / 오른쪽 부분, 두 부분으로 나눠서 각각 다시 정렬한다.

   (위 그림의 경우 [3, 1, 2] / [5] 로 나눠서 각각 정렬)

7) 더 이상 두 부분으로 나눌 수 없을 때까지 작업을 반복한다.

 

* 임의의 피벗으로 정해도 되지만,

빠른 정렬은 피벗을 무엇으로 정하느냐에 따라 실행 속도 차이가 심하다.

데이터의 중간 값을 피벗으로 정하는 것이 좋다.

 

 

 

소스코드

#include <iostream>

using namespace std;

void quickSort(int* arr, int left, int right);

int main() {
	int N;
	cin >> N;
	
	int* arr = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	quickSort(arr, 0, N - 1);

	for (int i = 0; i < N; i++) {
		cout << arr[i] << endl;
	}

	delete[] arr;

	return 0;
}

void quickSort(int* arr, int left, int right) {
	int l = left;
	int r = right;
	int pivot = arr[(l + r) / 2];
	if (l < r) {
		while (l < r) {
			while (arr[l] < pivot) l++;
			while (arr[r] > pivot) r--;

			// 값 교체
			int temp = arr[l];
			arr[l] = arr[r];
			arr[r] = temp;
		}

		quickSort(arr, left, l - 1);
		quickSort(arr, l + 1, right);
	}
}

 

 

시간복잡도

평균의 경우 : O(nlogn)

최선의 경우 : O(nlogn)

계속해서 중간 값이 피벗으로 정해졌다고 가정할 때, 그 깊이는 logn이 된다.

데이터 개수 n만큼 진행되므로 시간복잡도는 O(nlogn)이다.

 

최악의 경우 : O(n2)

최악의 경우는 데이터가 정렬(또는 역정렬)이 되어있다고 가정했을 때,

피벗이 가장 작은 값 또는 가장 큰 값이 되는 경우이다.

이 경우 분할의 깊이가 n이 되기 때문에 시간복잡도는 O(n2)이 된다.

 

 

합병 정렬과 비교

평균 시간 복잡도가 동일한 합병 정렬과 비교해보면,

1. 빠른 정렬은 합병 정렬과 달리 정렬한 데이터를 저장하기 위한 별도의 공간이 필요하지 않다.

2. 합병 정렬은 분할단계에서 균등하게 2분할되지만, 빠른 정렬은 데이터에 따라 다를 수 있다.

3. 빠른 정렬은 피벗을 어떤 것으로 선택하느냐에 따라 속도 차이가 심하다.

   따라서 데이터가 큰 경우에는 합병 정렬을 사용하는 것이 더 좋다.

4. 빠른 정렬과 합병 정렬은 (평균)시간복잡도가 O(nlogn)으로 동일한데,

   성능을 측정해보면 빠른 정렬이 2-3배 더 빠르다. (평균적으로)

   그 이유는 루프 안에서 실행되는 작업이 합병 정렬보다 더 간결하기 때문이다.

 

 

참고

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC