Insertion sort, merge sort 소개와 시간복잡도 구하기 (c구현)

Insertion sort

삽입정렬은 아직 정렬되지 않은 부분에서, 정렬된 부분에 순서를 유지하면서 반복적으로 삽입하는 알고리즘이다.

 

우선 첫 번째 인덱스를 선택하여 (정렬될) 앞부분에 삽입하는 것으로 회차를 마친다. 이후 두 번째 인덱스는 이미 정렬된 부분에서 순서에 맞게 삽입되고 회차를 마친다. 

이렇게 정렬된 부분의 순서를 해치지 않고 삽입하는 방식의 알고리즘이다.

 

전체 순회에서 올바른 장소에 key값을 삽입하는 코드가 n번 반복하고, n번 반복하는 순회 안에서 키값을 삽입하기 위한 올바른 장소를 찾는 데에 n번 반복하기 때문에 O(n^2)의 시간복잡도를 갖는다.

void Insertion(int arr[], int size)
{
    // 현재 회차에서 삽입할 element인 key
    int key;

    // 삽입정렬에서 첫 번째 step은 자동으로 결정되기 때문에 int i를 1로 설정. 
    for (int i = 1; i < size; i++) {
        // 현재 index에 저장된 element를 key값에 저장. 어디에 삽입할지 결정하기 위해 배열을 순회할 key
        key = arr[i];
        // 현재 선택한 element의 앞 index들을 전부 순회할 것이라 현재 index - 1
        int j = i - 1;

        // 순회할 index j가 0보다 크고, 앞서 정렬된 element들이 key값보다 크면 요소를 오른쪽으로 이동
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 정렬이 완료되었으면, 조건을 충족했을 때도 j--가 실행되므로 +1을 해준 index에 key값 삽입
        arr[j + 1] = key;
    }
}

 

 

Merge sort ( Divide and Conquer )

divide and conquer 방식은 위 그림처럼
큰 문제를 나눠서 작은 문제로 만들고, 잘게 나눈 문제들을 각자 해결한 뒤, 해결한 문제들을 합하여 원본 문제를 해결하는 것이다.

 

merge sort도 divide and conquer방식으로 해결한다.

우선 정렬해야 할 리스트를 반으로 나누고, 각각 리스트를 merge sort를 사용하여 정렬한다. 정렬 후 다시 합쳐서 원본 문제를 해결한다.

 

merge sort의 시간복잡도를 구하는 과정은 3 단계로 나눌 수 있다.

divde하는 단계와 conquer, combine하는 시간들을 구한 후 합쳐서 시간복잡도를 구해보자.

 

우선 나누는 단계이다

그냥 리스트를 반으로 나누기만 하는 것이다. 실제 연산이 필요한 명령은 아니므로 계산은 Θ(1)이다. 

다음은 각각을 conquer하는 단계이다. 각각을 반으로 나눈 후  T(n/2)의 연산을 반복하기 때문에
T(n/2)를 2번 곱해준 2 * T(n/2)만큼의 시간 복잡도를 갖는다.

마지막으로 combine하는 단계는 서로 나눈 리스트를 합치는 과정에서 

여기서 25와 47을 합칠 때, 바로 2547로 합치는 것이 아니라 이미 정렬된 25 중 2를 47과 비교해서 넣고, 5를 47과 비교해서 임의의 배열에 넣는것으로 정렬한다. n/2 길이 리스트와 n/2 길이 리스트를 하나의 n 길이의 리스트(temp array)로 combine 할 때 필요한 연산은 Θ(n)이다.

그럼 merge sort의 시간복잡도는 T(n) = 2*T(n/2) + Θ(n) + Θ(1) = 2*T(n/2) + cn 의 재귀 식을 얻는다는 것을 알 수 있다.

#define MAX_NUM 100

// 정렬된 요소를 임시로 저장해둘 배열 tempsort 선언
int tempsort[MAX_NUM];

