Quick Sort (퀵 소트)

참고 문헌 :

mygumi.tistory.com/308

퀵소트 알고리즘 :: 마이구미

 

blog.naver.com/ndb796/221226813382

5. 퀵 정렬(Quick Sort)

 

gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

 

---

1. 퀵 소트 개념 정리

- 분할 정복(Divide and Conquer)을 통하여 구현합니다.

- 시간 복잡도는 최악의 경우 O(N ^ 2)이고 평균적으로 O(NlogN)을 가집니다.

- 합병 정렬(merge sort)과 다르게 비 균등하게 정렬합니다.

---

2. 퀵 소트 정렬 과정

1) 배열의 원소 하나를 선택합니다. 이를 피벗(pivot)이라고 합니다.

2) 피벗을 기준으로 오른쪽에는 피벗보다 큰 수를 왼쪽으로 작은 수를 옮깁니다.(오름 차순으로 정렬 시)

3) 피벗을 제외하고 왼쪽, 오른쪽 배열을 분할합니다.

4) 분할 한 배열의 크기가 0 또는 1이 아닌 경우 1 ~ 3을 반복합니다.

 

ex)

1

4

3

5

2

를 정렬한다고 하면 과정은 다음과 같습니다. ( 주황색으로 채워진 칸은 정렬 완료 상태를 의미합니다. )

 

1번) pivot 선택하기 : pivot = 3(랜덤 선택)

 

2번) 정렬하기

1

2

3

5

4

3번) 배열 분할

 

left :

1

2

right :

5

4

 

4번) left 만족, right 만족

 

left - 1번) pivot 선택 : pivot = 1(랜덤 선택)

 

left - 2번) 정렬하기

1

2

 

left - 3번) 배열 분할하기

left_left

NULL

 

left_right

2

 

left - 4번) left_left 불만족, left_right 불만족 => left 종료

 

현재 배열 상태

1

2

3

5

4

 

right - 1번) pivot 선택 : pivot = 5(랜덤 선택)

 

right - 2번) 정렬하기

4

5

 

right - 3번) 배열 분할하기

right_left

4

 

right_right

NULL

 

right - 4번) right_left 불만족, right_right 불만족 => right 종료

 

현재 배열 상태

1

2

3

4

5

 

----- 더 이상 분할할 공간이 없으므로 정렬 종료 -----

 

최종 정렬 결과

1

2

3

4

5

 

 

pivot을 선택할 때 랜덤이라는 말을 사용하였는데 구현의 편리함을 위하여 보통 배열의 첫 번째 데이터를 pivot으로 선택합니다.

---

3. 퀵 소트 구현하기

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void quick_sort(int arr[], int s, int e) {
	
	//--- 1) select the pivot ---//
	int pivot = s;	
	int left = s + 1, right = e, tmp;

	//--- 2) sort the Array ---//
	while (left <= right) {
		while (left <= e && arr[pivot] >= arr[left])
			left++;

		while (s < right && arr[pivot] <= arr[right])
			right--;

		tmp = arr[right];
		if (left > right) {
			arr[right] = arr[pivot];
			arr[pivot] = tmp;
			pivot = right;
		}
		else {
			arr[right] = arr[left];
			arr[left] = tmp;
		}
	}
    
	//--- 3, 4) Check Array size and split Array ---//
	if (pivot - s > 0)
		quick_sort(arr, s, pivot - 1);
	if (e - pivot > 0)
		quick_sort(arr, pivot + 1, e);

}

int main(void) {
	srand((unsigned int)time(NULL));
	
	int arr[10] = {0, };
	
	for (int i = 0; i < 10; i++)
		arr[i] = rand() % 10 + 1;
	
	printf("before sort : ");
	for (int i = 0; i < 10; i++)
		printf("%2d ", arr[i]);

	quick_sort(arr, 0, 9);

	printf("\n after sort : ");
	for (int i = 0; i < 10; i++)
		printf("%2d ", arr[i]);
	return 0;
}

---

4. 추가로

퀵 소트의 최악의 시간 복잡도가 O(N ^ 2)이라고 되어있습니다. 

 

이는 바로 이미 정렬된 배열을 정렬할 때 최악의 시간 복잡도를 가지게 됩니다. 이를 해결하는 방법으로는 배열의 중간 값을 선택하면 됩니다.

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void quick_sort(int arr[], int s, int e) {
	
	//--- 1) select the pivot ---//
	int pivot = s;
	int left = s + 1, right = e, tmp;

	//--- *) code Improvement ---//
	tmp = arr[(s + e) / 2];
	arr[(s + e) / 2] = arr[s];
	arr[s] = tmp;

	//--- 2) sort the Array ---//
	while (left <= right) {
		while (left <= e && arr[pivot] >= arr[left])
			left++;

		while (s < right && arr[pivot] <= arr[right])
			right--;

		tmp = arr[right];
		if (left > right) {
			arr[right] = arr[pivot];
			arr[pivot] = tmp;
			pivot = right;
		}
		else {
			arr[right] = arr[left];
			arr[left] = tmp;
		}
	}
	
	//--- 3, 4) Check Array size and split Array ---//
	if (pivot - s > 0)
		quick_sort(arr, s, pivot - 1);
	if (e - pivot > 0)
		quick_sort(arr, pivot + 1, e);

}

int main(void) {
	srand((unsigned int)time(NULL));
	
	int arr[1000] = {0, };

	for (int i = 0; i < 1000; i++)
		arr[i] = rand() % 10 + 1;
	
	printf("before sort : ");
	for (int i = 0; i < 1000; i++)
		printf("%2d ", arr[i]);

	quick_sort(arr, 0, 999);

	printf("\n after sort : ");
	for (int i = 0; i < 1000; i++)
		printf("%2d ", arr[i]);

	return 0;
}