[자료구조/알고리즘] - 합병(병합)정렬

janjanee·2021년 3월 18일

Merge sort Sort 병합정렬 알고리즘 자료구조 정렬 합병정렬

자료구조/알고리즘

목록 보기

4/10

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

배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 합병하는 작업을 반복하여 정렬

합병정렬은 안전 정렬에 속하며, 분할 정복 알고리즘의 한 종류이다.

분할 정복 알고리즘이란?
- 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘을 뜻한다.
- 분할 정복 알고리즘은 보통 재귀를 통해 구현된다.

합병 정렬 알고리즘의 순서는 다음과 같다.

배열 요소 개수가 2개 이상인 경우 (길이가 1 이하이면 이미 정렬된 것으로 본다.)

분할 : 정렬되지 않은 배열을 절반으로 잘라 비슷한 크기의 두 배열로 나눈다.
정복 : 각 부분 배열을 재귀적으로 합병 정렬을 이용해 정렬한다.
결합 : 두 부분 배열을 다시 하나의 정렬된 배열로 합병한다. 이때, 정렬 결과는 임시배열에 저장된다.
복사 : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

합병정렬 - 예시

합병정렬 001

정렬되지 않은 배열을 이용하여 합병정렬을 한다.

합병정렬 002
합병정렬 003
합병정렬 004

그룹 내의 숫자가 한 개가 될 때까지 계속 반씩 분할해 나간다.
분할이 완료되면, 분할한 각 그룹을 병합한다. (거꾸로)

합병정렬 005

병합할 때는 병합 후의 그룹에서 숫자가 작은 순으로 나열되도록 정렬한다.
- 3, 1 -> 1, 3 으로 병합
- 2, 6 은 그대로 2, 6 으로 병합

합병정렬 007

[1, 3] 그룹과 [2, 6] 그룹을 병합할 때는 여러 숫자를 포함하기 때문에 각 그룹의 선두 숫자를
비교해서 작은 숫자를 먼저 이동한다.
1과 2를 비교하면 2 > 1 이므로 1을 이동한다.

합병정렬 008

2와 3을 비교하면 3 > 2 이므로 2를 이동한다.

합병정렬 009

3과 6을 비교하면 6 > 3 이므로 3을 이동한다.

합병정렬 010

남은 6은 그대로 마지막 자리로 이동된다.
나머지 그룹 병합 작업은 모든 숫자가 하나의 그룹이 될 때까지 재귀적으로 반복한다.

애니메이션

합병정렬 전체 과정 애니메이션이다.

합병정렬

합병정렬 - Java 코드

public class MergeSortTest {

    static int[] buff;  //  임시 배열은 전역 변수로 지정하여 매번 buff를 새로 생성하지 않도록 한다.

    public static void mergeSort(int[] arr) {

        // 배열 크기만큼 임시 배열 생성
        buff = new int[arr.length];

        // 분할 정복을 이용한 배열 전체 합병정렬
        mergeSort(arr, 0, arr.length - 1);

    }

    private static void mergeSort(int[] arr, int left, int right) {

        // 크키가 1보다 큰 경우만 분할
        if (left < right) {

            int center = left + (right - left) / 2;  //  중간을 기점으로 균등 분할 (분할)

            mergeSort(arr, left, center);            //  배열의 앞부분을 재귀적으로 합병정렬 (정복)
            mergeSort(arr, center + 1, right);  //  배열의 뒷부분을 재귀적으로 합병정렬 (정복)
            merge(arr, left, center, right);        //  실제 합병 수행

        }
    }

    private static void merge(int[] arr, int left, int center, int right) {

        // i는 arr[left] ~ arr[right] 배열의 인덱스
        int i;
        // p는 buff에 복사한 요소의 개수
        // j는 buff의 값과 arr의 값 비교 시 buff에서 사용하는 인덱스
        int p = 0, j = 0;
        // 새로 합병될 arr의 인덱스
        int k = left;

        // 배열의 앞부분 (a[left] ~ a[center])을 buff[0] ~ buff[center - left]에 복사.
        for (i = left; i <= center; i++)
            buff[p++] = arr[i];

        // 배열의 뒷부분 (a[center + 1] ~ a[right])과 buff로 복사한 배열의 앞부분 p개를 병합하여 배열 arr에 저장
        while (i <= right && j < p)
            arr[k++] = (buff[j] <= arr[i]) ? buff[j++] : arr[i++];

        // 배열 buff에 남아 있는 요소를 배열 arr에 복사
        while (j < p)
            arr[k++] = buff[j++];

    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 6, 7 , 5, 4};

        // 합병정렬
        mergeSort(arr);

        // 결과 출력
        System.out.println(Arrays.toString(arr));

    }

}

코드 과정 설명

코드의 merge() 메소드 흐름을 그림으로 조금 더 자세히 살펴보자.

무제 001

처음으로 수행되는 병합과정이다.

무제 002

배열의 앞부분 arr[0]을 buff 임시 배열에 복사한다.
p는 복사된 개수를 의미

무제 003

배열의 뒷부분 arr[1]과 buff로 복사한 앞부분 arr[0]을 병합하여 arr 배열에 저장
1과 3을 비교하면 1이 작은 숫자 이므로 arr[0]에 1이 들어간다.
뒷부분 배열에 비교할 요소가 없으므로 루프를 종료한다.

무제 004

buff 배열에 3이라는 요소가 남아있으모로 arr[1] 자리에 채운다.
합병정렬이 완료됐다.

무제 005

위와 동일한 방식으로 2, 6도 합병정렬이 됐다고 가정하고 이번에는 두 개 그룹 [1, 3]과 [2, 6]을 병합하자.

무제 006

배열의 앞부분 arr[0] ~ arr[1]을 buff 임시 배열에 복사한다.

무제 007

배열의 뒷부분 arr[2] ~ arr[3]과 buff로 복사한 앞부분 arr[0] ~ arr[1]을 병합하여 arr 배열에 저장
1과 2를 비교
둘 중 작은 수 1이 arr[0]에 들어간다.
j, k를 한칸 뒤로 이동한다.

무제 008

2와 3을 비교
둘 중 작은 수 2가 arr[1]에 들어간다.
i, k를 한칸 뒤로 이동한다.

무제 009

3과 6을 비교
둘 중 작은 수 3이 arr[2]에 들어간다.
j, k를 한칸 뒤로 이동한다.
buff 배열(앞부분)에 비교할 요소가 없으므로 루프가 종료된다.

무제 010

배열 buff에 남아있는 요소가 없으므로 종료
배열 뒷부분에 남아있는 요소인 6은 자동으로 해당 위치에 정렬이 된다.

합병정렬 특징

장점
- 시간복잡도
  - 배열의 요소가 1개가 될 때 까지 분할 -> n번 호출
  - 배열을 반씩 분할 해가며 정렬 -> logN 만큼의 시간 소요
  - 즉, 최종적으로 한 번 호출당 검색할 데이터 양이 절반이 되므로 O(nlogn)의 시간복잡도를 가진다.
- 안정적인 정렬
- 데이터의 분포에 영향을 덜 받는다. 입력 데이터가 무엇이든 간에 O(nlogn) 로 동일
- 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터 이동은 무시될만큼 작아짐.
단점
- 데이터가 배열로 구성된 경우 추가적인 메모리 임시 배열(buff)이 필요하다.
- 데이터 크기가 큰 경우 이동 횟수가 많으므로 시간 낭비 발생