병합 정렬(Merge Sort)에 대해 알아보자

이번 포스팅에서는 병합 정렬에 대해서 알아보겠다. 병합 정렬은 전체를 잘게 나누어 작은 조각끼리 먼저 정렬시키는 것을 반복해 결국 전체를 정렬하는 방법이다. 전문용어로는 분할 정복(Divide and Conquer)이라고 한다. 평균적인 시간복잡도는 O(nlogn)을 가진다. 문제를 풀 때 가끔 사용되고 특이하게도 지난번의 버블 정렬 문제인데 버블 정렬을 쓰면 안 되는 그 문제의 변형문제에 병합정렬이 사용된다. 이제 자세한 방법을 알아보자.

빨간색 줄이 분할한 기준선이다.

먼저 병합정렬을 하기 위해서는 전체를 가장 작은 단위로 나누어야 한다. 1개의 숫자만을 가지게 나누면 비교의 의미가 없어지니 2개씩 가지도록 나누자. 만약 홀수개라서 1개만 남으면 이번 단계에서는 그냥 놔두고 다음 단계에서 합치면 된다. 이제 2개씩 묶인 숫자들을 각각 정렬한다. 위의 예제에서 8과 2의 순서가 바뀌어 저장된 것을 볼 수 있다. 이렇게 2개씩 정렬을 했으면 이제 2 게씩 묶은 숫자들을 한 개의 단위로 하여 서로 병합한다. 즉 정렬된 2개, 2개 총 4개의 숫자를 다시 정렬시킨다는 말이다. 2회에서 4개씩 숫자가 정렬된 것을 볼 수 있다. 그리고 이것을 또 반복한다. 그러면 언젠가는 모든 숫자가 정렬될 것이다.

이렇게 글로만 보면 단순하지만 실제로 구현을 해보려고 하면 다소 난감하다. 정렬을 어떻게 해줘야 할까? 병합 정렬에서는 각각의 단위를 정렬할 때 임시로 사용할 공간이 필요하다. 병합정렬은 주로 재귀의 형태로 정렬의 한 사이클을 함수로 만들어 구현하는데 해당 함수가 시작할 때 임시 공간을 선언할 수 도 있고 미리 원본크기의 배열을 선언해 놓고 그것을 이용할 수 도 있다. 나는 미리 배열을 선언해 놓고 정렬 함수에서 정렬할 부분의 값들을 복사해서 넣어주고 시작하였다. 두 개의 배열을 병합할 때 프로그램에서는 투 포인터를 사용한다. 두 배열의 처음에 포인터를 위치시키고 작은 것부터 값을 옮기며 포인터를 증가시키는 것이다. 이것은 작은 단위가 미리 정렬되어 있기 때문에 가능하다. 앞의 숫자가 무조건 작기 때문이다. 이런 정렬 방법을 함수로 구현해 재귀로 가장 작은 단위에 도달한 후 병합을 시작하면 어렵지 않게 구현할 수 있다. 이때 홀수개의 숫자 묶음도 처리할 수 있도록 포인터의 끝쪽 동작을 잘 구현해야 한다.

병합 정렬을 구현한 코드이다. 백준 2751번을 이용하였다.

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] num = new int[N];
        int[] temp = new int[N];
        for(int i=0;i<N;i++){
            num[i] = Integer.parseInt(br.readLine());
        }
        if(N==1){
            bw.write(num[0]+"");
            bw.flush();
            bw.close();
            System.exit(0);
        }
        mergeSort(num, temp, 0, N-1);
        for(int i=0;i<N;i++){
            bw.write(num[i]+"\n");
        }
        bw.flush();
        bw.close();
    }
    static void mergeSort(int[] num, int[] temp, int start, int end){
        if(end-start<1){
            return;
        }
        int mergePoint = (start+end)/2;
        mergeSort(num, temp, start, mergePoint);
        mergeSort(num, temp, mergePoint+1, end);
        int i = start;
        int j = mergePoint+1;
        int s = start;
        for(int k=start;k<=end;k++){
            temp[k] = num[k];
        }
        while(i<=mergePoint && j<=end){
            if(temp[i]<=temp[j]){
                num[s] =  temp[i];
                i++;
            }else{
                num[s] = temp[j];
                j++;
            }
            s++;
        }
        while(i<=mergePoint){
            num[s] = temp[i];
            i++;
            s++;
        }
        while(j<=end){
            num[s] = temp[j];
            j++;
            s++;
        }
    }
}

병합 정렬 함수를 호출하면 먼저 최소단위까지 전부 나누고 시작한다는 것을 볼 수 있다. 그리고 인덱스를 잡아주고 임시 배열에 원본의 값을 복사해준 뒤, 투 포인터로 대소비교를 통해 값을 하나씩 복사해 준다. 마지막에는 남은 값을 전부 복사해 주고 재귀적으로 구현한 함수이므로 상위함수로 이동해 같은 로직을 반복한다. 나는 퀵 정렬로 풀려고 하다가 시간 초과가 나서 병합정렬로 했더니 바로 통과되었다. 아마 퀵 정렬의 최악의 경우가 테스트케이스에 들어가 있는 모양이다.

 

병합 정렬을 응용하는 문제로는 백준 1517번이 있다.

https://www.acmicpc.net/problem/1517

1517번: 버블 소트

버블 정렬 문제이지만 버블 정렬로 풀면 바로 시간초과다. 이 문제의 핵심은 버블 정렬의 swap을 병합 정렬에서 발견할 수 있다는 것이다. 병합의 각 단계에서 자신의 위치보다 앞쪽으로 이동한 숫자들은 작은 숫자들일 것이다. 이 숫자들이 몇 칸 이동했는지 새면 버블 정렬의 swap이 몇 번 일어났는지 유추할 수 있다. 병합을 할 때마다 작은 숫자들이 앞으로 몇 칸 이동했는지 전부 새면 그것이 정답이다. 몇 칸 이동했는지는 인덱스를 이용해 알아낼 수 있다. 이 문제는 플래티넘이라 다소 어려우니 기본 정렬 문제에서 병합 정렬을 먼저 구현해 본 뒤에 도전해 보자. 아이디어만 있다면 기본 병합 정렬 코드에서 수정이 많이 필요하지 않은 문제이다.

import java.io.*;
import java.util.*;

public class Main {
    public static int[] num, temp;
    public static long ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        num = new int[N];
        temp = new int[N];
        ans = 0;
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            num[i] = Integer.parseInt(st.nextToken());
        }
        mergeSort(0, N-1);
        bw.write(ans+"");
        bw.flush();
        bw.close();
    }
    static void mergeSort(int start, int end){
        if(end-start<1){
            return;
        }
        int mergePoint = (start+end)/2;
        mergeSort(start, mergePoint);
        mergeSort(mergePoint+1, end);
        int i = start;
        int j = mergePoint+1;
        int s = start;
        for(int k=start;k<=end;k++){
            temp[k] = num[k];
        }
        while(i<=mergePoint && j<=end){
            if(temp[i]<=temp[j]){
                num[s] =  temp[i];
                i++;
                s++;
            }else{
                num[s] = temp[j];
                ans += j - s;
                j++;
                s++;
            }
        }
        while(i<=mergePoint){
            num[s] = temp[i];
            i++;
            s++;
        }
        while(j<=end){
            num[s] = temp[j];
            j++;
            s++;
        }
    }
}

숫자가 뒤에서 앞으로 올 때 정답에 카운트를 추가하는 구문이 추가되었을 뿐 전체적인 로직은 위의 코드와 일치한다.

 

다음 포스팅에서는 기수 정렬에 대해서 알아보도록 하겠다.