정렬 알고리즘 3 (병합 정렬, 힙 정렬, 도수 정렬)

• 병합 정렬 (merge sort)

 병합 정렬을 알기 전에 병합 정렬의 기본이 되는 정렬을 마친 두 배열의 병합 과정을 알아야 한다. 정렬된 배열 a와 b가 있고 각각의 크기는 na, nb라 하자. 그리고 이 배열들의 병합해서 배열 c에 저장하는 과정을 살펴 보자. 우선 배열 a, b, c의 index를 나타내는 포인터를 각각 pa, pb, pc라 하고 이들을 0으로 초기화한다. 그리고 a[pa]와 b[pb]를 비교해 더 작은 값을 c[pc]에 저장한다. 이때 a[pa]를 c[pc]에 저장했으면 pa++, pc++를 하고, b[pb]를 c[pc]에 저장했으면 pb++, pc++를 한다. 그리고 이 과정을 pa > na가 되거나 pb > nb가 될때까지 반복한다. 반복이 끝나면 배열 c에 들어가지 못한 값들을 c에 저장한다. 즉 배열 a와 배열 b의 값들을 순서대로 비교해 배열 c에 넣는 과정을 배열 a의 값을 다 넣거나 배열 b의 값을 다 넣을 때까지 반복하고 배열 c에 들어가지 못한 배열 a 혹은 b의 나머지 값들을 c에 저장하면 배열 병합이 끝난다.

static void merge(int[] a, int[] b, int[] c) {
    int pa = 0; int na = a.length;
    int pb = 0; int nb = b.length;
    int pc = 0;
    while(na > pa && nb > pb){
        if(a[pa]<b[pb]) c[pc++]=a[pa++];
        else c[pc++]=b[pb++];
    }
    while(na > pa)
        c[pc++]=a[pa++];
    while(nb > pb)
        c[pc++]=b[pb++];
}

   첫번째 while문이 a배열과 b배열을 작은 값부터 비교해 배열 c에 넣는 반복문이다. 이때 a와 b 둘중 하나라도 배열 값을 c에 다 넣으면(na>pa&&nb>pb) while문을 탈출한다. 두번째 while문은 배열 b의 값들이 다 저장되어 첫번째 while문을 탈출 했을때 c에 저장하지 못한 a의 값들을 순서대로 c의 남은 자리에 저장해주는 반복문이고, 세번째 while문은 반대로 a의 값들을 c에 다 저장해서 c에 저장하지 못한 b의 값들이 존재할 경우 c의 남은 자리에 저장해주는 반복문이다. 배열을 병합하는 알고리즘의 시간 복잡도는 O(n)이다.

 

  이제 이를 이용하여 병합 정렬 알고리즘을 배워보자. 배열 a가 0~11의 index를 갖는 크기가 12인 배열이라 하자. a를 2분할 하여 index가 0~5인 그룹 a'과 index가 6~12인 그룹 b'을 만든다. 이때 a'과 b'을 각각 정렬하여 병합하면 병합된 배열 a를 얻을 수 있고 이때 배열 a는 병합 정렬 알고리즘에 의해 정렬됐다고 볼 수 있다. 하지만 a'과 b'은 정렬이 되지 않았으므로 a'과 b' 각각에 대해 병합 정렬을 진행한다. 따라서 a'를 병합 정렬 하기 위해 이를 2분할 하여 a'1과 a'2의 그룹 2개를 만들고 a'1과 a'2를 정렬하여 병합하면 a'의 병합 정렬이 끝난다. 하지만 또 a'1과  a'2는 정렬이 안돼있으므로 각각을 또 병합 정렬을 해야한다. 이렇게 병합 정렬 알고리즘은 2개의 그룹으로 나눴을 때 2개의 그룹이 정렬할 필요가 없을 때까지(나눠진 그룹의 요소가 1개가 될 때까지) 나눈다. 이 조건이 만족될때까지 나눴다면 이제 나눠진 그룹들의 병합을 전체를 병합할 때까지 반복 한다. 즉 병합 정렬 알고리즘의 순서는 다음과 같다.

 

(배열의 요솟수가 2개 이상인 경우)

