Chap3-1. 합병 정렬(MergeSort)

합병 정렬

= 입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 절반으로 감소하는 분할 정복 알고리즘 중 대표

  -순환문의 형태로 정렬을 한다.

  -2개의 부분 문제를 합병하면서 정렬하는 알고리즘

 

[ 설명 ]

• 정렬과 탐색 알고리즘이 제일 중요하다. 가장 효율적으로 원하는 것을 찾는 것이 매우 중요
• 정렬 알고리즘은 구현의 복잡도에 따라 단순한 알고리즘, 복잡으로 나눌 수 있다.

-단순한 알고리즘 = 순차적으로 찾아다니면서 한다(1씩 감소하면서 정렬) ex) 문제의 크기가 1씩 감소하는
                         중첩된 반복문을 통해 크기를 비교한다. → 시간 복잡도를 따지면 n * n의 시간 복잡도임
-복잡한 알고리즘  = 단순보다는 효율적이다. - 합병 정렬
                           로그 선형으로 가기 때문에 n의 제곱보단 효율적이라고 할 수 있다 .

 

합병 정렬 과정

[합병 과정]

    = 문제를 부분 문제로 나누고 부분 문제(2개의 각각 정렬된 숫자들)을 1개의 정렬된 숫자로 합치는 것

 

ex)

   (1번째) 각각의 부분 문제 A와 B는 정렬되어 있음

       부분 문제 A : 6 14 18 20 19

       부분 문제 B : 1 2 15 25 30 45

   (2번째) A와 B를 각각 비교하여 합친다. <순차적으로 서로를 비교한다>

 

알고리즘

-합병 정렬의 특징은 입력 배열과 출력 배열이 다르다. → 단점

MergeSort(A, p, q)
입력 : A[p] ~ A[q] 
출력 : 정렬된 A[p] ~ A[q] // 입력 배열과 출력 배열은 다르다. 이름은 같지만 다른 배열이라고 생각하자

1. if (p < q) { //입력 배열의 왼쪽 끝 인덱스와 오르쪽 끝 인덱스를 의미
//p = q이면 남은 원소는 1개이므로 더 이상 정렬 불가 -> 끝 
2.    k = [ (p+q) / 2 ] // 범위를 반으로 나눈다. (바닥 함수, 소수점 버림)
3.    MergeSort(A. p. k) // 앞부분 자르면서 수행 
4.    MergeSort(A, k+1, q) // 앞부분 다 자르면 뒷부분 자르면서 수행
5.    A[p] ~ A[k] 와 A[k+1] ~ A[q]를 합병
}

합병 정렬 소스 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 15

void makeList(int list[])
{
    for(int i = 0; i < SIZE; i++)
        list[i] =rand() % 100 + 1;
}

void printList(int list[])
{
    for(int i = 0; i < SIZE; i++)
        printf("%d ", list[i]);
    printf("\\n");    
}

