[알고리즘]분할정복을 이용한 정렬 알고리즘 - 병합 정렬 & 쾌속 정렬

[ 분할 정복 ]

 

 분할 정복 (divide-and-conquer) 접근 방법은 주어진 문제의 규모가 클 때 문제를 작은 부분 문제로 나눠서 해결하는 방식입니다. 

 

 부분 문제로 나누는 작업을 반복하여 그 해답을 찾고, 다시 그 해답을 합쳐서 처음 문제에 대한 해답을 유도하는 것입니다. 

 

 

• 분할 정복 알고리즘의 세 단계

1. 분할(divide) : 주어진 문제를 동일한 방식으로 해결할 수 있는 여러 부분 문제로 나눕니다. 

 

2. 정복(conquer) : 각 부분 문제에 대한 해답을 구합니다. 

 

3. 결합(combine) : 각 부분 문제의 해답을 결합하여 전체 문제에 대한 해답을 구합니다. 

 

 

 일반적인 정렬 알고리즘(bubble sort, insertion sort, selection sort)은 한 쌍식 비교하여 정렬을 하기 때문에 O(N^2)이라는 시간 복잡도를 가지게 됩니다. 

 

 이보다 더 빠르게 정렬을 하기 위해 분할 정복을 사용하며, 분할 정복 알고리즘을 사용한 정렬 알고리즘이 바로 병합 정렬(merge sort)와 쾌속 정렬(quick sort)입니다. 

 

 

 

 

[ 병합 정렬 Merge Sort ] 

 

 병합 정렬(merge sort)은 잘 알려진 정렬 알고리즘 중 하나이며, 많은 원소로 구성된 배열을 작은 크기의 부분집합으로 나누어 각각을 정렬하고 정렬된 부분집합을 오름차순 또는 내림차순을 유지하면서 합치는 방식입니다. 

 

 시간 복잡도는 O(N logN)입니다. 

 

 

1. 분할(divide) : 배열을 더 이상 쪼개지지 않을때까지 절반으로 분할한다. 

 

2. 정복(conquer) : 각 절반을 재귀적으로 정렬한다.

 

3. 결합(combine) : 정렬된 두 부분 배열을 병합한다. 

 

 

출처: https://images.velog.io/images/devjade/post/e65e83c6-0984-4df9-9a7b-51ff8046a3a1/image.png

 

void merge(int ls, int le, int rs, int re, int A[])
{

	int lptr = ls, rptr = rs, bptr = 0;
    	int *B = (int*)calloc((le - ls) + (re - rs) + 2, sizeof(int));
    
    	while(lptr <= le && rptr <= re){
			if(A[lptr] < A[rptr])
        			B[bptr++] = A[lptr++];
			else
        			B[bptr++] = A[rptr++];
		}
    
    	if(lptr > le)
    		for(int i = rptr; i <= re; i++)
        		B[bptr++] = A[i];
	if(rptr > re)
    		for(int i = lptr; i <= le; i++)
        		B[bptr++] = A[i];
            
	A <- B;
}

void merge_sort(int s, int e, int A[])
{
	if(s == e)
    		return;
        
    	int m = (s + e) / 2;
    	merge_sort(s, m, A);
    	merge_sort(m + 1, e, A);
    	merge(s, m, m + 1, e, A);
}

 

 

 

 

 

 

[ 쾌속 정렬 Quick Sort ] 

 

 병합 정렬의 목적이 대용량의 데이터를 정렬하는 것이라면, 퀵 정렬(quick sort)는 평균 실행 시간을 줄이는 것이 목표입니다. 

 

 퀵 정렬은 주어진 배욜울 작은 크기의 부분 배열로 나누고, 각 부분 배열을 정렬 후, 병합합니다. 

 

 병합 정렬과 매우 유사해 보이지만, 퀵 정렬의 key point는 분할입니다. 

 

 피봇(pivot)이라는 원소 P를 기준으로 배열을 분할합니다. 왼쪽 부분 배열 L은 피봇 P 보다 작거나 같은 원소들의 집합이고, 오른쪽 부분 배열 R은 피봇 P 보다 큰 원소들의 집합입니다. 

 

 시간 복잡도는 O(N logN)입니다. 

 

 

 1. 분할(divide) : 피봇(pivot)을 기준으로 두 부분으로 분할한다. 

 

 2. 정복(conquer) : 재귀적으로 각 부분 배열을 L P R 순으로 정렬을 한다. 

 

 

 

분할 전
5 (pivot)	6	7	3	1	9	2	4	8

 

분할 후
L				pivot	R
4	2	3	1	5	9	7	6	8

 

 

int partition(int s, int e, int A[])
{

	int pivot = A[s];
    int left = s + 1;
    int right = e;
    
    while(left <= right){
	while((A[right] >= pivot) && (left <= right))
        	right--;
        while((A[left] <= pivot) && (left <= right))
        	left++;
            
        if(left <= right)
        	swap(A[left], A[right]);
	}
    swap(A[right], A[s]);
    return right;
}

void quick_sort(int s, int e, int A[])
{

	if(s >= e)
    	return;
        
    int m = partition(s, e, A);
    quick_sort(s, m - 1, A);
    quick_sort(m + 1, e, A);
}