1. 배열의 앞부분을 병합 정렬로 정렬한다.

2. 배열의 뒷부분을 병합 정렬로 정렬한다.

3. 배열의 앞부분과 뒷부분을 병합한다.

 

 병합 정렬을 하는데 그 안에서 또 병합 정렬을 해야하므로 코드로 구현할 때 재귀 호출이 일어난다. 코드로 구현한 병합 정렬 알고리즘은 다음과 같다.

static int[] buff;
static void mergesort(int[] a, int n) {
    buff = new int[n]; // 작업용 배열 생성

    __mergesort(a,0,n-1); // 배열 전체를 병합 정렬

    buff = null; // 작업용 배열 해제
}
static void __mergesort(int[] a, int left, int right) {
    if(left<right){
        int center = (left + right) / 2;

        __mergesort(a,left,center); // 왼쪽 그룹 병합 정렬
        __mergesort(a,center+1,right); // 오른쪽 그룹 병합 정렬

        int pr; // 오른쪽 그룹의 pointer
        int nb = 0; // buff의 사용중인 공간의 크기
        int pb = 0; // buff의 pointer
        int pa = left; // 병합 정렬중인 a의 pointer

        for(pr = left; pr < center + 1 ; pr++){
            buff[nb++]=a[pr];
        }
        while(pr <= right && pb < nb) // buff와 a의 오른쪽 그룹의 병합
            a[pa++] = buff[pb] < a[pr] ? buff[pb++] : a[pr++];

        while(pb < nb) // buff의 값들이 남은 경우
            a[pa++] = buff[pb++];
    }
}

 배열 a를 정렬하기 위해 mergesort 메서드를 실행하면 a의 크기와 같은 작업용 배열 buff를 생산해주고 실제 병합 정렬을 하는 __mergesort 메서드로 들어간다. __mergesort 메서드를 사용하는 것을 지금부터 병합 정렬을 한다고 표현 하겠다. buff를 만들고 a를 병합 정렬하면 a가 left ~ center의 왼쪽 그룹과 center +1 ~ right의 오른쪽 그룹으로 나뉜다. 그리고 왼쪽그룹을 병합 정렬하고 그다음 오른쪽 그룹을 병합 정렬한다. 그러면 왼쪽 그룹과 오른쪽 그룹이 정렬된 후 병합이 시작된다. __mergesort내의 병합과정은 우리가 앞에서 배운것과 조금 다르다. 우리가 배운 것은 배열 3개를 이용한 병합이었지만 우리는 배열 a와 배열 buff 총 2개만 이용해서 병합을 진행한다. 어떻게 2개만으로 가능한지 확인해 보자. 우선 a의 왼쪽 그룹의 값들 a[left] ~ a[center]를 buff[0] ~ buff[na-1]에 저장한다. 그리고 a[left]에 buff[0]과 a[center+1]을 비교하여 작은 값을 넣고 pa(배열 a의 pointer), pb(배열 buff의 pointer), pr(오른쪽 배열의 pointer)을 상황에 맞게 증가시켜, 그 다음은 a[left+1]에 그 다음은 a[left+2]에 ...  마지막인 a[right]까지 buff와 오른쪽 그룹의 값들을 저장하며 병합한다. 이는 buff[0] ~ buff[nb]와 a[center+1] ~ a[right]의 2개 그룹을 a[left] ~ a[right] 배열에 병합하는 것과 같다. a를 2개로 나눠서 쓰는 알고리즘이라 범위가 겹쳐 오류가 생기지 않을까 걱정이 될 수 있지만 실제로는 어떻게 하더라도 범위가 겹치지 않아 오류 발생 걱정이 없다. 이렇게 buff와 a의 오른쪽 그룹중 하나의 그룹의 값을 다 저장하면 나머지 값을 a에 저장해야한다. 만약 buff에 값이 남은 경우를 대비해 buff의 값이 남은 경우의 while문을 만들어놨다. 하지만 오른쪽 그룹의 값이 남는경우, 오른쪽 그룹은 원래 배열 a를 사용하고 있으므로 굳이 옮기지 않아도 배열 a에 저장되어 있어 별다른 작업이 필요 없다.  

 

  배열 병합의 시간 복잡도는 O(n)이었고 병합 정렬의 전체 시간 복잡도는 O(n log n)이다. 병합 정렬은 서로 떨어져 있는 요소를 교환하는 경우가 없으므로 안정적인 정렬 방법이다.

 

