Java - 정렬 알고리즘 - 4 (병합 정렬)

◎병합 정렬

배열 분할을 반복하여 최대한 작게 쪼개진 시점에 부분배열에서 인접한 원소들끼리 비교하여 정렬하는 방식

'분할 정복(Divide and Conquer)' 알고리즘을 기반으로 정렬한다.

 

-분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘 이다. 보통 재귀함수를 통해 자연스럽게 구현된다.

---

◎병합 정렬의 특징

1. 비교 정렬(comparison sort)

 병합 정렬은 데이터를 비교하면서 찾는다.

 

2. 제자리 정렬(in-place sort)이 아님

정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 한다.

 

3. 안정 정렬(stable sort)

정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지된다.

---

◎병합 정렬의 동작

병합 정렬의 동작, 출처: https://st-lab.tistory.com/233?category=892973

1.  입력 배열을 2개의 부분 배열로 분할한다(divide)

2.  분할된 배열의 크기가 충분히 작지 않으면(배열의 크기가 1이 아니라면), 순환 호출을 이용하여 다시 분할한다(divide)

3.  분할된 배열이 충분히 작아졌으면(배열의 크기가 1이라면) 인접합 부분 배열들을 합병하여 정렬한다.(conquer)

 

좀 더 자세히 설명하면, 

divide, 출처: https://reakwon.tistory.com/38

이 과정이 divide 과정으로, 길이가 1인 부분 배열이 될때까지 분할하는 것이다.

 

conquer, 출처:https://reakwon.tistory.com/38

이 과정이 conquer 과정으로, 배열을 합병하면서 정렬한다.

 

- [3]배열과 [4]배열을 합병하는 과정:

[3]배열과 [4]배열은 원소가 각각 한개이므로, 정렬된 배열로 볼 수 있다.

그러므로, 배열의 첫번째 원소를 비교하여 더 작은 원소를 먼저 합병된 배열에 넣는다.

 

1. 3이 4보다 작으므로 3을 먼저 넣는다.

2. 3배열에 더 이상 원소가 없으므로 4를 넣어 [3,4]배열을 만든다.

 

-[1,3,4]배열과 [2,5]배열을 합병하는 과정:

[1,3,4]배열과 [2,5]배열은 정렬된 배열이다.

그러므로, 배열의 첫번째 원소를 비교하여 더 작은 원소를 먼저 합병된 배열에 넣는다.

 

1. [1,3,4]배열의 첫 원소 1이 [2,5]배열의 첫 원소 2보다 작으므로, 1을 넣는다.

2. [3,4]배열의 첫 원소 3이 [2,5]배열의 첫 원소 2보다 크므로, 2를 넣는다.

3. 과정을 반복하면, [1,2,3,4,5]배열이 만들어진다.

---

◎병합 정렬의 구현

1. Top-Down 형식, 재귀함수 사용

package SortAlgorithm;

import java.util.Arrays;

public class sort {
    //병합정렬 (Top-Down 형식, 재귀함수 사용) -1
	private void TopDown_mergesort(int[] numarr) {
		int[] tmparr = new int[numarr.length]; //임시배열 생성
		
		TopDown_innermergesort(numarr,0,numarr.length-1, tmparr);
		
		print(tmparr, "Top-Down 병합 정렬");
	}
	
	
	//병합 정렬 (Top-Down 형식, 재귀함수 사용) -2
	private void TopDown_innermergesort(int[] numarr, int start, int end, int[] tmparr) {
		
		
		
		if(start == end) { //부분 배열의 원소의 개수가 1개인 경우 더 이상 divide가 불가능하므로 return한다
			return;
		}
		
		int mid = (start+end)/2; //절반
		TopDown_innermergesort(numarr,start,mid,tmparr); //절반 중 왼쪽의 부분배열 divide and conquer
		TopDown_innermergesort(numarr,mid+1,end,tmparr);//절반 중 오른쪽의 부분배열 divide and conquer
		
		int left = start; //왼쪽 절반의 시작 지점
		int right = mid+1; //오른쪽 절반의 시작 지점
		int idx = left; //tmparr의 idx
		
		while(left<=mid || end>=right ) { //왼쪽이나 오른쪽에 원소가 남아있다면
        
        	// 오른쪽 원소를 다 사용했거나, (왼쪽 원소가 남아있고 왼쪽 원소가 더 작은 경우)
			if( right>end || (left<= mid && numarr[left]<numarr[right]) ){ 
				tmparr[idx] = numarr[left]; //왼쪽 원소를 tmparr에 넣는다
				idx++;
				left++; //사용한 원소는 비교대상에서 제외
			}else {
				tmparr[idx] = numarr[right];//오른쪽 원소를 tmparr에 넣는다
				idx++;
				right++;//사용한 원소는 비교대상에서 제외
			}
		}	
		
		for (int i = start; i <= end; i++) { //정렬된 부분 배열을 기존의 배열에 복사하여 붙여준다
			numarr[i] = tmparr[i];
		}
		/* 이 과정이 없다면, 부분배열을 정렬한 것이 원 배열에 반영되지 않아,
         * 합병하여 정렬하는 것이 반영이 되지 않는다
		 * 즉, 부분 배열을 정렬해놓고, 정렬 안되어있는 배열을 사용하는 셈이다
		 */
	}
	
	
	// swap
	private void swap(int[] numarr, int i, int j) {
		int temp = numarr[i];
		numarr[i] = numarr[j];
		numarr[j] = temp;
	}

