[정렬]병합정렬

병합정렬(merge sort)

배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘
퀵정렬과 유사하지만 퀵정렬은 내부정렬, 병합정렬은 외부정렬(외부에 추가적인 배열를 선언하여 정렬)으로 차이가 있다. 

• 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다
• 배열을 앞부분과 뒷부분으로 나눈다
• 나눈 두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬할 수 있다.
• 이때 앞뒤에 놓인 배열을 정렬할 때는 그냥 정렬하는 것이 아니라 다시 병합 정렬을 이용한다.

 

▶︎ 가장 먼저 정렬을 마친 배열의 병합을 보면, 각 배열에서 선택한 요소의 값을 비교하여 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복하여 정렬을 마치는 것을 볼 수 있다. 

package com.study.Algorithm;
import java.util.Scanner;
// 정렬을 마친 배열의 병합

class MergeArray {
	// 정렬을 마친 배열 a, b를 병합하여 배열 c에 저장합니다. 
	static void merge(int[] a, int na, int[] b, int nb, int[] c) {
		int pa = 0;
		int pb = 0;
		int pc = 0;

		while (pa < na && pb < nb)	// 작은 값을 저장합니다.
			c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];

		while (pa < na)				// a에 남아 있는 요소를 복사합니다.
			c[pc++] = a[pa++];

		while (pb < nb)				// b에 남아 있는요소를 복사합니다.
			c[pc++] = b[pb++];
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int[] a = {2, 4, 6, 8, 11, 13};
		int[] b = {1, 2, 3, 4, 9, 16, 21};
		int[] c = new int[13];

		System.out.println("두 배열의 병합");

		merge(a, a.length, b, b.length, c);	  // 배열 a와 b를 병합하여 c에 저장

		System.out.println("배열 a와 b를 병합하여 배열 c에 저장했습니다.");
		System.out.println("배열 a：");
		for (int i = 0; i < a.length; i++)
			System.out.println("a[" + i + "] = " + a[i]);

		System.out.println("배열 b：");
		for (int i = 0; i < b.length; i++)
			System.out.println("b[" + i + "] = " + b[i]);

		System.out.println("배열 c：");
		for (int i = 0; i < c.length; i++)
			System.out.println("c[" + i + "] = " + c[i]);
	}
}

 

▶︎ 병합정렬 알고리즘의 구체적인 개념

• 병합정렬은 다음의 단계들로 이루어진다.
  - 분할(divide): 입력 배열을 같은 크기의 2개의 부분으로 분할한다.
  - 정복(conquer): 부분 배열을 정렬한다. 부분배열의 크기가 충분히 작지 않으면 순환호출을 이용하여 다시 분할정복한다.
  - 결합(combine): 정렬된 부분 배열들을 하나의 배열에 병합한다.
• 병합정렬의 과정
  - 추가적인 리스트가 필요하다.
  - 각 부분 배열을 정렬할 때도 병합정렬을 순환적으로 호출하여 적용한다.
  - 병합정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 병합(merge)하는 단계이다.

그림출처:https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

▶︎ 병합정렬 알고리즘의 예제

• 2개의 정렬된 리스트를 병합하는 과정
  1. 2개의 리스트의 값들을 처음부터 하나씩 바교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트로 옮긴다.
  2. 둘 중에 하나가 끝날 때까지 이 과정을 되풀이 한다.
  3. 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트로 복사한다.
  4. 새로운 리스트를 원래의 리스트로 옮긴다. 

그림출처: https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

• 예제코드

package com.study.Algorithm;
import java.util.Scanner;
// 병합 정렬

class MergeSort {
	static int[] buff;	// 작업용 배열

	// a[left] ~ a[right]를 재귀적으로 병합 정렬 
	static void __mergeSort(int[] a, int left, int right) {
		if (left < right) {
			int i;
			int center = (left + right) / 2;
			int p = 0;
			int j = 0;
			int k = left;
			
			System.out.println("left : " + left);
			System.out.println("right : " + right);
			System.out.println("center : " + center);
			System.out.println("p : " + p);
			System.out.println("j : " + j);
			System.out.println("k(left) : " + k);

			__mergeSort(a, left, center);			// 배열의 앞부분을 병합 정렬합니다.
			__mergeSort(a, center + 1, right);		// 배열의 뒷부분을 병합 정렬합니다.

			for (i = left; i <= center; i++) { 
				System.out.println("buff[" + p + "] : " + a[i]);
				buff[p++] = a[i];
			}

			while (i <= right && j < p) {
				System.out.println("buff[" + j + "] : " + buff[j] + " ::: a[" + i + "] : " + a[i]);
				System.out.println("buff[j] <= a[i] : " + (buff[j] <= a[i]));
				System.out.println("a[ " + k + "] = " + ((buff[j] <= a[i]) ? buff[j] : a[i]));
				a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
			}

			while (j < p) { 
				System.out.println("a[" + k + "] : " + buff[j]);
				a[k++] = buff[j++];
			}
		}
	}

	// 병합 정렬
	static void mergeSort(int[] a, int n) {
		buff = new int[n];				// 작업용 배열을 생성합니다.

		__mergeSort(a, 0, n - 1);		// 배열 전체를 병합 정렬합니다.

		buff = null;					// 작업용 배열을 해제합니다.
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.println("병합 정렬");
		System.out.print("요솟수：");
		int nx = stdIn.nextInt();
		int[] x = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.print("x[" + i + "]：");
			x[i] = stdIn.nextInt();
		}

		mergeSort(x, nx);		// 배열 x를 병합 정렬합니다.

		System.out.println("오름차순으로 정렬했습니다.");
		for (int i = 0; i < nx; i++)
			System.out.println("x[" + i + "]＝" + x[i]);
	}
}

그림출처: https://www.notion.so/b8e2aedb909f454b93a7a3e7fe499728

 

 

▶︎ 클래스 객체 배열의 정렬(병합정렬)

1. 자연 정렬이 필요한 배열
 - 정렬방법 1. static void sort(Object[] a)
                 2. static void sort(Object[] a, int fromIndex, int toIndex)

2. 자연 정렬이 필요하지 않은 배열
- 정렬방법 1. static <T> void sort(T[] a, Comparator<?super T> c)
                2. static<T> void sort(T[] a, int fromIndex, int toIndex, Comparator<?super T> c)
- comparator c를 이용하여 정렬하기
   - Comparable : 객체 간의 일반적인 정렬이 필요할 때, Comparable 인터페이스를 확장해서 정렬의 기준을 정의하는 compareTo() 메서드를 구현한다
   -Comparator : 객체 간의 특정한 정렬이 필요할 때, Comparator 인터페이스를 확장해서 특정 기준을 정의하는 compare() 메서드를 구현한다.

 

 

 

 

자료출처
[ https://www.notion.so/b8e2aedb909f454b93a7a3e7fe499728]
[medium.com/quantum-ant/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%ED%95%A8%EA%BB%98-%EB%B0%B0%EC%9A%B0%EB%8A%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%85%EB%AC%B8-c%EC%96%B8%EC%96%B4%ED%8E%B8-6%EC%9E%A5-d93a438b6f89]