[C언어로 쉽게 풀어쓴 자료구조] Chapter12. 정렬 (2)

12.6 합병 정렬

● 합병 정렬의 개념

분할정복: 문제를 작은 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

문제가 충분히 작지 않아 해결이 어렵다면 분할 정복 방법을 연속으로 재적용하여 더 작게 만들어 해결

 

합병 정렬의 단계

1. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할

2. 정복(Conquer): 부분 배열 정렬. 부분 배열의 크기가 충분히 작지 않으면 순환 호출로 분할 정복 재적용

3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 통합

 

작은 문제인 부분 배열에 대해서도 다시 합병 정렬을 순환적으로 적용하면 부분 배열을 정렬할 수 있다.

 

● 합병 정렬의 알고리즘

void merge_sort(int list[],int left, int right){
	int mid;
	if(left<right){
		mid = (left + right) / 2;
		merge_sort(list,left,mid);
		merge_sort(list,mid+1,right);
		merge(list,left,mid, right);
	}
}

merge_sort 알고리즘: 중간 위치를 정하여 주어진 배열을 2개로 나누고, 이를 다시 합병하는 알고리즘

*나뉘어진 배열도 분할 합병으로 정렬시키기 때문에 순환호출을 사용

 

merge 알고리즘: 2개의 리스트의 요소들을 처음부터 하나씩 비교하여 두 개의 리스트의 요소 중

더 작은 요소를 새로운 리스트로 옮기는 과정을 두 리스트 중 하나가 끝날 때까지 반복

하나의 리스트가 먼저 끝나면 나머지 리스트의 남은 요소들을 새로운 리스트로 이동

void merge(int list[],int left, int mid, int right){
	int i,j,k,l;
	i = left; j = mid+1; k= left;
	
	while(i<=mid && j<=right){
		if(list[i]<=list[j]){
			sorted[k++] = list[i++];
		}
		else{
			sorted[k++] = list[j++];
		}
	}
	
	if(i>mid){
		for(l=j; l<=right; l++){
			sorted[k++] = list[l];
		}
	}
	else{
		for(l=i; l<=mid;l++){
			sorted[k++] = list[l];
		}
	}
	
	for(l = left; l<=right; l++){
		list[l]= sorted[l];
	} // sorted는 정렬용으로 사용하는 배열이므로 list에 재복사
}

 

● 합병 정렬의 복잡도 분석

- 비교연산

순환 호출 구조

→레코드 개수가 n일 때 n=2^k라고 하면 순환 호출의 깊이는 k, 즉 k = log2n의 순환호출 깊이를 가진다.

 

배열 합병 시 정렬

→각 합병 단계마다 최대 n번의 비교 연산 필요

 

∴ n * log2n = O(nlog2n)

 

- 이동연산

임시 배열에 복사하는 연산 + 다시 list[]에 가져오는 연산

→2n

 

배열 합병 시 이동

→각 합병 단계마다 이동 연산 필요

 

∴ 2n * log2n = O(2nlog2n)

 

장점

입력 데이터의 분포와 상관없이 최악, 평균, 최선의 경우가 다 같이 O(nlog2n)의 시간복잡도를 가진다

 

단점

임시 배열이 필요하여 공간적 낭비와 만약 레코드 크기 n이 클 경우 이동연산에서 매우 큰 시간적 낭비를 초래한다.

 

+) 레코드를 배열이 아닌 연결 리스트로 연결하여 합병 정렬할 경우 링크 인덱스만 변경되므로

데이터 이동 시간을 획기적으로 절약할 수 있다.

 

♠ 450p Quiz

01

0	1	2	3	4	5	6	7
8	2	5	7	6	4	1	3
2	8	5	7	4	6	1	3
2	5	7	8	1	3	4	6
1	2	3	4	5	6	7	8

 

02

데이터의 크기가 1이 될 때까지 부분배열로 나눈 뒤에 데이터 레코드의 개수에 비례하는 log2n만큼 합병단계를 진행하기에  이미 정렬이 되어있는 경우여도 O(nlog2n)의 비교연산을 수행하기 때문

 

