[알고리즘] 정렬(병합, 기수) 알고리즘 (3)

 

병합 정렬

 

분할 정복, 데이터를 분할하고 분할한 집합을 정렬하는 병합 정렬 알고리즘의 정렬 방식이다

특이한 점은 swap을 사용하지 않는 다는 것이다.

여기서 swap이란, 인접한 요소와 비교하여 교환하는 것을 말한다.

 

그럼 어떤 방식을 사용하길래 swap을 쓰지 않고도 정렬이 가능한 걸까?

병합 정렬의 핵심은 병합이다.  이 과정에서 정렬이 되게끔 재 조합한다는 것이다.

직접 코드를 살펴보며, 어떠한 방식으로 구동되는 지 살펴보자.

 

 

병합 정렬 문제 풀이

 

백준 2751번 문제를 통해 병합 정렬을 구현할 수 있다.

2751번: 수 정렬하기 2

 

 

 

해당 문제에 대한 풀이이다.

import java.util.*;
import java.io.*;
public class Main {
    public static int[] A, tmp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        A = new int[N+1];
        tmp = new int[N+1];

        for(int i=1; i<=N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }


        merge_sort(1, N);

        for(int i=1; i<=N; i++) {
            bw.write(A[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static void merge_sort(int s, int e) {
        if (e -s < 1) {
            return;
        }
        int m = s + (e-s)/2;

        merge_sort(s, m);
        merge_sort(m+1, e);
        for(int i=s; i<=e; i++) {
            tmp[i] = A[i];
        }

        int k=s;
        int index1 = s;
        int index2 = m+1;
        while(index1 <= m && index2 <= e) {
            if(tmp[index1] > tmp[index2]) {
                A[k] = tmp[index2];
                k++;
                index2++;
            } else {
                A[k] = tmp[index1];
                k++;
                index1++;
            }
        }

        while(index1 <= m) {
            A[k] = tmp[index1];
            k++;
            index1++;
        }
        while(index2 <= e) {
            A[k] = tmp[index2];
            k++;
            index2++;
        }

    }


}

 

 

코드에서 핵심적인 부분은 merge_sort메서드 부분이다.

해당 메서드는 두 부분으로 나뉠 수 있다. 한번 병합 정렬의 개념을 생각해보자.

 

분할과 정복

 

메서드를 자세히 살펴보면, 재귀적으로 merge_sort를 호출한다.
여기서 중간 값 m을 기준으로 분할 하는 과정을 발견할 수 있다.

이 과정은 e-s < 1, 즉 원소의 개수가 1개가 될때까지 재귀적으로 merge_sort를 호출한다. 호출이 완료된 각 부분 그룹들은 임시 배열 tmp에 그 값들을 복사해 놓는다.

이제 정복을 위한 핵심적인 부분이다. 이 구조 자체는 기억해 놓는 것이 좋을 듯 하다.
중간 값을 기준으로 나눈 각 부분 그룹들의 첫 번째 인덱스로 부터 각자 비교를 시작한다.
비교 결과 작은 값부터 정렬이 되도록, 작은 값을 원본 배열 A[k]에 위치시킬 수 있다.

두 부분 그룹 중, 하나가 먼저 끝나는 경우가 있다. 이러한 상황을 대처하기 위해 while문을 통해서 각 부분 그룹의 남은 요소들을 원본 배열 A에 그대로 집어넣는 코드를 넣어준다.

 

 

 

 

기수 정렬

 

기수 정렬은 값 자체를 비교하지 않으면서 정렬을 수행할 수 있는 알고리즘이다.

값을 놓고, 비교할 자릿수를 정한 후 해당 자릿수만 비교한다.

기수 정렬의 시간 복잡도는 O(kn)으로 k는 데이터의 자릿수를 의미한다.

 

 

자릿수 기준으로 정렬?

 

직접 기수 정렬을 해본 바로 간단하게 표현하자면, "누적하여 정렬" 이라고 말할 것 같다.

자릿수를 일의 자리부터 최대 자릿 수까지 정렬을 꾸준히 거치며 업그레이드하는 방식이기 때문이다.

 

기수 정렬은 시간복잡도가 가장 짧다. 그래서 만일 코딩 테스트에서 정렬 데이터 개수가 너무 많다면 기수 정렬 방법을 고려해 볼 것 같다.

 

 

기수 정렬 문제 풀이

 

문제에서 N의 최대 개수가 많이 커진다면, 기수 정렬 문제를 생각할 수 있다.

백준 10989 문제를 풀며 기수 정렬 수행 방법을 살펴보자.

 

10989번: 수 정렬하기 3

 

import java.util.*;
import java.io.*;
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));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        for(int i=0; i<N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        Radix_Sort(A, 5);
        for(int i=0; i<N; i++) {
            bw.write(A[i] + "\n");
        }
        bw.flush();
        bw.close();

    }
    public static void Radix_Sort(int[] A, int max_size) {
        int[] output = new int[A.length];
        int jarisu = 1;
        int count = 0;
        while(count != max_size) {
            int[] bucket = new int[10];

            for(int i=0; i< A.length; i++) {
                bucket[(A[i] / jarisu) % 10]++;
            }
            for(int i=1; i<10; i++) {
                bucket[i] += bucket[i-1];
            }

            for(int i=A.length-1; i>=0; i--) {
                output[bucket[(A[i] / jarisu % 10)] -1] = A[i];
                bucket[(A[i] / jarisu) % 10]--;
            }
            for(int i=0; i< A.length; i++) {
                A[i] = output[i];
            }
            jarisu = jarisu * 10;
            count++;
        }
    }

}

 

 

 

기수 정렬 메서드는 Radix_Sort()이다. 해당 메서드의 인자로, 정렬을 수행할 배열과 최대 자릿수 값을 넣어준다.

메서드 내부로 들어가보면, ouput[], bucket[], jarisu 변수가 있다.
이 변수들은 굉장히 중요하므로, 잘 기억해 두자.

bucket은 현재 자릿수들의 분포를 합 배열 형태로 알려주는 배열이다.(왜 합 배열인가? -> 중복 값들이 없어지지 않도록 하기 위함). 이 bucket을 합 배열 대신 우선 순위 큐로도 나타내는 것이 간단하기는 하나, 합 배열을 사용하는 것이 더욱 효율적이라고 한다.


output은 임시 정렬을 위한 배열이다. 각 자릿수 이동 시마다 원본 배열과 합쳐진다.

jarisu는 현재 자릿수를 표현하는 수이다.

 

bucket은 각 자릿수의 분포의 빈도를 먼저 저장해주고, 합 배열 형식으로 바꾸어, 후에 정렬 시 누락되는 값이 없도록 한다.

 

output은 현재 자릿수를 기준으로 정렬을 해준다. 합 배열의 값 자체가 인덱스가 되어 처리가 가능하다. 대신 합 배열의 값을 하나씩 줄여주어야, 누락 값이 없도록 할 수 있다.

 

다음 자릿수로 이동하기 전에 현재 자릿수 기준으로 한 정렬 데이터 output을 원본 배열에 그대로 옮겨준다.

 

 

 

Reference

- Do it! 코딩 테스트 - 기초 편