Inor

[Algorithm] 합병 정렬 (Merge Sort) 본문

Algorithm

[Algorithm] 합병 정렬 (Merge Sort)

Inor 2018. 2. 2. 13:05

- 합병 정렬


 분할 정복 기법을 사용한 정렬 알고리즘 입니다. 분할 정복 기법은 분할하면서 정복하는 방법과 분할이 끝날때 까지 분할 하고 합치면서 정복하는 방법이 있습니다. 합병 정렬은 분할이 안될때까지 분할 한 후에 합병하며 정렬하는 방식입니다. 분할하는 방법과 병합하는 방법을 그림으로 설명하겠습니다.


1. 분할


 4

7

6

2

5

3


먼저 전체 배열을 반으로 나눕니다.


 4

7

6

2

5

3


이후에 반으로 분할이 안될때까지 분할을 반복합니다.


2. 정복


 정복하면서 분할된 공간끼리 정렬을 합니다.


 4

7

6

2

5

3


 먼저 파란색 영역의 4와 7 값을 비교해서 4를 7의 앞에 위치하도록 해줍니다. 6과 2의 경우에는 2가 6보다 작으니 2를 6의 앞에 위치 시켜줍니다. 이러한 방법으로 (5,3)과 (1,8)을 각각 정렬합니다. 정렬한 후에는 아래와 같은 순서가됩니다.


4

s, l

7

2

r

6

e

3

5

1

8


 위의 배열은 4개의 값을 갖고있는 2개의 영역으로 나뉘어져 있습니다. 초록색 영역 먼저 정복하며 정렬하겠습니다. 이 과정에서 중요한 것이 있는데 시작과 끝을 정해줘야 합니다. 시작은 4 끝은 6, s(start)와 e(end)로 표현하겠습니다. 그리고 왼쪽 영역과 오른쪽 영역을 나누어서 왼쪽 영역의 값과 오른쪽 영역의 값을 비교하겠습니다.

 4는 왼쪽 영역의 시작점(l) 입니다. 2는 오른쪽 영역의 시작점(r) 입니다. l과 r을 비교해서 2를 먼저 맨 앞에 위치 시키고 r을 오른쪽으로 한칸 옮겨줍니다. 다시 l과 r을 비교하고 4가 6보다 크니 4를 2의 뒤에 위치 시켜줍니다. 그리고 l을 오른쪽으로 한칸 이동 시킵니다. 위와 같은 방법으로 l과 r을 비교해서 위치를 잡아줍니다. 이해가 잘 안되시면 아래의 정렬된 모습을 보시면 됩니다. 왼쪽 영역의 정렬이 완료되면 오른쪽 영역을 정렬합니다.


2

s, l

4

6

7

1

r

3

5

8

e


 이제 전체 영역을 정렬하면 됩니다. 마찬가지로 왼쪽과 오른쪽 영역으로 나누고 l과 r을 이동 시키며 정렬된 위치를 지정해주면 됩니다.

 정렬을 하다보면 왼쪽과 오른쪽 중에 한 곳에만 정렬 안된 값이 남아있어서 비교할 값이 없는 경우가 생깁니다. 이럴 경우에는 그냥 남아있는 수들을 차례대로 위치시켜주면 됩니다. 만약 왼쪽에 3개의 값이 남아있다면 3개의 값을 차례로 위치시켜주면 됩니다. 그 이유는 이 값들이 해당 영역에서 가장 큰 값들이기 때문입니다. 이미 정렬된 상태이고 가장 큰 값들이 차례로 남아있는 경우이기 때문에 차례로 정렬된 값들의 뒤에 넣어주면 됩니다.




- 코드


class Sorting{
	static int[] sorted;

	public void mergeSort(int[] arr, int start, int end) {
		int middle = (start + end) / 2;
		if (start < end) {
			mergeSort(arr, start, middle);
			mergeSort(arr, middle + 1, end);
			merge(arr, start, middle, end);
		}
	}

	public void merge(int[] arr, int start, int middle, int end) {
		int leftIndex, rightIndex, copyIndex;

		leftIndex = start;
		rightIndex = middle + 1;
		copyIndex = start;

		while (leftIndex <= middle && rightIndex <= end) {
			if (arr[leftIndex] > arr[rightIndex]) {
				sorted[copyIndex++] = arr[rightIndex++];
			} else {
				sorted[copyIndex++] = arr[leftIndex++];
			}
		}

		while (rightIndex <= end) {
			sorted[copyIndex++] = arr[rightIndex++];
		}
		while (leftIndex <= middle) {
			sorted[copyIndex++] = arr[leftIndex++];
		}

		for (int i = start; i <= end; i++) {
			arr[i] = sorted[i];
		}

		System.out.println("\n 합병 정렬 >> ");
		System.out.println(Arrays.toString(arr));
	}

	public static void main(String[] args) {
		Sorting m = new Sorting();
		int[] a = { 69, 10, 30, 2, 16, 8, 31, 22 };
		sorted = new int[a.length];

		m.mergeSort(a, 0, a.length - 1);
	}
}

'Algorithm' 카테고리의 다른 글

[Algorithm] 스택을 이용한 큐 구현  (0) 2018.01.25
[Algorithm] Quick Sort (퀵 정렬)  (0) 2017.11.26
[Algorithm] Big O 표기법  (0) 2017.11.12
Comments