[Java] 병합 정렬(Merge Sort)

1. 좀 더 쉬운 버전 

public class MergeSort {
	static void merge(int arr[], int first, int last) {
		int sort[] = new int[arr.length];	// arr의 값들을 정렬하여 저장할 배열 생성
		
		int mid = (first + last) / 2;
		int leftidx = first;	// arr의 왼쪽 부분을 움직이는 index
		int rightidx = mid + 1;	// arr의 오른쪽 부분을 움직이는 index
		int sortidx = first;	// sort 배열의 index
		
		System.out.println("merge() 실행 - first:"+first+", last:"+last);
        
        
		while (leftidx <= mid && rightidx <= last) {
        // leftidx와 rightidx 둘 중 하나라도 범위를 벗어나면 한 쪽은 정렬이 끝났다는 뜻
			if (arr[leftidx] <= arr[rightidx])	// 왼쪽 값이 더 작은 경우 또는 두 값이 같은 경우
				sort[sortidx++] = arr[leftidx++];	// 왼쪽 값을 sort에 저장, 왼쪽 index 증가
			
			else						 		// 오른쪽 값이 더 작은 경우
				sort[sortidx++] = arr[rightidx++];	// 오른쪽 값을 sort에 저장, 오른쪽 index 증가
		}
		// 반드시 왼쪽과 오른쪽 중 먼저 끝나는 곳이 있음
	
		if (leftidx > mid) {  // 왼쪽이 정렬이 먼저 끝난 경우
			for (int i = rightidx; i <= last; i++)	// 오른쪽 부분의 남은 값들을 순서대로 sort에 저장
				sort[sortidx++] = arr[i];
		}
		else	 {			  // 오른쪽이 정렬이 먼저 끝난 경우
			for (int i = leftidx; i <= mid; i++) 	// 왼쪽 부분의 남은 값들을 순서대로 sort에 저장	
				sort[sortidx++] = arr[i];
		}
		
		for (int i = first; i <= last; i++) { 
			arr[i] = sort[i];		// 정렬 완료된 값들을 원래 배열에 순서대로 저장
		}
	}
	
	static void merge_sort(int arr[], int first, int last) {
		int mid = (first + last) / 2;
		
		// arr의 크기가 1이 되면 if문을 실행하지 않고 중첩된 재귀함수를 빠져나오기 시작하면서 크기가 1이 되기 이전 arr에서 merge 메소드가 실행된다.
		// merge_sort의 반복 순서 : 왼쪽 - 오른쪽 - 위
		if (first < last) {	// arr의 크기가 1이 될 때까지 나누는 것을 반복
			merge_sort(arr, first, mid);	// arr의 왼쪽 부분
			merge_sort(arr, mid + 1, last);	// arr의 오른쪽 부분
			merge(arr, first, last);	// arr를 오름차순으로 정렬
		}
	}
	
	
	public static void main(String[] args) {
		int arr[] = { 7,3,6,4,2,9,1};
		
		System.out.println("[초기 배열]");
		for (int i = 0; i < arr.length; i++)
			System.out.print(arr[i]+" ");
		System.out.println("\n");
		
		merge_sort(arr, 0, arr.length-1);	// arr의 첫 index부터 마지막 index를 넘겨줌
	
		System.out.println("\n[정렬된 배열]");
		for (int i = 0; i < arr.length; i++)
			System.out.print(arr[i]+" ");
		System.out.println();
	}
}

 

2. 좀 더 효율적인 버전

import java.io.*;

