[C] 합병 정렬(Merge Sort)

합병 정렬(Merge Sort)

---

합병 정렬? 

합병 정렬은 병합 정렬이라고도 불리며, 배열을 여러개로 분할해서 병합하면서 정렬하는 방법입니다.

특징

1) 메모리 내부에서 정렬하는 방법

2) 연결 리스트와 같은 순차적인 접근이 가능한 자료구조에 유일한 정렬 방법

어떠한 방법?

예제는 정렬할 배열과 임시로 담아놓을 배열 2개를 이용해서 정렬을 진행했습니다.

아래와 같은 배열이 있을 때

배열을 나눠서 정렬을 한 뒤 병합하면서 정렬을 진행합니다.

---

배열을 이용한 합병 정렬 예제

배열 출력 함수

void print_array(int array[], int size){

for(int i=0; i<size; i++){

printf("%-4d",array[i]);

}

printf("\n");

}

병합 정렬 함수

- size : 2씩 곱해지면서 정렬할 항의 수를 결정

- first, second : 하나의 배열을 두개처럼 사용하기위한 변수 각각 비교할 항 앞과 뒤를 가리킴

- i, j : 각각 비교할 앞의 항과 뒤의 항

- k : 임시로 담을 배열의 인덱스

void merge_sort(int a[], int n){

int i, j, k;

int first, second, size;

int *b;

b = (int*)malloc(sizeof(int)*n);

for(size = 1; size<n; size *=2){

first = -2 * size; // 초기 값

second = first + size;

while(second + size*2 < n){

first = second + size;

second = first + size;

i = k = first;

j = second;

while(i<first+size || (j<second+size && j<n)){

if(a[i]<=a[j]){

if(i<first + size)

b[k++] = a[i++];

else

b[k++] = a[j++];

}else{

if(j<second+size && j<n)

b[k++] = a[j++];

else

b[k++] = a[i++];

}

printf(" b[%d]=%d\t",k-1,b[k-1]);

}

printf("\n############################\n");

}

for(i=0; i<n; i++)

a[i] = b[i];

}

free(b);

}

메인 함수

void main(){

int array[] = {6,8,5,2,7,3,1,4};

int size = sizeof(array)/sizeof(int);

printf("########### Sorting before ###########\n");

print_array(array, size);

printf("######################################\n");

merge_sort(array, size);

printf("########### Sorting after ###########\n");

print_array(array, size);

}

실행 결과

---

참고 : C로 배우는 알고리즘 (이재규)

위키백과(합병 정렬)

---

관련 포스팅

[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)