정렬(1). 병합정렬(merge sort)

병합 정렬이란?

 재귀를 이용한 정렬방법으로 원래의 배열을 분할한 뒤 정렬하며 병합하는 방식으로 정렬을 수행하는 방법을 말한다. 분할 정복의 개념을 도입한 방법이며, 부분 배열 array [a.... b]를 다음과 같이 정렬한다.

1. 만일 a=b이면 아무것도 하지 않는다. 부분 배열이 원소 한 개로 이루어져 있으며, 이는 이미 정렬되어 있기 때문이다.
2. 가운데 원소의 위치를 k = (a+b)/2 
※이때, a+b가 2로 나누어 떨어지지 않는다면 (a+b)/2보다 크지 않은 정수중 가장 큰 수가 k가 된다.
3. 재귀적으로 부분 배열 array [a.... k]를 정렬한다.
4. 재귀적으로 부분 배열 arrat [k+1..... b]를 정렬한다.
5. 정렬된 부분 배열 array [a... k]와 array [k+1.... b]를 병합하여 정렬된 부분 배열 array [a.... b]로 만든다.

만약 array= {1, 3, 6, 2, 8, 2, 5, 9}라 하였을 때, 이를 4개 2개...로 나눈다. 그리고 알고리즘을 재귀적으로 호출하여 두 부분 배열을 정렬한다. 마지막으로, 정렬된 부분 배열을 병합하여 여덟 개의 원소로 이루어진 정렬된 배열로 만든다.

그 후, 정렬된 부분 배열을 선형 시간에 병합할 수 있는데, 이는 부분 배열은 이미 정렬되어 있기 때문이다.
따라서, 재귀 호출의 단계 O(logn)이고, 각 단계를 처리하는 데 총 O(n) 시간이 걸리기 때문에 이 알고리즘의 전체 시간 복잡도는 O(nlogn)이다.

다음은 JAVA로 작성한 merge sort이다.

public class mergeSort {

	public static void main(String[] args) {
		int arr[] = {1,3,6,2,8,2,5,9};
		System.out.print("정렬전: ");
		for(int i = 0; i< arr.length; i++) {
			System.out.print(" " + arr[i]);
		}
		System.out.println();
		
		mergeSort(arr,0,arr.length-1);
		
		System.out.print("정렬후: ");
		for(int i = 0; i< arr.length; i++) {
			System.out.print(" " +arr[i]);
		}
	}

	//분할
	static void mergeSort(int[] array, int first,int end) {
		//하나의 element가 남을때 까지 수행
		if(first<end) {
			//홀수를 2로 나눌때 에러방지 
			int mid = first+(end-first)/2;
			mergeSort(array, first, mid);
			mergeSort(array, mid+1, end);

			merge(array,first,mid,end);
		}
	}

	//정렬
	static void merge(int[] array,int first, int mid,int end) {
		
		//임시 저장 배열
		int temp[] = new int[100];

		//왼쪽 그룹의 시작
		int i = first;
		//오른쪽 그룹의 시작
		int j = mid+1;

		//임시배열의 인덱스
		int k=0;

		//한쪽 그룹에 더이상 비교할 element가 없을때까지 비교
		while(i<=mid && j<=end) {
			//왼쪽 그룹과 오른쪽 그룹을 비교하여 더 작은 것을 임시 배열에 저장
			if(array[i]<array[j]) {
				temp[k]=array[i];
				i++;
				k++;
			}else {
				temp[k]=array[j];
				j++;
				k++;
			}
		}
		//왼쪽에 element가 남아있을때
		while(i<= mid) {
			temp[k] = array[i];
			k++;
			i++;
		}

		//오른쪽에 element가 남아있을때
		while(j<=end) {
			temp[k] = array[j];
			k++;
			j++;

		}

		//올바른 인덱스 유지
		k--;
		

		//병합
		while(k>=0) {
			array[first+k] = temp[k];
			k--;
		}
		
	}

}

 

1. mergeSort함수를 원래의 배열과 시작, 끝의 인덱스를 매개변수로 하여 호출한다.
2. 전달받은 배열의 시작 위치와 끝 위치를 더하여 반으로 나누어 중간지점을 잡는다.
3. 시작~중간, 중간+1~끝으로 배열을 두 부분 배열로 나누어 mergeSort를 재귀적으로 호출한다.
4. 계속하여 분할하다 element가 하나가 남는다면 아무것도 수행하지 않고 돌아와 merge를 호출한다.
5. merge함수에서는 임시 배열을 생성하고 왼쪽 부분 배열과 오른쪽 부분 배열을 계속하여 비교하여 작은 것은 임시 배열에 저장한 후, 임시 배열의 인덱스를 하나씩 증가시키고 부분 배열의 인덱스 또한 증가시킨다.
6. 하나의 부분 배열에 더 이상 비교할 element가 없을 때까지 반복한다.
7. 그 후, 비교할 element가 아직 남아있는 부분 배열을 찾아 임시 배열에 저장하지 않은 element들을 저장한다.
(각 부분 배열들은 이미 정렬되어 있으니 순차적으로 임시배열에 저장하면 된다)
8. 정렬된 임시 배열이 완성이 되었으면, 원래의 배열에 임시 배열을 덮어 씌운다.