public class Main {
	static void merge(int arr[], int first, int last) {
		int cnt = last-first+1;	// 정렬을 할 부분의 길이
		int sort[] = new int[cnt];	// 해당 부분의 값들을 정렬하여 저장할 배열
		
		int mid = (first + last) / 2;
		int leftidx = first;	// arr의 왼쪽 부분을 움직일 index
		int rightidx = mid + 1;	// arr의 오른쪽 부분을 움직일 index
		int sortidx = 0;	// sort 배열의 index

		System.out.println("merge() 실행 - first:"+first+", last:"+last);

		while (leftidx <= mid && rightidx <= last) {  // leftidx와 rightidx 둘 중 하나라도 범위를 벗어나면 한 쪽은 정렬이 끝났다는 뜻
			if (arr[leftidx] <= arr[rightidx])	// 왼쪽 값이 더 작은 경우 또는 두 값이 같은 경우
				sort[sortidx++] = arr[leftidx++];	// 왼쪽 값을 sort에 저장, 왼쪽 index 증가
			
			else						 		// 오른쪽 값이 더 작은 경우
				sort[sortidx++] = arr[rightidx++];	// 오른쪽 값을 sort에 저장, 오른쪽 index 증가
		}
		// 반드시 왼쪽과 오른쪽 중 먼저 끝나는 곳이 있음
	
		if (leftidx > mid) {  // 왼쪽이 정렬이 먼저 끝난 경우
			for (int i = rightidx; i <= last; i++)	// 오른쪽 부분의 남은 값들을 순서대로 sort에 저장
				sort[sortidx++] = arr[i];
		}
		else	 {			  // 오른쪽이 정렬이 먼저 끝난 경우
			for (int i = leftidx; i <= mid; i++) 	// 왼쪽 부분의 남은 값들을 순서대로 sort에 저장	
				sort[sortidx++] = arr[i];
		}
		
		sortidx=0;
		for (int i = first; i <= last; i++) {	// 정렬 완료된 값들을 원래 배열에 순서대로 저장 
			arr[i] = sort[sortidx++];	// sort에 정렬한 값들을 맨 앞부터 arr의 전달 받은 부분에 저장
		}
	}
	
	static void merge_sort(int arr[], int first, int last) {
		int mid = (first + last) / 2;
		
		// arr의 크기가 1이 되면 if문을 실행하지 않고 중첩된 재귀함수를 빠져나오기 시작하면서 크기가 1이 되기 이전 arr에서 merge 메소드가 실행된다.
		// merge_sort의 반복 순서 : 왼쪽 - 오른쪽 - 위
		if (first < last) {	// arr의 크기가 1이 될 때까지 나누는 것을 반복
			merge_sort(arr, first, mid);	// arr의 왼쪽 부분
			merge_sort(arr, mid + 1, last);	// arr의 오른쪽 부분
			merge(arr, first, last);	// arr를 오름차순으로 정렬
		}
	}
	
	
	public static void main(String[] args) throws IOException {
  		int arr[] = { 7,3,6,4,2,9,1 };
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		System.out.println("[초기 배열]");	// 초기 값 출력
		for (int i = 0; i < arr.length; i++)
			System.out.print(arr[i]+" ");
		System.out.println("\n");
		
		merge_sort(arr, 0, arr.length-1);	// arr의 첫 index부터 마지막 index를 넘겨줌
	
		System.out.println("\n[정렬된 배열]");	// 정렬한 값 출력
		for (int i = 0; i < arr.length; i++) {
			bw.write(arr[i]+" ");
			bw.flush();
		}
		bw.close();
	}
}

 

실행 결과>>

[초기 배열]
7 3 6 4 2 9 1 

merge() 실행 - first:0, last:1
merge() 실행 - first:2, last:3
merge() 실행 - first:0, last:3
merge() 실행 - first:4, last:5
merge() 실행 - first:4, last:6
merge() 실행 - first:0, last:6

[정렬된 배열]
1 2 3 4 6 7 9 

---

 

"merge() 실행"이라는 출력 부분에서 merge 메소드의 실행 순서를 알 수 있다.

[0]~[1], [2]~[3], [0]~[3], [4]~[5], [4]~[6], [0]~[6] 순으로 merge 메소드가 실행된다.

이는 merge_sort 메소드가 재귀함수여서, 계속해서 배열의 왼쪽으로 중첩이 되다가 배열의 크기가 1이 된 순간 if(first<last) 조건문을 만족하지 않기 때문에 중첩된 재귀함수를 하나씩 벗어나게 된다.

해당 배열의 왼쪽에 대한 재귀함수를 벗어나면 오른쪽에 대한 재귀함수가 실행되고 위 과정이 반복된다.

전체적인 동작을 살펴보면 왼쪽 - 오른쪽 - 위 로 동작한다고 볼 수 있다. 

merge 메소드는 해당 배열의 왼쪽 부분과 오른쪽 부분의 값을 하나씩 비교하는데, 더 작은 값을 sort 배열에 저장하고 더 작았던 쪽의 index를 증가시킴으로써 해당 배열의 값을 오름차순으로 정렬한다.

 

https://blog.naver.com/rbals0445/221313176730 

이 곳에 잘 설명되어 있으니 참고하자!