[알고리즘] 합병정렬(Merge Sort)

합병정렬(Merge Sort)

- 분할 정복(Divide and Conquer) 알고리즘

- 주어진 배열을 두 개의 배열로 계속 분할한 뒤, 합치면서 정렬

- 합병 과정에서 O(n), 분할 과정에서 O(logn)으로 O(nlogn)의 시간복잡도를 가짐

- 합병을 위한 배열을 추가로 필요로 함

 

선택정렬(Selection Sort) 과정

1) 분할

n개의 데이터가 주어졌을 때,

더 이상 분할할 수 없도록 배열을 두 개로 분할한다.

 

 

2) 합병

 

분할과정에서 나누어진 배열을 정렬을 유지한 상태로 합쳐나간다.

 

 

3) 합병 과정 자세히보기

위의 두 배열을 합치는 과정을 통해 합병 단계를 자세히 살펴보면

두 배열을 합칠 새로운 공간을 하나 만든다.

두 배열을 첫번째 위치를 표시하는 인덱스 i(left), j(mid + 1)와 합쳐진 공간의 현재 인덱스를 표시하는 k(left)가 있다.

i의 값과 j의 값 중 작은 값이 k에 위치하고 해당 k값과 i, j 중 선택된 인덱스 값이 1 증가한다.

마찬가지로 i의 값과 j의 값 중 작은 값이 k에 위치하고 해당 k값과 i, j 중 선택된 인덱스 값이 1 증가한다.

i와 j의 값을 비교해야하는데, j의 존재하는 값이 없다.

그렇다면 나머지 값들은 i가 가르치는 값들로 채워진다.

i, j의 값을 비교해가며 작은 값부터 선택해 합쳐나간다. 

 

 

소스코드

package algorithm;

import java.util.*;

public class mergeSort {
	static int[] arr = {6, 5, 3, 1, 8, 7, 2, 4};
	static int[] sorted = new int[arr.length];
	
	public static void merge(int left, int right) {
		int mid = (left + right) / 2;
		int i = left;
		int j = mid + 1;
		int k = left;
		
		while(i <= mid && j <= right) {
			if(arr[i] < arr[j]) sorted[k++] = arr[i++];
			else sorted[k++] = arr[j++];
		}
		
		int margin = (i <= mid) ? i : j;
		
		while(k <= right) sorted[k++] = arr[margin++];
		
		for(int l = left; l <= right; l++) arr[l] = sorted[l];
	}
	
	public static void div(int left, int right) {
		int mid;
		
		if(left < right) {
			mid = (left + right) / 2;
			div(left, mid);
			div(mid + 1, right);
			merge(left, right);
		}
	}
	
	public static void main(String[] args) {
		div(0, arr.length - 1);
		
		for(int o : arr) System.out.print(o + " ");
	}
}