알고리즘: Divide and conquer를 이용한 quick sort 구현 (feat. c++)

 

< 빠른정렬(quick sort) >

 

 

이름은 빠른 정렬이지만 사실상 가장빠른 정렬 알고리즘이라고 할 수는 없다.

 

차라리 분할교환정렬(partition exchange sort)라고 하는게 더 정확하다.

 

이번 포스팅은 quick sort를 분할 정복으로 구현한다.

 

사실상 quick sort 분할정복구현에는 가중치가 분할 > 정복이다.

 

즉 정복에는 별거 없다. 하지만 분할과정이 까다롭다.

 

 

 

quick sort를 분할 정복으로 다음과 같이 나눈다. 

 

배열의 원소 중 하나를 pivot으로 잡는다. (어떤 값을 pivot으로 잡든 상관 없다. 단지 기준을 만들어주기 위함이다)

 

주로 배열의 가장 끝값이나 처음 값을 기준으로 잡는다. 

 

예를 들어 다음과 같은 배열이 있다.

 

array = { 6, 2, 5, 3, 7, 10, 6, 9 }

 

우리는 pivot값을 0이라고 하자 

 

그리고 unknown index값이라 하여 i를 잡고

last small index라고 해서 j 값을 잡는다. 

 

array[pivot] > array[i] 라 하면 j에 값을 하나 더해주고

array[i]와 array[j]를 swap시킨다.

 

i는 매 반복시마다 값을 증가시켜준다.

 

 

1) i = 1

 

4  2  5  3  7  10  6  9

    i

    j

 

 

2) i = 2

 

4  2  5  3  7  10  6  9

        i

    j

 

 

3) i = 3

 

4  2  5  3  7  10  6  9

           i

        j

 

 

4) i = 4

 

4  2  3  5  7  10  6  9

               i

        j

 

 

5) 이렇게 끝까지 반복하면 다음과 같아진다.

 

4  2  3  5  7  10  6  9

                           i

        j

 

 

6) 마지막으로 

 

pivot = j

array[pivot]과 array[0]을 swap해 준다. 

 

 

이후 5  2  3  4  7  10  6  9 로 정렬되고, 

 

이렇게 pivot을 기준으로 좌측에는 pivot 보다 작은 값

우측에는 pivot보다 큰 값으로 나누는 과정을 파티션(partition)이라 한다. 

 

 

다음은 파티션 함수이다. 

void partition(int num_list[], int low, int high, int &pivot_index) {

	pivot_index = low;
	int pivot_item = num_list[low];

	int i = low + 1; // unknown
	int j = low; // lastsmall
	while (i <= high) {
		if (pivot_item > num_list[i]) {
			j++;
			swap(num_list[i], num_list[j]);
		}
		i++;
	}
	pivot_index = j ;
	swap(num_list[low], num_list[pivot_index]);
}

 

 

 

 

 

이렇게 파티션을 끝낸후, pivot을 기준으로 

 

시작값부터 pivot - 1

pivot + 1부터 끝값으로 나누어 

 

quick sort를 시행해준다. 

 

void quick_sort(int num_list[], int low, int high) {
	int pivot_index;

	if (high > low) {
    
		partition(num_list,low, high, pivot_index);
		quick_sort(num_list, low, pivot_index - 1);
		quick_sort(num_list, pivot_index + 1, high);

	}
}

 

 

 

<Main>

int main() {
	int array[10] = { 4,2,3,1,5,8,7,10,6,9 };

	quick_sort(array, 0, 9);

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



	return 0;
}

 

1
2
3
4
5
6
7
8
9
10