	// 출력
	private void print(int[] numarr, String sortname) {
		System.out.println(sortname + "로 정렬된 배열:" + Arrays.toString(numarr));
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] numarr = { 5, 6, 3, 1, 4, 2 }; // 정렬할 배열
		System.out.println("원래 배열:" + Arrays.toString(numarr));

		sort Sort = new sort();

		Sort.TopDown_mergesort(numarr);

	}
}

실행 결과:

원래 배열:[5, 6, 3, 1, 4, 2]
Top-Down 병합 정렬로 정렬된 배열:[1, 2, 3, 4, 5, 6]

---

※재귀 함수의 장단점:

장점:

1. 코드에 대한 표현적인 측면에서 가독성이 좋아진다.

 

 단점:

1. 재귀의 깊이가 깊어졌을 때, stack overflow가 발생하면서 프로그램이 비정상적으로 종료될 수 있다.

2. 함수가 호출되고 종료될 때 스택 프레임을 구성하고 해제하는 과정에서 반복문보다 오버헤드가 들기 때문에 성능이 저하된다.

 

stack overflow:

함수를 호출하면 함수의 매개변수, 지역변수, 리턴 값, 그리고 함수 종료 후 돌아가는 위치가 스택 메모리에 함께 저장된다.

재귀함수를 쓰게되면, 함수를 반복적으로 호출하므로, 스택 메모리에 콜 스택이 쌓이게 된다. 함수를 호출하는 횟수가 많아진다면 스택 메모리를 초과하여 stack overflow가 발생할 수 있다.

그러나 일반적인 반복문을 사용하면 지역 변수들이 호출될 때 한번만 할당되기 때문에 그러한 비효율이 발생하지 않는다.

 

Overhead:

오버헤드(Overhead)는 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 말한다.

---

재귀함수를 이용하여 구성된 Top-Down 형식은 이해하기 쉽고, 코드가 직관적으로 포함되어있지만, stack overflow문제, overhead문제 등 여러 문제들이 발생할 수 있어서, 재귀함수를 사용하지 않고 병합정렬을 구현하는 편이 좋다.

 

 

2. Bottom-Up 형식, 재귀함수 사용 x

package SortAlgorithm;

import java.util.Arrays;

public class sort {
  
  	//병합 정렬 (Bottom-Up 형식, 재귀함수 사용 x) -1
	private void BottomUp_mergesort(int[] numarr) {
		int[] tmparr = new int[numarr.length]; //임시배열 생성
		
		BottomUp_innermergesort(numarr, tmparr);
		
		print(numarr, "Bottom-Up 병합 정렬");
		
	}
	
