[자료구조 복습 10] Quick Sort 퀵 정렬

일반 퀵소트 

 

1. 파티션 함수를 통해 '피벗값'을 정한다.

  - 여기서 파티션 함수의 수행은 이러하다

 

1) 피벗값을 중심으로 왼쪽에는 피벗보다 작은 값을, 오른쪽에는 피벗보다 큰 값을 정렬한다.

 

2) 이를위해 left와 right이 배열을 따라 내려오면서, arr[left] > pivot 인경우와 arr[right]<pivot인 경우

서로 스왑해준다. 

 

3) 이를 반복하다가 left > right 이 되는 경우, 즉 right과 left가 서로 교차하는 경우 루프를 멈추어준다.

 

4) 멈춘 곳에서 right과 우리가 정한 pivot의 자리를 바꾸어준다. 왜냐하면, pivot을 맨 첫번째 요소로 선택한다 했을때, pivot은 자신보다 작은 값과 바꾸어 져야하는데 pivot보다 작은 값을 마지막으로 가리키고 있는 것은 right이기 때문이다. 

즉,pivot값 <pivot보다 작은 값 j> <i 피벗보다 큰 값> 이렇게 위치해있으므로 둘을 바꾸어주는 게맞다.

 

5) 따라서 right자리에 pivot이 들어가므로 right을 피벗값으로 리턴해준다.

 

2. 반환된 피벗값의 인덱스를 중심으로 배열을 나누어 반복한다. 해당 피벗자리는 이미 정렬되었으므로, 피벗자리를 중심으로 앞, 뒤 배열을 나누어준다

이 과정을 배열을 더이상 나눌 수 없을 때까지 계속한다.

 

퀵소트 역시, 분할정복으로 재귀함수의 깊이가 O(log2N)이다. 또한 재귀마다 실행되는 파티션 내부에서 비교 및 교환 연산이 평균적으로 N번 수행되기 때문에 O(Nlog2N)이라고 할 수 있다.

 

사진출처: https://cs.nyu.edu/~gottlieb/courses/2000s/2002-03-fall/alg/lectures/lecture-22.html

하지만, 이러한 일반 퀵소트의 경우 피벗값의 선정이 문제가 될 수 있다. 특히나 피벗값을 맨 앞 값이나 맨 뒷값으로 선정했는데, 배열이 이미 정렬된 경우에는 재귀의 깊이가 N까지 가게 된다. 여기에 파티션에서의 연산이 재귀마다 N번 수행된다고 했을 때 최악의 경우 (이미 정렬된 배열) 에 퀵소트의 시간복잡도는 O(N^2)이다.

 

 

<C++소스>

#include <iostream>
using namespace std;

void swap(int arr[], int index1, int index2) {
	int tmp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = tmp;
}

int partition(int arr[], int first, int last) {
	int pivot = arr[first];
	//들어가서 먼저 ++ -- 될 것이므로..
	int i = first ;
	int j = last+1;
	
	
	while (1) {
		while (++i < last && arr[front] < pivot); //첫번째 조건식은 ++i < j 로 바꿔도 무방하다
                                                  //어차피 두번째 조건식때문에 루프가 멈추는 경우는 i<j이기 때문에
		while (--j> first >= front && arr[rear] > pivot);
		//rear >= front 인 경우도 루프 돌아가도록 처리해야함 -> 그래야지 언젠가 rear와 front가 엇갈린다.
		if (front < rear) swap(arr, front, rear);
		if (rear <front) break;
	}
	swap(arr, first, rear);
	return rear;
}

void Quick_sort(int arr[], int first, int last) {
	if(first<last)
	{
		int q = partition(arr, first, last);
		Quick_sort(arr, first, q-1); //인덱스 q는 이미 정렬되었음. q를 기준으로 양옆값 보기.
		Quick_sort(arr, q + 1, first);
	}
}