• 힙 정렬 (heap sort)

    힙 이란?

 

  힙 정렬은 힙(heap)을 사용하여 정렬하는 알고리즘이다. 힙이란 부모값이 자식값보다 항상 큰 완전이진트리이고 형제 사이의 대소 관계는 일정하지 않다. 완전이진트리는 부모, 왼쪽 자식, 오른쪽 자식 순으로 채워지는 이진 트리로 마지막 레벨(맨 아래 줄)을 제외한 모든 레벨이 가득 차있는 트리이다. 그리고 이진 트리는 자식을 최대 2개 가질수 있는 트리를 말한다.   

 

  힙은 배열로 표현할 수 있는데 다음 규칙에 맞게 배열을 만들면 된다.

 1. 부모는 a[(자식의 index - 1) / 2]

 2. 왼쪽 자식은 a[(부모의 index) * 2 + 1]

 3. 오른쪽 자식은 a[(부모의 index) * 2 + 2]

 따라서 부모의 index가 5면 왼쪽 자식의 index = 5*2+1 = 11이고 오른쪽 자식의 index = 5*2+2 = 12이다. 역으로 자식의 index를 이용해 부모의 index를 계산해보면 (11-1)/2 = 5,  (12-1)/2 = 5로 부모의 index인 5가 나오는 것을 알 수 있다.

 

    힙 정렬 구현하기

 

 힙 정렬은 앞에서 말했듯 힙을 이용한 알고리즘으로 힙의 가장 큰 값이 root(부모가 없는 자리로 힙의 가장 위)에 위치하는 특징을 이용한 정렬 알고리즘이다. 알고리즘은 다음과 같이 진행된다. 

 

1. 힙에서 가장 큰 값인 루트를 꺼내고 배열의 마지막 자리에 저장한다.

2, 비어있는 루트를 힙의 나머지 값들 중 가장 큰 값으로 채워 힙을 유지한다.

3. 정렬이 끝날 때까지 이 과정을 반복한다. 

 

  1번은 그냥 root의 값을 배열의 마지막값과 교환해 주면 된다. 구현하기 쉬운 1번에 비해 2번은 생각을 좀 해볼 필요가 있다. 우선 1번을 한번 실행하면 배열의 마지막 값은 고정되므로 정렬해야하는 요소가 1개 줄어들고 맨 마지막 값이 root로 올라왔으므로 배열이 힙이 아니게 됐을 가능성이 크다.(마지막 값은 작은 값이므로) 따라서 힙을 유지하고 남은 값들 중 가장 큰 값을 찾기 위해 고정된 마지막 값을 제외한 나머지 값들로 힙을 유지해야 한다. 현재 root에 있는 값을 자식들과 비교, 교환을 하며 내려보내면  힙을 유지할 수 있다. root에 있는 값이 왼쪽 자식과 오른쪽 자식보다 작으면 부모는 자식들보다 커야하므로 자식중 1개와 바꿔줘야한다. 만약 자식이 둘 다 부모보다 크면 자식 중 더 큰 값을 가진 자식과 부모를 바꿔준다. 이렇게 자식들보다 큰 부모가 될때까지 root에 있는 값을 내려주면 힙이 유지될 수 있다. 이렇게 1, 2, 3번을 구현하는 법을 알아봤다. 

 힙 정렬 알고리즘을 구현하기 위해 우리는 1개를 더 배워야 한다. 바로 1, 2, 3번의 전제를 충족시켜야 한다는 것이다. 1, 2, 3번의 전제는 시작하기 전부터 배열이 힙이어야 한다는 것이다. 그래서 우리는 주어진 배열을 힙으로 만드는 방법을 배울 것이다. 

  힙을 만들기 위해 우리는 bottom-up 방식 , 즉 작은 힙부터 만들어 올라가는 방식을 사용할 것이다. 배열의 마지막 index값을 정해 부모로 지정하고 그 부모의 자식 값들과 비교해 앞에서 본 것처럼 자식들 중 부모보다 더 큰 값이 있으면 자식과 부모를 교환한다(만약 자식이 둘다 부모보다 크면 둘 중 더 큰 값과 부모를 바꾼다). 이 과정을 배열의 index를 1씩 줄여가며 반복하고 index=0일 때까지 반복을 완료한다면 그 배열은 힙이 된다. 그러면 코드로 구현한 힙 정렬을 보고 이해해보자.

