[자료구조] Sorting(정렬) - Merge, Heap Sort

 

Merge Sort

 

Merge Sort는 하나의 리스트를 부분 리스트로 점차 분할하여 각 부분 리스트를 정렬한 다음 다시 부분 리스트를 합병해 정렬하는 방법이다.

 

반복적으로 구현하는 방법이 있지만 결론적으로 재귀적인 방법이 효율적이기에 재귀적인 Merge Sort를 소개할 것이다.

 

 

// 정렬할 리스트를 분할해 2개의 부분 리스트 생성

int rmergeSort(element a[], int link[], int left, int right) {
	if (left >= right) return left;
    	int mid = (left + right) / 2;
        return listMerge(a, link, rmergeSort(a, link, left, mid), rmergeSort(a, link, mid+1, right));
    }

// link[i] = 0일 때 배열 a[]의 두 체인 start1, start2를 합병해 
// 키 값이 비 감소순으로 연결된 결과 체인의 첫 번째 위치 반환

int listMerge(element a[], int link[], int start1, int start2) {
	int last1, last2, lastResult = 0;
    	for (last1 = start1, last2 = start2; last1 && last2; ) {
        	if (a[last1) <= a[last2]) {
            	link[lastResult] = last;
                lastResult = last1; last1 = link[last1];
            }
            else {
            	link[lastResult] = last2;
                lastResult = last2; last2 = link[last2];
            }
        }
        
        if (last1 == 0) link[lastResult] = last2;
        else link[lastResult] = last1;
        
        return link[0];
 }

 

 

 

Heap Sort

 

Heap Sort는 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법이다.

내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

 

내림차순 정렬 과정은 아래와 같다.

• 정렬해야 할 n개의 요소들로 최대 힙을 만든다. 
• 한 번에 하나씩 요소를 힙에서 꺼내 배열의 뒤부터 저장한다.
• 삭제되는 요소들은 값이 감소되는 순서로 정렬된다.

 

Heap에 데이터를 삭제하고 삽입하는 과정을 코드로 확인해보겠다.

데이터 삭제와 삽입하는 과정에 대한 설명은 [자료구조] Tree(트리) - 우선순위 큐와 힙을 참고하면 된다.

 

void adjust(element list[], int root, int n) {
	int child, rootkey;
    	element temp;
        temp = lst[root];
        rootkey = list[root].key;
        child = 2 * root;
        while (child <= n) {
        	if ((child < n) && (list[child].key < list[child+1].key))
            		child++;
            	if (rootkey > list[child].key) break;
            	else {
            		list[child/2] = list[child];
                	child *= 2;
            	}
        }
     	list[child/2] = temp;
}

// i번째로 높은 키를 n-i+1번째 위치에 삽입
// Max Heap을 순서대로 배열에 정렬하는 과정

void heapsort(element list[], int n) {
	int i, j;
    	element temp;
    
    	for (i = n/2; i>0; i--)
    		adjust(list, i, n);
    	for (i = n-1; i > 0; i--) {
    		SWAP(list[1], list[i+1], temp);
        	adjust(list, 1, i);
    	}
}

 

 

이로써 정렬 알고리즘인 Insertion Sort, Quick Sort, Merge Sort, Heap Sort 를 모두 알아봤다.

 

정렬 알고리즘 전체의 시간 복잡도를 비교해보겠다.

• 단순하지만 비효율적인 정렬
  
  • 삽입 정렬, 선택 정렬, 버블 정렬
• 복잡하지만 효율적인 정렬
  • 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

 

Stable vs Unstable

• Stable Sort
  • 삽입 정렬, 버블 정렬, 기수 정렬, 합병 정렬
• Unstable Sort
  • 힙 정렬, 선택 정렬, 퀵 정렬, 쉘 정렬