5-3. 퀵 정렬(Quick Sort)

1. 퀵 정렬(Quick Sort)의 원리

(1) 인덱스 지정

- 배열의 첫 값을 pivot(피벗)으로 지정

- 그 다음 값을 시작위치인 low로 지정

- 배열의 마지막 값을 high로 지정

 

(2) 인덱스 이동

- pivot >= arr[low] 일 때까지 low 인덱스를 1씩 증가시킴

- pivot <= arr[high] 일 때까지 high 인덱스를 1씩 감소시킴

 

(3) 데이터 교체

인덱스 간 크기 비교를 통해, low < high 이면 arr[low]와 arr[high]의 데이터를 교체 함

다시 1번과 2번을 반복함

2회차 인덱스 이동

2회차 데이터 교체

 

(4) 알고리즘 종료

- 인덱스 high > low보다 커질 때 알고리즘을 종료

- arr[pivot] 과 arr[high] 교체

피벗의 값과 high의 값을 교체

위의 알고리즘을 통해 피벗을 기준으로 좌측은 피벗 값보다 작게,

피벗을 기준으로 우측은 피벗 값보다 크게 정렬된다.

 

2. 퀵 정렬 구현

int Partition(vector<int>& v, int left, int right)
{
	int pivot = v[left];
	int low = left + 1;
	int high = right;

	while (low <= high)
	{
		while (low <= right && pivot >= v[low]) // 유효 범위를 벗어날 수 없음
			low++;

		while (high >= left + 1 && pivot <= v[high]) // 피벗을 제외한 앞의 값까지가 유효 범위
			high--;

		if (low < high)
			swap(v[low], v[high]);
	}

	swap(v[left], v[high]);
	return high;
}

void QuickSort(vector<int>& v, int left, int right) // left ; 시작 위치, right ; 끝 위치
{
	if (left > right)
		return;

	int pivot = Partition(v, left, right);
	QuickSort(v, left, pivot - 1); // 중앙 피벗 기준 좌측 배열
	QuickSort(v, pivot + 1, right); // 중앙 피벗 기준 우측 배열
}

 

3. 코드 분석

(1) 알고리즘 작동

int Partition(vector<int>& v, int left, int right)
{
	int pivot = v[left];
	int low = left + 1;
	int high = right;

	while (low <= high)
	{
		while (low <= right && pivot >= v[low]) // 유효 범위를 벗어날 수 없음
			low++;

		while (high >= left + 1 && pivot <= v[high]) // 피벗을 제외한 앞의 값까지가 유효 범위
			high--;

		if (low < high)
			swap(v[low], v[high]);
	}

	swap(v[left], v[high]);
	return high;
}

2번의 알고리즘에 따라 피벗이 중앙에 올 때까지 정렬을 수행한다.

그리고 이 그림처럼 피벗이 중앙에 오고, 좌측에는 피벗보다 작은값이, 우측에는 피벗보다 큰 값이 오게되면 

swap(v[left], v[high])로 기존 피벗 값과 중앙의 값을 교환해준다.

즉, high에는 새로 변경된 피벗의 위치가 저장되어 있으므로, high의 값을 반환한다.

 

(2) 퀵 정렬 함수를 재귀적 호출

void QuickSort(vector<int>& v, int left, int right) // left ; 시작 위치, right ; 끝 위치
{
	if (left > right)
		return;

	int pivot = Partition(v, left, right);
	QuickSort(v, left, pivot - 1); // 중앙 피벗 기준 좌측 배열
	QuickSort(v, pivot + 1, right); // 중앙 피벗 기준 우측 배열
}

예외 처리를 통해 left 인덱스가 right 인덱스보다 크면 함수를 종료한다.

Partition 함수를 실행시켜 반환된 피벗의 위치인 high의 값을 pivot 변수에 저장한다.

그리고 재귀적 호출을 통해서 중앙 피벗 기준으로 좌측과 우측 배열의 정렬을 실시한다.

 

(3) 좌측 부분 배열 정렬

첫번째 재귀적 호출에서 right의 값이 pivot - 1(중앙 기준 왼쪽 부분 배열의 끝)으로 바뀌었으므로, 배열의 첫번째 원소를 새로운 피벗으로 삼아 정렬 알고리즘을 실행한다.

 

(4) 우측 부분 배열 정렬

두번째 재귀적 호출에서 left의 값이 pivot + 1(중앙 기준 오른쪽 부분 배열의 시작)으로 바뀌었으므로, 배열의 (중앙 + 1)번째 원소를 새로운 피벗으로 삼아 정렬 알고리즘을 실행한다.

 

 

4. 시간 복잡도

(1) 최악의 경우

배열이 이미 오름차순 혹은 내림차순으로 정렬되어 있을 때.

O ( N^2 )

 

(2) 평균

최악의 경우가 아닐 때.

O ( N logN )