7. 정렬 (2) - 합병 정렬, 힙 정렬, 쉘 정렬

 

합병 정렬

폰 노이만에 의해 만들어진 정렬 방법이다.
분할 정복(Divide and Conquer)를 이용한 정렬 방법으로, 문제를 작은 문제로 나누고 각각을 해결한 다음, 그 결과로 큰 문제를 해결하는 방법이다.
합병 정렬(Merge Sort)은 3가지 과정으로 구성된다.
분할(Divide) = 배열을 같은 크기의 배열 두개로 분할한다
정복(Conquer) = 이 두 개의 배열을 정렬한다. (크기가 아직 크면 순환 호출로 다시 분할)
결합(Combine) = 배열들을 다시 합치면서 원래의 정렬된 배열로 만든다.

코드

//머지소트 c++ 코드
void MergeSort(int sort[], int data[], int first, int last)
{
	int mid;

	//1개 남았을때는 멈추게
	if (first < last) {
		mid = (first + last) / 2; 
		//왼쪽
		MergeSort(sort,data, first, mid);
		//오른쪽
		MergeSort(sort,data, mid + 1, last);
		//합병
		merge(sort,data, first, mid, last);
	}

}
//합병 알고리즘
void merge(int sort[], int data[], int first, int mid, int last)ㅊ
{
	int left = first;
	int right = mid + 1;
	int index = first;
	int i;

	//비교 후 합치기
	while (left <= mid && right <= last) {
		if (data[left] <= data[right]) {
			sort[index++] = data[left++];
		}
		else {
			sort[index++] = data[right++];
		}
	}
	//left가 먼저 끝남 -> right 남은거 옮겨주기
	if (left > mid) {
		for (i = right; i <= last; i++) {
			sort[index++] = data[i];
		}
	} //right가 먼저 끝남 -> left 남은거 옮겨주기
	else {
		for (i = left; i <= mid; i++) {
			sort[index++] = data[i];
		}
	}
	//데이터 업데이트
	for (i = first; i <= last; i++) {
		data[i] = sort[i];
	}
}

시간복잡도

합병 시, 한쪽으로 쏠렸을 때({1,2,3,4,5}와{6,7,8,9,10})는 $\frac{N}{2}$ 번의 비교만 하면 되지만, 완전히 촘촘히 겹칠때({1,3,5,7,9}와{2,4,6,8,10})는 $N-1$번의 비교가 필요하다.
보통 식을 세우면 $W(n) = W(\frac{n}2)(분할) + W(\frac{n}2)(분할) + n-1(병합) $ 로 표현할 수 있는데 이는 퀵소트에서 보았다시피 $O(NlgN)$의 시간복잡도로 표현됨을 알 수 있다.
합병정렬은 입력이 어떻게 되건 결국 반씩 나누기 때문에 Best, Worst, Average 모두 $O(NlgN)$임을 알 수 있다.
다만 한가지 단점은, 만약 정렬해야 하는 것이 배열이라면, 추가적인 배열이 필요하므로 메모리 낭비가 심하다. 또한 노드의 수가 많으면 이동이 많기 때문에 비교적 퀵, 힙 정렬에 비해 시간이 오래 걸린다.

힙정렬

힙 정렬은 이진 트리의 일부인 힙을 사용한 정렬방법이다!
힙에 관한 정보는 이전 글에 간단하게 정리해두었다 -> https://howtolivelikehuman.tistory.com/26?category=952546
이 힙에서 최대 힙 트리, 또는 최소 힙 트리를 구성하여 결국 정렬을 하는 과정으로
FixHeap을 통해 힙 구조를 유지하고 -> 루트 하나씩 저장해나가면서 (힙 삭제) 나머지를 계속 힙 구조를 유지하는 방식으로 정렬을 한다.

코드