12.7 퀵 정렬

● 퀵 정렬의 개념

퀵 정렬도 합병 정렬과 마찬가지로 분할-정복법(divide and conquer)에 근거

 

합병 정렬과는 달리 리스트를 mid를 기준으로 분할하는 것이 아닌 pivot을 중심으로 비균등하게 분할

- 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로, 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 이동

void quick_sort(int list[],int left, int right){
	if(left<right){
		int q = partition(list,left,right);
		quick_sort(list,left,q-1);
		quick_sort(list,q+1,right);
	}
}

 

· low는 왼쪽 부분 리스트, high는 오른쪽 부분 리스트를 만드는 데 사용

· low는 왼쪽에서 오른쪽으로 증가하다가 pivot보다 큰 데이터를 찾으면 멈추고

high는 오른쪽에서 왼쪽으로 감소하다가 pivot보다 작은 데이터를 찾으면 멈춘다

· 탐색을 멈춘 각 인덱스는 부분 리스트에 적합하지 않은 데이터이므로 두 포인터 변수가 엇갈리지 않았다면

두 인덱스가 가리키는 요소들을 SWAP한다

· 두 포인터 변수가 엇갈리게 되면서 가장 큰 while문을 빠져나온다면 pivot과 high가 가리키는 요소를 SWAP한다

int partition(int list[],int left, int right){
	int pivot, temp;
	int low, high;
	
	low = left;
	high = right +1; // 아래 do-while문에서 한 칸씩 이동해야하기 때문
	pivot = list[left];
	
	do{
		do{
			low++;
		}while(list[low]<pivot);
		do{
			high--;
		}while(list[high]>pivot);
		if(low<high) SWAP(list[low],list[high],temp);
	}while(low<high);
	
	SWAP(list[left],list[high],temp);
	// pivot과 high인덱스에 위치한 요소를 교환
	return high;
}

 

● 퀵 정렬의 복잡도 분석

- 비교연산

순환 호출 구조

→레코드 개수가 n일 때 n=2^k라고 하면 순환 호출의 깊이는 k, 즉 k = log2n의 순환호출 깊이를 가진다.

 

각 분할 단계마다 평균 n번의 비교 연산 필요

 

∴ n * log2n = O(nlog2n)

 

이동연산은 비교 횟수보다 적으므로 무시

 

◆ 최악의 경우

리스트가 이미 정렬되어 있는 경우와 같이 리스트가 계속 불균형하게 나누어지는 경우

퀵 정렬의 패스의 개수는 n, 각 패스에서 평균 n번의 비교 연산이 필요하므로 거의 O(n^2)의 시간복잡도를 가진다.

 

 

● 퀵 정렬 라이브러리 함수의 사용

대개의 c언어 실행시간 라이브러리에 퀵 정렬 함수가 qsort란 이름으로 제공됨

 

qsort 함수

- 일반적인 구조체 배열 정렬 위함

void qosrt(
    void *base,
    size_t num,
    size_t width,
    int (*compare)(const void *, const void *)
);

 

- 각 요소가 width 바이트인 num개의 요소를 가지는 배열에 대하여 퀵정렬 수행

- compare는 배열 요소 2개를 서로 비교하는 사용자 제공함수,

compare( (void *) elem1, (void *) elem2 );

elem1이 elem2보다 작으면 음수, 같으면 0, 크면 양수 반환

