퀵 정렬(Quick Sort)

정렬을 하려는 n개의 원소들이 있고, 랜덤 원소 P(Pivot이라 칭함)가 있다고 했을 때,

이 P를 기준으로 n-1개의 원소들을 왼쪽 / 오른쪽 분리했다고 생각해봅시다.

 

7 8 1 4 2 3 (Pivot) 10 17 11 14 13 12  // 중앙에 있는 값을 Pivot으로 선정했을 때

 

P를 기준으로 왼쪽에 있는 원소 / P를 기준으로 오른쪽에 있는 원소가 정렬되있는 상태입니다.

이러한 왼쪽 오른쪽 분할을 계속해서 반복하여 SIZE 줄여나가면서 정렬하는 방식이 퀵정렬입니다.

 

퀵 정렬은 분할 정복(Divede & Conquer)를 이용한 정렬 방식이며,

기준점(Pivot)을 이용하여 Pivot의 왼쪽은 모두 작은수, 오른쪽은 모두 큰 수로 두어

이 과정을 반복하여 완성된 리스트로 정렬을 하는 방식입니다.

 

 

퀵정렬을 시행할 때, Pivot (= 기준점)이라고 부르는 것에 대한 설계가 필요합니다.

맨 앞의 원소를 Pivot으로 주어 분할하는 방식이 있고, 맨 뒤의 원소를 Pivot으로 하는 방식...

여러가지의 방식이 존재하나,

맨 앞의 원소를 Pivot이라 지정하고 설명을 하겠습니다.

 

아래는 퀵정렬을 구현하면서 생각해야할 3가지 특징입니다.

기준점(Pivot)의 왼쪽부터 시작하여 Pivot보다 큰 값을 찾음 : index를 i라 하고 i번째 원소를 찾음 끝에서부터 왼쪽으로 시작하여 Pivot보다 작은 값을 찾음 : index를 j라 하고 j번째 원소를 찾음 찾은 두 값의 인덱스의 상태를 보고 Swap을 누구와 할지 결정한다   * i < j인 경우에는 arr[i]와 arr[j]를 SWAP, i와 j가 엇갈리기(i>j)까지 계속해서 탐색을 진행한다.   * i > j인 경우는 '엇갈렸다'라고 표현하며 Pivot으로 설정된 값과 Pivot보다 작은 값을 Swap후 재분할한다.

 

배열 : 21 10 12 20 25 13 15 22 첫 번째 Pivot : 21

 

Pivot				i		j
0	1	2	3	4	5	6	7
21	10	12	20	25	13	15	22

 

1. Pivot(21, idx = 0)의 왼쪽부터 출발하여 Pivot보다 큰 값이 처음으로 나타난 숫자 : 25, index i = 4

2. 끝(22, idx = 7)에서 왼쪽으로 출발하여 Pivot보다 작은 값이 처음으로 나타난 숫자 : 15, index j = 6

    - i(4) < j(6)인 경우이므로 두 값이 엇갈리지 않은 상황이므로 두 값을 교체합니다.

 

Pivot					j	i
0	1	2	3	4	5	6	7
21	10	12	20	15	13	25	22

이 i,j의 idx가 유지된 상태에서 계속 탐색을 진행합니다.

 

1.Pivot(21) 보다 큰 값이 나타나는 곳 : 25, idx = 6

2.끝(22)보다 작은 값이 나타나는 곳 : 13, idx = 5

   - i(6) > j(5)로 '엇갈렸다'의 상태에 도달하였습니다.

   - 이 때는 Pivot(21)과 작은 값(idx j = 5가 가리키는 값, 13)을 Swap합니다.

					Pivot
0	1	2	3	4	5	6	7
13	10	12	20	15	21	25	22

 

위의 상태를 잘 관찰해보면, 21(Pivot)을 기준으로 왼쪽 리스트 (idx 0~4)까지는 Pivot보다 작고,

21(Pivot)을 기준으로 오른쪽 리스트(idx 6~7)은 모두 큰 값입니다.

이 상태로 왼쪽 / 오른쪽을 분할하여 

왼쪽은 다시 Pivot(13)부터 시작, 오른쪽은 Pivot(25)부터 시작하여 다시 정렬을 시작합니다.

 

Pivot		j		i
0	1	2	3	4
13	10	12	20	15

1.Pivot(13) 보다 큰 값이 처음으로 나타나는 곳 : 15, idx = 4

2.끝(15)보다 작은 값이 처음으로 나타나는 곳 : 13, idx = 2

   - i(4) > j(2)로 '엇갈렸다'의 상태에 도달하였습니다.

   - 이 때는 Pivot(13)과 작은 값(idx j = 2가 가리키는 값, 12)을 Swap합니다.

 

		Pivot