//힙 구조를 유지하는 방식
void FixHeap(int heap[], int n, int i)
{
	int parent = i;
	int left_child = i * 2 + 1;
	int right_child = i * 2 + 2;
	int temp;

	if (left_child < n && heap[parent] < heap[left_child]) {
		parent = left_child;
	}
	if (right_child < n && heap[parent] < heap[right_child]) {
		parent = right_child;
	}
	if (i != parent) {
		temp = heap[parent];
		heap[parent] = heap[i];
		heap[i] = temp;
		FixHeap(heap, n, parent);
	}

}

void HeapSort(int heap[])
{
	int temp;
	//depth h-1의 노드들부터 자식 확인
	for (int i = SIZE / 2 - 1; i >= 0; i--) {
		FixHeap(heap, SIZE, i);
	}

	for (int i = SIZE - 1; i > 0; i--) {
		temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		FixHeap(heap, i, 0); //힙 구조 유지
	}
}

시간복잡도

 

힙 정렬 역시 합병 정렬과 마찬가지로 이미 정렬되어 있는 경우 Best Case이지만, 어차피 FixHeap과 Sort 과정은 해야 하므로 Worst, Average Case 역시 시간복잡도에 큰 차이가 없다.
힙 정렬을 두 가지 과정 $T_1$ 과 $T_2$로 나눴을 때 시간복잡도는 아래와 같이 각각 $O(N)$과 $O(NlgN)$으로 나오고, 따라서 결국 $O(NlgN)$의 시간복잡도를 갖는다.

쉘 정렬

쉘 정렬은 D.L.Shell이 만든 정렬방법으로 삽입 정렬이 정렬되어 있는 배열에 대해서는 대단히 빠르나, 요소들이 삽입될 때 다른 요소들이 한 칸 씩 모두 이동하는 점을 개선한 방법이다.
Merging pairs 방식의 부분 부분 정렬하는 방식을 사용하는데 gap 값으로 간격을 주어 마치 부분리스트가 만들어진 것처럼 구현 하여 이 리스트들을 정렬 하는 것이다.
쉘은 대용량 고속 RAM의 등장으로 한번에 많은 양을 저장할 수 있고, 고속으로 임의의 값을 접근할 수 있으므로 합병 정렬에 비해 느리지만 같은 메모리에서 두 배 많은 양의 숫자를 정렬할 수 있다고 언급하였다.

코드

// 셸 정렬
void Shellsort(int data[]){
  int i, gap;
  
  for(gap=SIZE/2; gap>0; gap=gap/2){
    if((gap%2) == 0)(	//gap은 홀수가 좋다고 한다.
      gap++; 
    )
    
    // 부분 리스트수 = gap만큼
    for(i=0; i<gap; i++){
      Insertionsort(data, gap, i, SIZE-1); //각각 삽입정렬
    }
  }
}

void Insertionsort(int data[], int gap, int first, int last){
  int i, j, key;

  for(i=first+gap; i<=last; i=i+gap){
    key = data[i]; //삽입 될 수를 복사해뒀다가
    
    for(j=i-gap; j>=first; j=j-gap){
    	if(data[j] > key){
    		data[j+gap] = data[j]; // 레코드를 gap만큼 이동하면서 삽입.
    	}
    }
    data[j+gap] = key;
  }
}

시간복잡도

Best Case에선 역시 삽입정렬과 마찬가지로 이미 정렬되어 있는 상태이다. 총 N-1번의 비교만 진행하므로 $O(N)$이다.
Worst Case에서도 역시 삽입정렬과 마찬가지로, 완전 역순으로 정렬되어 있는 상태일때 $O(N^2)$이라 할 수 있다.
Average Case에는 쉘의 논문에서의 실험 결과로 한 단어인 항복들에 대해서 평균 $O(N^{1.226})$의 복잡도라고 발표하였다. 보편적으로 $O(N^{1.5})$ 라 알려져 있다.

A High Speed Sorting Procedure (D.L.Shell)에서의 일부