'분할 정복'에 해당되는 글 1건

퀵정렬(Quick Sort)

오늘 다루어볼 정렬 주제는 바로 퀵정렬입니다. 이름만에서도 알 수 있듯이 빠른 속도를 자랑합니다.

하지만 다른 정렬 알고리즘에 비해서 병합정렬과 더불어 까다로운 정렬 알고리즘인데요. 사실 이해만 정확히 한다면 그리 어려운 알고리즘은 아니지요.

개념

퀵 정렬에서 우선 pivot이라는 개념부터 알아야합니다. 뭐 어렵지 않습니다. 그냥 비교할 기준이라고 생각하면 되겠네요.

배열의 원소들은 피봇보다 작으면 왼쪽, 피봇보다 크면 오른쪽에 놓이는데요.

바로 아래 그림을 보면서 이해하도록 합시다.

정렬되지 않은 배열 arr= {5,6,7,3,4,2,1,9}가 있다고 하겠습니다. 이 배열에서 피봇은 1번째 원소인 5라고 가장하겠습니다.

퀵 소트를 한번 돌게 된다면 5를 기준으로 작은 원소들은 모두 왼쪽에, 큰 원소들은 모두 오른쪽에 놓이게 됩니다.

이제 이런 짓을 계속하다가 보면 어느 순간 정렬된 형태가 나오는 것이죠. 병합정렬을 배운 분이라면 뭔가 보이지 않나요? 

퀵정렬의 분할정복

퀵 정렬은 병합정렬과 마찬가지로 분할 정복의 아주 대표적인 예입니다. 하지만 정직하게 2로 나누는 병합정렬과는 다르게 퀵정렬은 비대칭으로 두동강을 내버립니다. 내 얼굴

아래 그림에서 일부를 쪼개고 다시 합치는 과정이 보이세요? 이것이 분할-정복의 개념입니다. 

분할 퀵정렬은 우선 피봇을 기준으로 2개로 나누지요. 나누고 쪼개는 것이 바로 분할입니다. 분할을 통해서 큰 문제를 여러개의 문제로 조각을 내서 더 쉽게 문제를 푼다는 개념입니다.

정복 분할 이후에 다시 정렬의 과정을 거치게 됩니다. 

병합 정복 이후 다시 합치는 과정을 병합이라고 합니다. 원래의 커다란 문제를 풀기 위해서는 해결했던 조각난 문제들을 다시 합쳐야하기 때문에 병합이라는 과정이 필요하죠. 

구현

다음의 코드가 바로 퀵소트를 구현한 것입니다.

void swap(int *a, int *b) {
	int t = *a;
	*a = *b;
	*b = t;
}

void quickSort(int left, int right, int *arr) {
	int pivot = arr[left];
	int less = left;
	int more = right+1;
	
	if (left < right) {
		do {
			do
				less++;
			while (less <= right && arr[less] < pivot);

			do
				more--;
			while (more >= left && arr[more] > pivot);

			if (less < more)
				swap(&arr[less], &arr[more]);

		} while (less < more);
		swap(&arr[left], &arr[more]);
		
		quickSort(left, more - 1,arr);
		quickSort(more + 1, right, arr);
	}

}

소스코드를 보면 가장 왼쪽의 원소가 피봇이라는 것을 알 수 있네요. 이 피봇값을 기준으로 작다면 배열에 왼쪽으로 놓고 크다면 오른쪽으로 놓는 것이죠. 그 후에 피봇의 위치를 찾고 다시 피봇의 위치 기준으로 배열을 쪼개서 재귀호출을 하게 됩니다.

우리는 do ~ while 문으로 위 코드를 쓰기 때문에 more은 right의 한칸 더 뒤에 있어야합니다. do ~ while문의 특징은 우선 한번은 실행시키기 때문입니다. 

역시 less 그렇습니다. 가장 첫번째 left의 위치부터 시작해야 피봇 다음 원소부터 비교할 수 있는 것입니다.

어려울 수 있으니 다시 그림과 함께 이 코드를 봅시다.

우선 초기 상태는 이렇습니다. 그림에서도 볼 수 있듯이 less는 left의 위치에 있고, more은 right의 다음번째에 있습니다. 이제 do ~ while문을 실행하는 거죠.

less는 5보다 큰 원소가 있으면 멈추고 more은 5보다 작은 원소가 있으면 멈춥니다.

자, 6과 1이 걸리게 되겠죠? 6은 5보다 크니까 오른쪽에 있어야하고 1은 5보다 작으니 왼쪽에 있어야합니다. 그러니까 less와 more의 원소를 교환합시다. 그 후 계속 이 과정을 반복할 겁니다.

이제는 7과 2가 걸리게 되겠네요. 역시 교환합시다.

3과 4는 5보다 작으니까 지나가고 less는 7을 만나게 되면 멈춥니다. 그리고 more은 4를 만날때까지 왼쪽으로 가게 되죠. 하지만 이때 more과 less가 교차하게 됩니다. 이때 우리는 more과 less 사이의 지점, 그 지점이 바로 피봇이 위치하게 되는 지점이 되는 겁니다. 그러니 피봇이 있는 위치 left와 more과 swap하게 되면 5를 기준으로 작은 원소는 왼쪽에, 큰 원소들은 오른쪽에 위치하게 되는 것이죠.

최종상태는 위와 같습니다. 이제 5(pivot)을 기준으로 다시 이러한 과정을 반복하게 됩니다.

이제 이해가 되셨나요?

시간복잡도

위의 분할 정복의 그림에서 봤듯이 계속 두개로 쪼개 n번 비교하게 되므로 시간 복잡도는 평균적으로 O(nlogn)이 됩니다.

하지만 이미 정렬된 배열에서도 O(nlogn)이 나오게 될까요? 이 경우에는 O(n^2)이 됩니다. 피봇의 위치가 항상 왼쪽이라면 항상 2개로 쪼개지는 것이 아니라 pivot을 제외한 배열을 정렬하게 되는 샘이지요.

하지만 퀵소트가 빠른 점은 바로 pivot은 정렬에 포함시키지 않기 때문이죠. 그러므로 병합정렬보다 빠릅니다. 그러니까 이름이 Quick Sort이지요.

그리고 퀵 정렬은 배열의 공간외에는 다른 공간을 쓰지 않기 때문에 공간복잡도는 O(n)입니다.

이상으로 퀵소트에 대한 포스팅을 마치도록 하지요. 바이바이