int main(){
    int i;
    double list[5] = {2.1, 0.9, 1.6, 3.8, 1.2 };
    qsort((void*) list, (size_t)5, sizeof(double), compare);
    for(i =0; i<5; i++){
        printf("%f ",list[i]);
    return 0;
}

 

 

♠ 479p Quiz

01

0	1	2	3	4	5	6	7
4	3	1	8	6	2	5	7
4	3	1	2	6	8	5	7
2	3	1	4	6	8	5	7
2	1	3	4	6	7	5	8
1	2	3	4	6	5	7	8
1	2	3	4	5	6	7	8

 

02

n^2 / nlog2n = nlog2n

1,000,000(19.931569) 배 = 19931569배

 

12.8 히프 정렬

● 히프 정렬의 개념

정렬할 배열을 최소 히프로 변환한 다음, 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법

 

- 루트 노드가 가장 작은 원소이므로 최소 히프의 삭제 연산을 반복 수행하여

삭제된 노드는 별도의 배열에 순차적으로 저장하면 정렬된 배열을 얻을 수 있다

 

♠ 480p Quiz

01

1	2	3	4	5	6	7	8
1	2	4	6	3	7	5	8
2	3	4	6	8	7	5
3	5	4	6	8	7
4	5	7	6	8
5	6	7	8
6	8	7
7	8
8

 

 

12.9 기수 정렬

● 기수 정렬의 원리

- 레코드를 비교하지 않고 데이터를 정렬할 수 있는 정렬 기법

- O(kn) (k는 대부분 4 이하)의 시간 복잡도를 가지면서 O(nlog2n)의 이론적 하한선을 깰 수 있는 기법

- 추가적인 메모리를 요구한다는 점과 레코드의 키들이 동일한 길이를 가져야 한다는 한계를 가진다.

 

기수 = radix = 숫자의 자릿수

ex) 42는 두 개의 자릿수를 가지고 기수는 2이다.

 

0에서 99까지의 숫자를 정렬하려면 100개의 버킷을 사용할 수도 있지만

1의 자릿수와 10의 자릿수를 따로 사용하여 정렬하면 10개의 버킷을 두 번의 패스에 걸쳐 정렬할 수 있다.

 

32비트 정수의 경우 8비트씩 나누어 256 버킷을 4번의 패스에 걸쳐 정렬할 수 있다.

 

● 기수 정렬의 알고리즘 및 구현

- 각 버킷에 먼저 들어간 숫자들은 먼저 나온다 = queue를 사용한다

- 버킷에 숫자를 집어넣는 연산 = enqueue        버킷에서 숫자를 읽는 연산 = dequeue

void radix_sort(int list[], int n){
	int i, b, d, factor =1;
	QueueType queues[BUCKETS];
	
	for(b =0; b<BUCKETS; b++){
		init_queue(&queues[b]);
	}
	
	for(d=0; d< DIGITS; d++){
		for(i=0; i<n; i++){
			enqueue(&queues[(list[i] / factor) % 10], list[i]);
		}
		
		for(b=i=0; b<BUCKETS; b++){
			while(!is_empty(&queues[b])){
				list[i++] = dequeue(&queues[b]);
			}
		}
		factor *= 10;
	}
}

 

● 기수 정렬의 분석

입력 리스트의 정수 개수 n = 내부 루프 반복 수

d개의 자릿수 = 외부 루프 반복 수

∴ O(d*n)

 

- 다른 정렬 방법에 비하여 비교적 빠른 수행 시간 안에 정렬

- 다만 키값이 숫자로 표현되거나 같은 크기를 가져야

-> 실수, 한글, 한자 등으로 이루어진 키값은 필요한 버킷 수가 매우 많아지므로 적용 불가

 

♠ 486p Quiz

01

0	1	2	3	4	5	6	7
52	42	72	53	85	87	77	47
42	47	52	53	72	77	85	87

 

02

nlog2n : dn

이때 d는 주민등록번호 자릿수 13

log2(50,000,000) =≒ 25 이므로 기수정렬이 2배 정도 유리하다

 

12.10 정렬 알고리즘의 비교

알고리즘	최선	평균	최악
삽입 정렬	O(n)	O(n^2)	O(n^2)
선택 정렬	O(n^2)	O(n^2)	O(n^2)
버블 정렬	O(n^2)	O(n^2)	O(n^2)
쉘 정렬	O(n)	O(n^1.5)	O(n^1.5)
퀵 정렬	O(nlog2n)	O(nlog2n)	O(n^2)
히프 정렬	O(nlog2n)	O(nlog2n)	O(nlog2n)
합병 정렬	O(nlog2n)	O(nlog2n)	O(nlog2n)
기수 정렬	O(dn)	O(dn)	O(dn)