0	1	2	3	4
12	10	13	20	15

위의 상태를 잘 관찰해보면, 13(Pivot)을 기준으로 왼쪽 리스트 (idx 0~1)까지는 Pivot보다 작고,

13(Pivot)을 기준으로 오른쪽 리스트(idx 3~4)은 모두 큰 값입니다.

 

다시 왼쪽 / 오른쪽 분할을 하게 되면 10 12 / 13 / 15 20으로 분할이 됩니다.

왼쪽 리스트(12 10)을 기준으로 12보다 큰 값은 없는데, 이 때 idx i는 이미 증가된 상태로 2를 가리키게 되고

j는 1을 가리키게 되므로

무조건 엇갈린 상황이기 때문에 자연스럽게 SWAP합니다.

이 분할을 모두 마치게 되면 정렬이 되는 것이죠!

우측 리스트(20 15)도 동일하게 정렬이 됩니다.

 

 

============================================================================================

이 정렬 방식은 O(NlogN)의 시간복잡도를 가지는 방식입니다.

N개의 데이터에 대하여 분할을 통해 size를 줄여나가는 방식으로 정렬을 하기 때문입니다.

 

그러나, 모든 경우에서 O(NlogN)이라고 말할 수는 없습니다.

이미 정렬된 데이터 (1 2 3 4 5 6 7 8 9 10)이 들어왔다고 가정하면,

Pivot을 기준으로 n-1번, n-2번, n-3번....의 분할을 하고 결국 O(n^2)을 맞닥뜨리게 됩니다.

 

 

"만약 정렬하기 위한 데이터가 랜덤 순서로 주어진다면?"

랜덤 재배치는 O(n)시간에 구성이 가능하며, 최악의 경우(이미 데이터가 정렬되있는 경우)가 아예 배제되지는 않지만

랜덤으로 수를 배치했을 때 이미 다 정렬이 되있는 경우가 얼마나 있을까요? 이는 거의 최악의 운입니다.

없는 경우라고 봐도 무방한 것이죠. 

 

충분히 좋은 Pivot은 최대한 중앙값에 가깝게 위치한 Pivot이고,

충분히 좋지 못한 Pivot은 중앙값에 멀리 위치한 Pivot이 될 것입니다.

 

이 구간을 4개의 구간으로 나누어 표현하면 아래와 같습니다.

충분히 좋지 못한 Pivot

충분히 좋은 Pivot

충분히 좋은 Pivot

충분히 좋지 못한 Pivot

 

충분히 좋은 Pivot을 가질 확률이 1/2,

충분히 좋지 못한 Pivot을 가질 확률이 1/2로 동일하다고 볼 수 있습니다.

 

평균 절반은 충분히 좋은 Pivot을 가져서 분할을 하고, 절반은 충분히 좋지 못한 Pivot을 가져서 분할을 한다는 것이죠.

좋지 못한 분할을 하면 분할 횟수를 2배만큼 늘리고, 좋은 분할을 하면 분할 횟수를 2배만큼 줄이나

이 Pivot을 가질 확률들이 각각 1/2로 동일하니,

이 것의 평균으로 O(NlogN)이라고 할 수 있습니다.

 

============================================================================================

하여 "랜덤 퀵 정렬은 높은 확률로 어떠한 입력에 대해서도 O(NlogN) 시간에 실행이 된다"고 말할 수 있겠습니다!

============================================================================================

 

 

 

 

#include <iostream>

using namespace std;

int arr[8] = { 21,10,12,20,25,13,15,22};

void quick_sort(int arr[], int start, int end)
{
	if (start < end) // 원소가 1개도 없는 경우에는 진행하지 않음.
	{
		int pivot = start; // pivot은 맨 왼쪽 인덱스임
		int i = start + 1; 
		int j = end;

		while (i <= j)
		{
			if (i <= end && arr[i] <= arr[pivot]) // 끝 인덱스보다 i가 작고 pivot보다 큰 값을 만날 때까지 반복
			{
				i++;
			}

			if (j > start && arr[j] >= arr[pivot]) // j가 start보다 크고 pivot보다 작은 값을 만날 때 까지 반복
			{
				j--;
			}

			if (i > j) // 엇갈리면 pivot과 작은 값을 스왑
			{
				int temp = arr[j];
				arr[j] = arr[pivot];
				arr[pivot] = temp;
			}
			else // 아니라면 i와 j가 가리키는 값을 서로 스왑
			{
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}

		quick_sort(arr, start, j - 1); // 왼쪽
		quick_sort(arr, j + 1, end); // 오른쪽
	}
}

int main(void) {
	quick_sort(arr, 0, 7);

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

	return 0;
}