void Merge(int arr[], int left, int middle, int right)
{
    // 배열을 순회하는 데에 사용할 index들의 선언
    int i, j, k;
    i = left; // 정렬된 왼쪽 리스트 인덱스
    j = middle + 1; // 정렬된 오른쪽 리스트 인덱스

    // tempsort를 순회할 index값 k 선언
    k = left;

    // start point와 end point를 전부 순회하기 위한 while문
    // 가상의 Left 배열과 Right 배열을 index i와 j로 구분
    while (i <= middle && j <= right)
    {
        // left와 middle+1의 index값을 비교해서 둘 중 더 작은 값을 tempsort에 할당하는 것으로 합침
        // middle index쪽이 더 크다면 left값 할당
        if (arr[i] <= arr[j])
        {
            tempsort[k] = arr[i];
            i++;
        }
        // left index쪽이 더 크다면 middle값 할당
        else
        {
            tempsort[k] = arr[j];
            j++;
        }
        k++;
    }

    // 위 while 순회에서 Left배열의 index i가 주어진 길이를 넘었을 경우
    if (i > middle)
    {
        // j index부터 right index까지 쭉 저장(이미 정렬된 상태)
        for (int t = j; t <= right; t++)
        {
            tempsort[k] = arr[t];
            k++;
        }
    }
    else
    {
        // i index부터 middle index까지 쭉 저장(이미 정렬된 상태)
        for (int t = i; t <= middle; t++)
        {
            tempsort[k] = arr[t];
            k++;
        }
    }
    // 지금까지 tempsort에 정렬해놓은 요소들을 우리가 정렬할 배열 arr에 할당
    for (int t = left; t <= right; t++)
    {
        arr[t] = tempsort[t];
    }

}

// 요소들을 잘게 나누는 과정을 재귀적으로 반복한 후 merge를 이용해서 순서대로 합침
void MergeSort(int arr[], int left, int right)
{
    // 가장 왼쪽 index와 오른쪽의 index를 비교하여 현재 배열이 존재하는지 판단
    if (left < right) 
    {
        // 중간 index middle
        int middle = (left + right) / 2;
        // 두 개의 하위 배열로 나누기 divide
        MergeSort(arr, left, middle);
        MergeSort(arr, middle + 1, right);

        // 분할된 두 하위 배열을 합치기 merge
        Merge(arr, left, middle, right);
    }
}

 

그런데 지금까진 바로 구해왔었는데.. 재귀식의 시간복잡도는 어떻게 구하지?

merge sort의 시간복잡도를 구하기 위한 예시 그림 하나를 보자.
T(n) = 2*T(n/2) + cn

이 식에서 시간복잡도를 구하려면 2*T(n/2)의 계산을 알아야 한다.

 

우선 우리는 한번 반복할 때 마다(각 LEVEL마다 ) 얼마만큼의 비용이 드는지 알아야 한다.

k번 진행했을 때 노드는 총 n개 있고, 비용은 2^k의 규칙으로 나타낼 수 있으므로
k(몇 번 반복했는지) 는 log n으로 나타낼 수 있다.

즉, T(n) = 2*T(n/2) + cn 의 식을 연산하는 데에 드는 비용은
cn의 비용이 총 log n번(level) 걸리므로 곱해주면 O(n log n)으로 나타낼 수 있다.

 

이렇게 divide and conquer방식의 merge sort 알고리즘을 사용하면 O(n log n)의 시간복잡도를 얻을 수 있기 때문에 다른 정렬에 비해서 이득을 볼 수 있다. 

이 알고리즘은 쉽게 병렬화되어 처리될 수 있고, 이해랑 구현하기도 쉽다. 하지만 높은 메모리 사용량이 필요하고 분석하기가 어렵다는 단점이 있다.

 

 

어려운 만큼 여러가지 분석 방법이 있다.

우선 substitution 방법을 통해 시간 복잡도를 재귀로 해결해보자.
(솔직히 비추.. 어차피 나중에 다른 방식으로 풀 테지만 알아는 둬야하니..)

 

Substitution 방법은 2가지 단계가 있다.
1. 어떻게 문제를 해결할 것인지 가정하는 단계
2. 수학적인 유도를 통해 추측이 과연 맞는 것인가 증명하는 단계 

