퀵 정렬(Quick Sort) C 언어

요즘 다시 C 언어를 공부하는 중입니다.

표준을 지키려고 KNK의 C Programming: A Modern Approach, 2nd ed. 을 보고 있는데

역시 굉장히 좋은 책입니다.

 

프로그래밍 언어를 공부하는 방법으로 저는 사소한 것들도 계속 따라해보려고 하는 편입니다.

 

이전에 자료구조를 배우며, 정렬을 정리해본 적은 있으나 기억이 안나는 관계로..

 

이 책에 나왔던 퀵 정렬을 정리해보고자 합니다.

 

 

https://wikidocs.net/book/2494

C 프로그래밍: 현대적 접근

 

 

Quick Sort

---

퀵 정렬(Quick Sort)는 찰스 앤터니 리드 호어가 개발한 정렬 알고리즘입니다.

 

이름부터 Quick인 만큼 평균적으로 다른 알고리즘에 비해 매우 빠른 시간에 동작합니다.

평균 시간복잡도는 $O(n log_2 n)$입니다.

 

https://wikidocs.net/86387

6 재귀

 

이 글을 읽어보고 오시면 좋겠습니다.

 

퀵 정렬은 분할-정복 알고리즘입니다. 분할-정복(divide-conquer)알고리즘은 문제를 작은 문제로 나누고 각각을 해결한 다음 그것들을 모아서 큰 문제를 해결하는 방법입니다.

 

위 책대로 설명하겠습니다.

Quick Sort를 구성하는 요소는 pivot(여기서는 그냥 part_element로 사용했습니다.), low, high가 있습니다.

알고리듬은 두 가지 "표식marker"에 의존하는데, 각각 "저점low"과 "고점hight"라 부른다. 이 표식들은 배열에서 원소의 위치를 추적하는 역할을 한다. 초기엔 저점이 배열의 첫번째 원소를, 고점이 배열의 마지막 원소를 가리킨다. 첫번째 원소 (분할 원소)를 다른 임시 공간에 복사하여 배열에 "구멍"을 만드는 것으로 알고리듬은 시작된다. 다음, 고점이 오른쪽에서 왼쪽 순으로 분할 원소보다 더 작은 원소를 찾을 때까지 이동한다. 분할 원소보다 더 작은 원소를 찾는 순간 해당 원소를 저점이 가리키는 원소에 값을 복사한다. 이러면 새로운 구멍(고점
이 가리키는 곳)이 생긴다 이제부턴 저점을 왼쪽에서 오른쪽 순으로 분할 원소보다 더 큰 원소가 나올 때까지 움직인다. 분할 원소보다 더 큰 원소를 찾는다면 해당 값을 고점이 가리키는 구멍에 복사한다. 이 과정은 저점과 고점이 서로 순서를 바꿔가며 진행하는 형태를 띠며, 저점과 고점이 배열 중간 어딘가에서 만나면 중단된다. 그 시점이 되면 둘 다 한 구멍을 가리킬 것이다; 그 구멍에 분할 원소를 복사해넣어주면 된다. 

 

 

여기 주어진 배열이 있습니다.

위에 인용한 것처럼 첫 번째를 빈칸으로 만들겁니다. pivot을 12로 두어 따로 두는 것이죠

 

우리의 목표는 12의 자리를 찾아주는 것입니다. 동시에 12의 왼쪽에는 12보다 작은 수가, 오른쪽에는 12보다 큰 수가 오도록 하는 것입니다.

 

교재에 나와있는 코드는 다음과 같습니다.

#include<stdio.h>

#define N (10)


void quicksort_recursive(int arr[], int low, int high);
int split(int arr[], int low, int high);


int main(void)
{
	int arr[N];
	int i=0;
	
	printf("정렬할 숫자 %d 개를 입력하세요 : ",N);
	for(i=0; i<N; i++)
	{
		scanf("%d",&arr[i]);
	}
	
	quicksort_recursive(arr, 0, N-1);
	
	printf("정렬 이후 : ");
	for(i=0; i<N; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	
	return 0;
	
}

void quicksort_recursive(int arr[], int low, int high)
{
	int middle = 0;
	
	if(low >= high)
	{
		return;
	}
	
	middle = split(arr, low, high);
	quicksort_recursive(arr,low,middle-1);
	quicksort_recursive(arr,middle+1, high);
	
}


int split(int arr[], int low, int high)
{
	int part_element = arr[low];
	
	for( ; ; )
	{
		while(low < high && part_element <= arr[high])
		{
			--high;
		}
		if (low >= high)
		{
				break;
		}
		
		arr[low++] = arr[high];
		
		while(low < high && arr[low] <= part_element)
		{
			low++;
		}
		if(low >= high)
		{
			break;
		}
		
		arr[high--] = arr[low];
		
	}
	
	arr[high] = part_element;
	
	return high;
}

다시 돌아가서, 위 코드에서는 high를 먼저 확인합니다.

pivot인 12와 high를 비교하여 high가 작다면 high에 있는 수를 low로 옮깁니다. 그리고 low를 1 증가시킵니다.

 

low가 3에 오게 되는데 low를 확인합니다. 6이 12보다 작으므로 그냥 low를 1 증가시킵니다.

 

코드에서는 while 문에서 pivot(part_element)보다 작으므로 계속 반복이 돌아서 low가 증가합니다.

 

이제 18은 12보다 크므로 18을 high 자리에 옮기고 high를 1 감소시킵니다.

high에서 15는 12보다 크므로 high를 1 감소시킵니다.

7은 12보다 작으므로 low로 옮기고 high를 1 감소시킵니다.

low와 high가 같아졌으므로 반복을 종료하고 high, 즉 두개가 겹쳐있는 자리에 pivot을 놓아둡니다.

이러면 pivot, 12의 자리를 찾았죠.

 

12를 기준으로 왼쪽에서 다시 quick sort를, 오른쪽에서 quick sort를 실시합니다.

 

이렇게 퀵 정렬이 완성되었습니다.