void merge(int list[], int sorted[], int left, int mid, int right)
{
    int i, j, k, l;
    i = left; j = mid + 1; k = left;
    
    while(i <= mid && j <= right)
    {
        if(list[i] <= list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }
    
    if(i > mid)
        for(l = j; l <= right; l++)
            sorted[k++] = list[l];
    else
        for(l = i; l <= mid; l++)
            sorted[k++] = list[l];
            
    for(l = left; l <= right; l++)
        list[l] = sorted[l];
}

void mergeSort(int list[], int sorted[], int left, int right)
{
    int mid;
    if(left < right)
    {
        mid = (left + right) / 2;
        mergeSort(list, sorted, left, mid);
        mergeSort(list, sorted, mid + 1, right);
        merge(list, sorted, left, mid, right);
    }
}

int main()
{
	int list[SIZE], sorted[SIZE];
	srand(time(NULL));
    
    makeList(list);
    printList(list);
    
    mergeSort(list, sorted, 0, SIZE - 1);
    printList(sorted);
    //printList(list);
}

 

 

[예시 - 과정 ]

문제 : n = 8, A = [37, 10, 22, 30, 35, 13, 25, 24]

MergeSort(0, 0)  // 여기서는 if ( p < q)조건을 만족하지 않으므로 끝나버림
===========================
MergeSort(0, 1) 
    k = 0
     MergeSort(0, 0)...// 대기하고 있다가 호출한 것이 끝남(1)
 (2) MergeSort(1, 1) // (3) 함수 끝 -> (4) MERGE() (5) 이 부분 끝남
==================
MergeSort(0, 3) 
   k = 1 // 3/2
    MergeSort(0, 1).... // 대기하고 있다가 호출한 것이 끝남(1)
(2) MergeSort(2, 3) // (3) 함수 끝 -> (4) MERGE() (5) 이 부분 끝남
======================
MergeSort(0, 7) //0~ 7인덱스를 합병 정렬 한다. 
  k = 3 // (0 + 7)/2
  MergeSort(0, 3).... 
  MergeSort(4, 7)

함수를 호출하면 함수의 호출 정보는 컴퓨터 메모리 상의 시스템 스택이라는 곳에 저장된다.

순차적으로 쌓인다.

여기서 MergeSort(0, 7)를 호출하고 기록이 되는 와중에 또 다시 MergeSort(0, 3) 라는 함수를 호출한다. 그러면 컴퓨터는 가장 최근에 호출된 함수( MergeSort(0, 3) ) 의 처리를 우선적으로 한다.

 

 

시간복잡도

[ 1. 분할하는 과정 ]

1. k = [ (p+q) / 2 ] - >분할
2. MergeSort(A. p. k) → 함수 호출
3. MergeSort(A, k+1, q)

→ 위의 2, 3, 4인 분할 하는 부분은 중간 인덱스 계산(2번 부분)과 2회의 순환 호출이므로 O(1) 시간이 소요된다(큰 숫자 만큼 반복해도 상수 횟수만큼 반복하는 것이다 → 빅오 표기법에 의해 신경쓰지 않아도 된다)

 

[ 2. 합병 하는 과정]

 

만약 배열A가 4개가 있고 배열 B가 4개가 있다고 가정하자

각각 하나의 원소씩 비교하는데 마지막 하나 남은 원소는 비교할 대상이 없으므로 비교를 수행하지 않아도 된다. 따라서 4 + 4 -1만큼의 비교 횟수가 필요할 것이다.

이를 일반화하면, 2개의 정렬된 배열 A와 B의 크기가 각각 m과 n이라면, 최대 비교 횟수는 (m + n -1)

합병의 시간 복잡도 = O(m + n) = 입력 데이터가 n개 이므로 O(n)이라고 할 수 있다.

 

층수 비교 횟수

입력 데이터가 더 이상 분할될 수 없을 때까지 분할되고 점차 합병하는데 합병을 기준으로 “층”으로 표현하자면

1층 = (37) (10)    (22) (30)          (35) (13)        (25) (24)

2층 = (10, 37)    (22, 30)              (13 ,35)      (24, 25)

3층 =    (10, 22, 30, 37)                      (13, 24, 25, 35)

                (10, 13, 22, 24, 35, 30, 35, 37)

 

    => 따라서 각 층마다 O(n)번씩 비교하므로 전체 비교횟수는 O(3n)이다.

 

층수의 계산

입력 크기          층

n

n/2                 1층

n/4 = n/2^2     2층

n/8 = n/2^3     3층

분모의 지수자리가 층이다.

 

⇒ 입력크기가 n개일 때, k 번 1/2로 분할했으면 k개의 층이 생기는 것이고 k는 2^k = n으로부터 log2의 n이라는 것을 알 수 있다.

따라서 합병 정렬의 시간 복잡도는

(층수) * O(n) = log2의 n * O(n) = O(nlogn)이다. (로그 선형 함수의 기울기를 따른다)

→ 2차 함수보다 더 효율적이다. (구현은 복잡하지만)

 

 

[ 시간 복잡도를 순환 방적식으로 표현 가능 ]

T(n) = aT(n/b) + n의 d승

여기서 aT(n/b)는 분할할 때 시간 복잡도를 의미하며, n의 d승은 합병할 때 시간 복잡도를 의미

조건에 따라 T(n)은 3가지 케이스가 있다.

1. d <logb의 a → O(n의 logb의a승)
2. d = logb의 a → O(n의 d승 * log n)
3. d > logb의 a → O(n의 d승)

합병 정렬의 단점

입력 데이터를 위한 공간 + 입력과 같은 크기의 공간(임시 배열)이 필요

공간 복잡도가 O(n)개 만큼 더 필요하다.

↔ 다른 알고리즘의 공간 복잡도 = 입력 데이터를 위한 공간 + 변수를 하나를 위한 공간

 

합병 정렬의 장점

1. 합병정렬은 외부 정렬의 기본이 되는 정렬 알고리즘이다.

합병 정렬은 내부 정렬이지만 부분만 가지고 와서 정렬한다는 개념이 외부 정렬과 유사하다는 의미

 

[외부 정렬 vs 내부 정렬]
내부 정렬은 정렬하기 전에 모든 데이터가 메인 메모리에 올라오게 된다. → 합병 정렬이든 퀵정렬이든 컴퓨터 프로그램으로 돌리는 모든 알고리즘은 내부정렬이다.
합병 정렬도 내부 정렬인데 합병 정렬의 개념이 부분 부분들이 정렬되는 개념이 외부 정렬과 유사하다는 것이다. 외부정렬이라는 것은 아니다.
만약 엄청난 데이터를 정렬을 하려면 구조상 내부 정렬이 불가능하다. 하드디스크에 데이터를 넣고 거기서 조금씩 가져와서 정렬하는 개념이다.

 

 

1. 모든 자료구조는 배열 혹은 연결리스트를 통해 나타낼 수 있다. 서로 장단점이 있다.

   배열은 쉽다. 하지만 배열의 특성상 공간이 중간 중간 비는데 이 공간을 메꿔야 한다는 단점이 있다. (처리를 하기 위해 하는 연산과 배열을 유지하기 위한 연산이 또 필요하다)

   ↔ 연결리스트는 구현이 어렵지만 중간에 값이 빠져도 상관없다. 연결만 하면된다.

퀵이나 합병 정렬이나 힙 정렬은 배열로 표현하는 것이 더 적합 하지만 연결리스트로 구현은 할 수 있다. 저 3가지 알고리즘 중에 합병이 연결리스트로 나타내기가 더 좋다.