예를들어 T(n) = 2*T(n/2) + n 의 재귀가 있다.

1. 우리는 일단 그냥 T(n) = O(n^2)으로 가정한다.
2. 그 식을 그대로 대입해서 T(n) = 2*T(n/2) + n <= 2*c(n^2/4) + n = cn^2 식을 얻는다.

이 부등식은 C가 2보다 크거나 같고 n이 1보다 크거나 같으면 성립한다. 그런데 이런식으로 하는 asymptotical bound이 올바른 방법... 이 맞을까?

 

이렇듯, 오직 재귀만으로 좋은 해결책을 추측하는 것은 어렵다.

그래서 substitution 방법의 보완으로 나온게 Recursion - Tree method이다.

 

1. 우선 재귀 tree를 그린다.
2. 각 레벨의 비용을 계산한다.
3. 총 레벨의 수를 계산한다. (깊이)
4. 마지막 레벨의 비용을 계산한다.

다음 예시를 통해 알아보자.

일단 이렇게 recursion tree를 그린다.

2번. 각 레벨의 비용은 cn으로 동일함을 알 수 있다.

3번. 총 레벨의 수를 계산한다. (n  = 2^k 이므로 k = lg n)

마지막으로 가장 밑에 있는 level의 비용을 계산해보면 cn이다. cn이 log n개 있으니 시간복잡도는 O(n lg n)

 

이렇게  recursion tree T(n) = O(n lg n) 으로 추측해 봤는데 과연 맞는 값인지 수학적 유도로 증명해보자.

제대로 증명됐다. 맞는 추론이었던것 같다.

 

 

다음 예시다. T(n) = 3T(n/4) + O(n^2)

 

트리를 그렸으니, 이제 깊이와 각 레벨의 비용을 구해보자.

각 레벨별 비용은 (3/16)^k (cn^2)이다.

tree의 깊이 k를 구해보면 k = log4 n

가장 아래에 있는 level의 비용들은 T(1)이 3^k 만큼 있으므로 k를 대입해주면
 T(1) * 3^(log 4 n) 이다. 로그법칙을 이용해서 n^(log 4 3)으로 표현해줄 수도 있다. 

여기서 이것과 각 노드의 비용을 곱해준 T(1) * n^(log 4 3) 을 얻을 수 있다.
T(1)은 근사해서  O(n^(log 4 3))

 

아까와 다르게 레벨 별 비용이 다르니 직접 합쳐주자. (각 레벨별 비용 + 마지막 레벨 비용 따로)
왜 마지막 레벨만 따로 계산하냐면 최종적으로 나눠진 T(1)을 따로 구해야 하기 때문.
어차피 근사할 것이라도 과정이 다름.

이것으로 T(n) = O(n^2) 이것이 성립함을 알게 됐다. (세타 값에서 n의 지수가 1보다 작으므로)

 

 

 

마지막 예시이다. T(n) = T(n/3) + T(2n/3) + cn

이건 진짜 못봤던 패턴이다. 사실 이전 예제도 만만찮긴 한데 이런식으로 나눠지는건...

아무튼 트리를 그렸으니 각 레벨의 비용과 그때 노드들의 수를 구해보자.

 

 

그런데.. 일단 트리의 깊이를 구할 때 부터 고비다. 이건 무엇을 기준으로 해야하는 건지.. 그래서 교수님이 준비해주신 그림이 있다.

트리를 그릴 때 이와 같은 그림이 그려지니 더 깊이가 깊은것을 기준으로 측정하겠다. 옆에 빈 부분은 어차피 근사처리 한다나..

그리고 이번엔 각 레벨별 비용은 모두 cn (ㅋㅋ 여기서 비용은 그래도 양반으로 내주심)

레벨은 위에 보다싶이 log3/2 n

이렇게 모두 합쳐주면 cn * log3/2 n  >>  T(n) = O(n log n)

 

과연 이것이 맞을까 증명하는 과정은 길긴 한데 다음과 같다.

 

아 이렇게 드디어 시간복잡도 계산이 끝났구나~ 이제 그만~