[Algorithm] MergeSort Algorithm

MergeSort

시간 복잡도 : ( N * Log N )

 

간단 설명 : 일단 정렬을 할 배열을 하나하나 다 쪼갠다 밑에 그림 참고!!

 

 

이렇게 잘린 배열로 뭘 하면 될까?

우리는 저렇게 잘린 배열을 하나하나 붙여 가며 정렬할 것이다 말로 하면 어려우니 밑에 그림을 보도록 하자!

 

#include <stdio.h>

int sorted[10];

void merge(int a[], int s, int middle, int e){
	int i = s;
	int j = middle + 1;
	int k = s;
	
	while(i <= middle && j <= e){
		if(a[i] <= a[j]){
			sorted[k] = a[i];
			i++;
		} else{
			sorted[k] = a[j];
			j++;
		}
		k++;
	}
	if(i > middle){
		for(int t = j; t <= e; t++){
			sorted[k] = a[t];
			k++;
		}
	} else{
		for(int t = i; t <= middle; t++){
			sorted[k] = a[t];
			k++;
		}
	}
	for(int t = s; t <= e; t++){
		a[t] = sorted[t]; 
	}
}

//모두 반으로 나누기 
void mergeSort(int a[], int s, int e){
	if(s < e){
		int middle = (s + e)/2;
		mergeSort(a, s, middle);
		mergeSort(a, middle + 1, e);
		merge(a, s, middle, e);
	}
}

int main(void){
	int arr[10] = {1,5,2,7,9,3,4,10,8,6};
	mergeSort(arr, 0, 9);
	for(int i = 0; i < 10; i++){
		printf("%d ", sorted[i]);
	}
	return 0;
}

위의 코드가 전체 코드이다. 이렇게 보면 어려워 보일 수 있으니 밑에서 설명할 때는 부분 부분 파트를 나눠서

설명하도록 하겠다.

 

Part 01.  mergeSort 함수

//s = start 시작하는 인덱스
//e = end 끝나는 인덱스

//반으로 계속 쪼개주는 함수
void mergeSort(int a[], int s, int e){
	if(s < e){
		int middle = (s + e)/2;
		mergeSort(a, s, middle);
		mergeSort(a, middle + 1, e);
		merge(a, s, middle, e);      //<---- 이 부분은 일단 넘어가도록 하자 이따 설명 하겠다
	}
}

이 함수는 첫 번째 그림처럼 하나하나 다 쪼개 주는 재귀 함수이다.

말만 쪼개주는 거지 진짜 따로 배열을 만들어 쪼개는 것은 아니다 ㅎㅎ

 

( 나는 처음에 이게 너무 헷갈렸다 "왜 쪼갠다면서 안 쪼개는 겨???" ) 

 

 

start, end 분포도

if(s < e){
	code....
}

start와 end가 같으면 실행 안 해!!

즉 배열의 크기가 1이상이여야 한다

 

(start, end 분포도 그림에서 맨 마지막에 start와 end가 같은 곳을 가리키는 곳이 있었는데 거기서 끝낼 수 있도록 하기 위해서)

 

Middle 분포도

	int middle = (s + e)/2;
	mergeSort(a, s, middle);
	mergeSort(a, middle + 1, e);
	merge(a, s, middle, e);      //<---- 이 부분은 일단 넘어가도록 하자 이따 설명 하겠다

일단 우리는 middle이라는 것을 알아야 한다 그래야 반을 쪼개고 쪼개고 계속 쪼갤 수 있기 때문이다.

 

그리고 얻어낸 Middle을 기준으로 왼쪽 오른쪽으로 계속 쪼개서 Start와 End가 같은 곳을 가리키는 곳까지 즉 한 개가 될 때까지 나누는 함수이다!!

 

위에 보이는 merge 함수는 바로 다음 파트에서 설명하겠다

 

Part 02. merge 함수

void merge(int a[], int s, int middle, int e){
	int i = s;
	int j = middle + 1;
	int k = s;
	
	while(i <= middle && j <= e){
		if(a[i] <= a[j]){
			sorted[k] = a[i];
			i++;
		} else{
			sorted[k] = a[j];
			j++;
		}
		k++;
	}
	if(i > middle){
		for(int t = j; t <= e; t++){
			sorted[k] = a[t];
			k++;
		}
	} else{
		for(int t = i; t <= middle; t++){
			sorted[k] = a[t];
			k++;
		}
	}
	for(int t = s; t <= e; t++){
		a[t] = sorted[t]; 
	}
}

이 함수는 마지막 재귀 함수가 끝나고 처음 호출된 부분으로 돌아오는 과정에서 나눠진 하나하나가 정렬되어 결합되게 하는 함수이다

 

재귀 함수의 이해가 부족하다면 이 영상을 보면 도움이 될 것 같다

 

나눠서 설명해보겠다

 

int i = s;
int j = middle + 1;
int k = s;

 

현재 

i = 4 가 들어 있는 인덱스 

j = 9 가 들어 있는 인덱스

라고 생각하면 쉬울 듯

 

그럼 옆에서 또 이런 일이 반복되고 있을 거다 예를 들면 

이것도 다른 함수에서 위랑 똑같이 되고 있을 것이다

 

그럼 k는 뭔가?

 

k는 우리가 저장할 가상의 배열(전역 변수 sorted)의 인덱스이다

어차피 i가 첫 번째 start index를 가리키고 있기 때문에 i와 같이 s를 대입해 준 것이다.

 

그럼 i가 4의 인덱스를 가지면 가상의 배열 (전역 변수 sorted)의 4번째 인덱스부터 s ~ e를 정렬하는 것이다.

 

	while(i <= middle && j <= e){
		if(a[i] <= a[j]){
			sorted[k] = a[i];
			i++;
		} else{
			sorted[k] = a[j];
			j++;
		}
		k++;
	}

위 코드는 i가 middle보다 자거나 같고 j가 현재 배열의 끝(e) 보다 작다면 실행

 

( a [i] <= a [j] )이라면 가상의 배열의 k인덱스 ( sorted [k] )에 a [i]를 저장하는 것

 

쉽게 말해 작은 것을 먼저 가상의 배열에 저장하는 것이다

 

말로 하면 어려우니 그림으로 보여주겠다 

 

1.

2.

3.

위 그림처럼 되면  i는 비교 대상이 사라지고 혼자 남는다 

그러면 밑의 코드를 보도록 하자

if(i > middle){
		for(int t = j; t <= e; t++){
			sorted[k] = a[t];
			k++;
		}
	} else{
		for(int t = i; t <= middle; t++){
			sorted[k] = a[t];
			k++;
		}
	}

위 코드는 위의 그림에서  왼쪽 배열이 혼자 남아 있기 때문에 가상의 배열에 모두 담아주는 기능을 하는 코드이다.

 

그럼 결국 이렇게 가상 배열에 정렬이 되고

또 남은 왼쪽 배열과 지금 해온 일들을 반복해주는 것이다

 

그러면 배열이 정렬된다!!!!!!!!!!!!!!!!!!!!!!!!

 

 

 

 

글을 끝내며

이번 글은 나중에 다시 보고 있을 나를 위해 열심히 적었다

 

글을 쓰며 MergeSort에 대해 더 명확하게 알았으며 완벽하게 이해한 거 같다 

그럼 이걸 어디에 쓸 수 있는가.... 이제는 이걸 고민해 보려고 한다