	//병합 정렬 (Bottom-Up 형식, 재귀함수 사용 x) -2
	private void BottomUp_innermergesort(int[] numarr, int[] tmparr) {
		
		for(int size = 1; size<numarr.length; size +=size) {
			//size = 나눌 배열의 크기, 1,2,4,8...로 증가한다
			for(int l = 0; l < numarr.length - size; l += (2 * size)) {
				/*
				 * 두개의 부분 배열을 합치는 것이다.
				 * Top-Down 형식에서 인덱스가 start~mid인 부분 배열과 
				 * 인덱스가 mid+1~end인 두 배열을 합친 것과 같이
				 * size 변수에 따라, 즉 low~mid 부분배열과 mid+1~high까지인 부분 배열을 병합한다.
				 * 이때, l + (2 * size) - 1(사이즈에 기반한 다음 부분배열의 크기)가 
				 * 원래 배열의 최대 인덱스보다 클 수 있으므로,
				 * Math.min함수를 통해 high 값을 제한해준다.
				 * l < numarr.length - size;에서 numarr.length - size부분은 
				 * 배열의 길이가 2의 제곱이 아닐경우에 어쩔 수 없이 생기는
				 * 하나 남은 배열을 방지해준다.
				 * 예를 들어, 배열의 길이가 6이고 size가 2라면, 
				 * for문은 인덱스가 0~1인 부분 배열과 인덱스가 2~3인 부분 배열을 합치고, 
				 * 4~6부분 배열이 홀로 남는다.
				 * 이때, numarr.length - size = 4이므로, 변수 ㅣ이 4보다 크거나 같아지지 않아서 
				 * 4~6배열이 merge함수에 들어가는 일을방지해준다.   
				 */
				int low = l;
				int mid = l + size - 1;
				int high = Math.min(l + (2 * size) - 1, numarr.length-1);
				merge(numarr, low, mid, high, tmparr);		// 병합(merging)작업
			}
		}
		
	}
	
	//병합정렬 병합(merging)함수(Top-Down ,Bottom-Up 형식 둘 다 사용 )
	private void merge(int[] numarr, int start, int mid, int end, int[] tmparr) {
		
		int left = start; //왼쪽 절반의 시작 지점
		int right = mid+1; //오른쪽 절반의 시작 지점
		int idx = left; //tmparr의 idx
		
		while(left<=mid || end>=right ) { //왼쪽이나 오른쪽에 원소가 남아있다면
			if( right>end || (left<= mid && numarr[left]<numarr[right]) ){ 
				// 오른쪽 원소를 다 사용했거나, (왼쪽 원소가 남아있고 왼쪽 원소가 더 작은 경우)
				tmparr[idx] = numarr[left]; //왼쪽 원소를 tmparr에 넣는다
				idx++;
				left++; //사용한 원소는 비교대상에서 제외
			}else {
				tmparr[idx] = numarr[right];//오른쪽 원소를 tmparr에 넣는다
				idx++;
				right++;//사용한 원소는 비교대상에서 제외
			}
		}	
		
		for (int i = start; i <= end; i++) { //정렬된 부분 배열을 기존의 배열에 복사하여 붙여준다
			numarr[i] = tmparr[i];
		}
		/*이 과정이 없다면, 부분배열을 정렬한 것이 원 배열에 반영되지 않아, 
		 * 합병하여 정렬하는 것이 반영이 되지 않는다
		 * 즉, 부분 배열을 정렬해놓고, 정렬 안되어있는 배열을 사용하는 셈이다
		 */
	}
	
	// swap
	private void swap(int[] numarr, int i, int j) {
		int temp = numarr[i];
		numarr[i] = numarr[j];
		numarr[j] = temp;
	}

	// 출력
	private void print(int[] numarr, String sortname) {
		System.out.println(sortname + "로 정렬된 배열:" + Arrays.toString(numarr));
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] numarr = { 5, 6, 3, 1, 4, 2 }; // 정렬할 배열
		System.out.println("원래 배열:" + Arrays.toString(numarr));

		sort Sort = new sort();

		Sort.BottomUp_mergesort(numarr);

	}
}

실행 결과:

원래 배열:[5, 6, 3, 1, 4, 2]
Bottom-Up 병합 정렬로 정렬된 배열:[1, 2, 3, 4, 5, 6]

---

◎병합 정렬의 시간 복잡도

 항상 두 부분리스트로 쪼개어 들어가기 때문에 최악의 경우에도 O(NlogN) 으로 유지가 된다. (언제나 O(NlogN)이다)

---

◎병합 정렬의 단점

제자리 정렬(in-place sort)이 아니므로, 다른 배열을 사용하여 함수를 정렬하기 때문에, 메모리 사용이 다른 정렬에 비해 크다.

보조 배열에서 원본 배열로 복사하는 과정에서 많은 시간을 소비한다.

◎Sorting algorithm 시간 복잡도(time complexity) & 평균 정렬 속도(average sorting rate)

Sorting algorithm 시간복잡도(time complexity) & 평균 정렬 속도(average sorting rate) 출처:   https://st-lab.tistory.com/195

 

 

---

◎정렬 알고리즘 구현-github

github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/sorting_algorithm

jerry-ryu/java_problemsolving_algorithm