static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
static void downheap(int[] a, int left, int right) {
    int root = a[left];
    int child;
    int parent;

    for(parent = left; parent<(right+1)/2; parent=child){
        // (right-1)/2가 마지막 부모이므로 여기에 1을 더하면 (right+1)/2
        int lc = parent*2+1; // 왼쪽 자식
        int rc = lc + 1;  // 오른쪽 자식
        child = (rc<=right && a[rc] > a[lc])? rc : lc; // child에 자식들 중 큰 값을 저장
        if(a[child] <= root) break; // 부모값이 크거나 같으면 종료
        a[parent]=a[child];  // 자식값이 더 크면 자식을 부모자리로 이동 후 반복
    }
    a[parent] = root;
}
static void heapsort(int[] a, int n){
    for(int i = (n-2)/2; i >= 0; i--){ // 전체 배열을 힙으로 만듦
        downheap(a,i,n-1);
    }
    for(int i = n-1; i > 0; i--){ // 정렬 시작
        swap(a,0,i);
        downheap(a,0,i-1);
    }
}

  heapsort 메서드에서 힙 정렬을 시작하는데 우선 전체 배열을 힙으로 만든다. 여기서 사용되는 downheap은 매개변수가 a, left, right가 있는데 이는 배열 a의 left 인덱스에서 right 인덱스까지 heap으로 만들어주는 메서드이다. downheap 메서드를 살펴보면 root 값을 a[left]로 저장해 놓고 for문을 통해 자식들과의 비교를 해가며 자식이 더 크면 자식과 부모의 자리를 바꾸고 반복하고, 부모가 더 크면 반복문 종료후 정해진 부모자리에 root 값을 입력한다. 이렇게 downheap 메서드를 통해 전체 배열을 힙으로 만들면 정렬을 시작한다. 배열 a[n-1]부터 root값을 넣어가며 정렬을 완성시켜가고 a[1]의 자리까지 root를 집어넣으면 정렬이 끝난다. (a[0]은 자동으로 정렬됨)

 

  힙 정렬을 알아봤는데 잘 보면 a[n-1]에 가장 큰 값을 넣고 a[n-2]에 그 다음으로 큰 값을 넣고 이런 방식을 반복하는 것이 단순 선택 정렬 방법에서 a[0]에 가장 작은 값을 넣고 a[1]에 그 다음 작은 값을 넣고 채워가는 과정이랑 비슷하다. 하지만 시간 복잡도가 O(n^2)인 단순 선택 정렬에 비해 힙 정렬의 시간 복잡도는 O(n log n)으로 힙 정렬이 단순 선택 정렬에 비해 훨씬 빠르다.

 

• 도수 정렬 (counting sort)

  도수 정렬은 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다. 따라서 요소들을 비교하고 교환하는 과정이 없고 도수분포표만들기, 누적도수분포표 만들기, 목표 배열 만들기, 배열 복사하기 4단계를 거치면 정렬이 완성된다. 그러면 단계별로 확인해 보자.

 

    1. 도수분포표 만들기 

  a = { 5, 7, 0, 2, 4, 10, 3, 1, 3 }을 도수 정렬 알고리즘을 이용해 정렬을 해보자. 우선 작업용 배열 f를 배열 a의 요솟값 중 최댓값인 10에 1을 더한 크기로 만든다. (배열 f의 크기 = 11) 그리고 a의 요솟값을 index로 하여 f[index]에 1을 더해주는 과정을 a의 요솟값 전부에 대해 진행한다. 따라서 f = { 1, 1, 1, 2, 1, 1, 0, 1, 0, 0, 1 }이 된다( a의 요소가 0~2가 1개씩, 3이 2개, 4~5가 1개씩,  6이 0개, 7이 1개, 8~9가 0개, 10이 1개이므로 다음과 같이 완성된다). 이러면 도수분포표 f가 완성된다.

 

    2. 누적도수분포표 만들기

  배열 f를 누적도수분포표로 만들어야한다. 각각의 index들은 누적값을 가져야 하므로, f[1]부터 본인의 값에 앞의 값을 더한 값을 갖게 만들면 된다. 즉 f[i] = f[i-1]을 index 1부터 10까지 하면 f = { 1, 2, 3, 5, 6, 7, 7, 8, 8, 8, 9 }가 된다.

 

    3. 목표 배열 만들기

  이제 배열 a와 크기가 같은 배열 b를 만들어 누적도수분포표를 이용하여 정렬한다. 그 과정은 다음과 같다.

 

