[알고리즘] 정렬알고리즘, 머지정렬(merge sort) java 구현

머지가 머지 ...???

 

머지정렬

합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현하는 정렬 방식이다.

(분할 정복 방법) 큰 문제를 작은 문제 단위로 쪼갠 뒤(분할), 다시 그들을 합치면서 정렬하는 방식이다.

 

실행 시 별도의 공간이 필요하다.

 

머지정렬은 이진트리 형태로 쪼개기 때문에 가질 수 있는 최대 깊이는 log n 이 된다. 

이때, 각 분할 (n개) 별로 합병을 진행하므로, 총 시간 복잡도는 O(nlogn)이 된다.

public void method6() {
		/*
		 * 머지정렬
		 *  - 합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현하는 정렬 방식이다.
		 *    (분할 정복 방법) 큰 문제를 작은 문제 단위로 쪼갠 뒤, 다시 그들을 합치면서 정렬
		 *  - MergeSort : 하나의 배열을 두개의 배열로 분할
		 *  - Merge : 두개의 정렬된 배열을 하나의 정렬로 합병 
		 *  - 실행 시 별도의 공간이 필요하다.
		 *  - 머지정렬은 트리형태로 쪼개기 때문에 가질 수 있는 최대 깊이는 log n 이 된다. 
		 *    이때, 각 분할 (n개) 별로 합병을 진행하므로, 총 시간 복잡도는 O(nlogn)이 된다.
		 *    
		 * ex) {7, 4, 6, 5, 2, 1, 8, 10}      //더 이상 쪼개질 수 없을 때까지 두 부분으로 나누어 쪼갠다.
		 *     {7, 4, 6, 5} {2, 1, 8, 10}
		 *     {7, 4} {6, 5} {2, 1} {8, 10}
		 *     {7} {4} {6} {5} {2} {1} {8} {10}
		 * 
		 *     {7} {4} {6} {5} {2} {1} {8} {10}  
		 *     {4, 7} {5, 6} {1, 2} {8, 10}      // 값을 2개씩 묶은 후 비교하여 작은값은 앞으로, 큰 값은 뒤로 정렬된 배열을 원본에 복사 -> 반복
		 *     {4, 5, 6, 7} {1, 2, 8, 10}        
		 *     {1, 2, 4, 5, 6, 7, 8, 10}    
		 */
		
		int[] arr = {7, 4, 6, 5, 2, 1, 8, 10};
		int[] tmp = new int[arr.length];
		
		System.out.println("정렬 전 배열 : " + Arrays.toString(arr));
		System.out.println();
		mergeSort(arr, tmp, 0, arr.length - 1);
		System.out.println("정렬 후 배열 : " + Arrays.toString(arr));
	}
	
	// 분할
	public static void mergeSort(int[] arr) {   // 머지소트 함수 정의, 정렬할 배열을 인자로 받는다.
		int[] tmp = new int[arr.length];         // 배열의 크기만큼 임시저장소 생성
		mergeSort(arr, tmp, 0, arr.length - 1);  // 정렬 할 베열, 임시저장소, 시작과 끝 인덱스를 넘겨서 재귀호출시작 
	}
	
	public static void mergeSort(int[] arr, int[] tmp, int start,int end) { // 재귀함수가 호출되면 정렬할 배열, 임시저장공간, 시작과 끝 인덱스를 인자로 받는다.
		if (start < end) {  //시작 인덱스가 끝 인덱스보다 작은 동안만 호출
			int mid = (start + end) / 2;  // 함수가 호출되면 배열을 가운데로 잘라야 하므로 가운데 인덱스가 필요
			mergeSort(arr, tmp, start, mid);  // 배열의 앞부분 호출
			mergeSort(arr, tmp, mid + 1, end);  // 배열의 뒷부분  호출    => 왼쪽과 오른쪽배열 방 정렬
			merge(arr, tmp, start, mid, end);  // 두개로 나뉜 배열을 merge로 병합
		}
	}
	
	// 합병
	public static void merge(int[] arr, int[] tmp, int start, int mid, int end) {  // 배열의 포인터, 임시저장장소, 시작인덱스, 파티션으로 나눴던 중간인텍스, 끝 인덱스를 인자로 받는다.
		int part1 = start;  // 첫번째 배열방에 첫번째 방과
		int part2 = mid + 1;  // 두번째 배열의 첫번째 방의 인덱스를 각각 part1,2로 저장
		int index = start;  //

		for(int i = start; i <= end; i++) {  
			tmp[i] = arr[i];  // 임시저장소에 정렬이 된 배열을 필요한만큼 복사  => 배열이 중간지점을 기준으로 하나로 붙어있음
		}
		
		while(part1 <= mid && part2 <= end) {  // 첫번째 배열이 끝까지가거나 두번째 배열이 끝까지 갈 때까지 반복
			if (tmp[part1] <= tmp[part2]) {  // 두개의 배열방에 첫번째 값부터 비교를 하여 앞에께 작으면 
				arr[index] = tmp[part1];  // 앞의껄 옮기고
				part1++;  // 앞쪽 포인터를 하나 뒤로 옮기고 
			} else {  // 앞의 값이 작은게 아니면
				arr[index] = tmp[part2];  // 뒤쪽 배열에서 하나 가져왕서 복사하고
				part2++;  // 뒤쪽 포인터를 하나 옮긴다.
			}
			index++;  // 배열 후 인덱스를 하나 늘려준다.
		// 	만약 뒤쪽 배열은 비었고, 앞쪽 배열에 데이터가 남아있는 경우
		}
		
		for (int i =0; i <= mid - part1; i++) {  // 앞쪽 포인터가 배열에 끝에서 남은 만큼을 돌면서 최종적으로 저장할 배열의 남은 값을 붙여준다
			arr[index + i] = tmp[part1 + i];  // 뒤쪽 배열은 최종배열의 뒤쪽에 이미 자리하고 있기 떄문에, 뒤쪽에 남은 데이터는 그 자리에 두고, 앞쪽데이터만 필요한 위치에 복사
		}
	}