1) 정렬할 a의 요솟값 a[ i ]를 정해 f[a[ i ]] 값을 찾는다.

2) 배열 b의 index = f[a[ i ]] - 1인 곳에 a[ i ]를 저장한다.

3) f[a[ i ]] = f[a[ i ]] -1을 해준다.

4) a의 모든 요솟값에대해 위 과정을 반복한다.

 

a[8]을 배열 b에 정렬해보자. a[8] = 3이므로 f[3] = 5를 이용한다. b[5-1] = b[4]이므로 b[4]에 a[8]의 값인 3을 저장한다. 그리고 f[3]의 값에 1을 빼준다.(f[3] = 4)

a[7]을 배열 b에 정렬해보자. a[7] = 1이므로 f[1] = 2를 이용한다. b[2-1] = b[1]이므로 b[1]에 a[7]의 값인 1을 저장한다. 그리고 f[1]의 값에 1을 빼준다.(f[1] = 1)

마지막으로 a[6]을 배열 b에 정렬해보자. a[6]은 앞에서 정렬한 a[8]과 같은 3이다. f[3] = 4를 이용하는데 f[3]은 앞에서 한 번 썼기 때문에 5에서 1을 뺀 4가 된다. b[4-1] = b[3]이므로 b[3]에 a[6]의 값인 3을 저장한다. 그리고 f[3]의 값에 1을 빼준다. (f[3] = 3) a[6]까지 정렬해보니 왜 3번 과정이 필요한지 알 수 있다. 그 이유는 같은 값을 갖는 경우 f[a[i]]값이 b의 같은 index로 a[i]값을 안내하기 때문에 중복을 피하기 위해 1을 빼줘야 하는 것이다. 이렇게 b를 다 채우면 b = { 0, 1, 2, 3, 3, 4, 5, 7, 10 }이 된다.

 

    4. 배열 복사하기

  배열 b는 우리가 작업용으로 만든 것이므로 이를 배열 a 에 복사해야한다. 이 과정은 for문을 이용한다. 

  

  이제 이 4단계를 이용한 도수 정렬을 코드로 구현해보자.

static void count(int[] a, int n, int max){
    int[] f = new int[max+1];
    int[] b = new int[n];
    for(int i=0; i<n; i++) f[a[i]]++;  // 1단계
    for(int i=1; i<max+1; i++) f[i]+=f[i-1]; // 2단계
    for(int i=0; i<n; i++) b[--f[a[i]]]=a[i]; // 3단계
    for(int i=0; i<n; i++) a[i]=b[i]; // 4단계
}

count 메서드는 총 4단계의 for문을 거친다. 도수 정렬 알고리즘은 데이터를 비교, 교환하는 작업이 필요 없어 매우 빠르다. 다중 for문이 아닌 단순 for문만 사용하고, 재귀 호출, 2중 for문이 없어 아주 효율적인 알고리즘이다. 하지만 도수분포표가 필요하기 때문에 배열 a의 최댓값과 최솟값을 알고있어야만 사용이 가능하다. count 메서드 내부의 4개의 for문에서 반복을 순서대로 진행하면 안정적인 알고리즘이 되고 순서대로 진행하지 않으면 안정적이지 않은 알고리즘이 된다.