Dasol Hong

I am a master’s student advised by Professor Hyun Myung at KAIST (Urban Robotics Lab).

[ALGO] Lect7. 삽입 정렬과 합병 정렬의 비교 분석을 통한 재귀적 알고리즘 복잡도 도출 방법

3 minutes to read

강의 정보
강의명: [집콕]인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고
교수: 성균관대학교 소프트웨어학과 허재필 교수님
사이트: http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/course/



이번 시간에는 삽입 정렬과 합병 정렬의 비교 분석을 통한 재귀적 알고리즘 복잡도 도출 방법에 대해 배운다.


삽입 정렬, Insertion Sort

Insertiong Sort란, 정렬된 array가 주어졌을 때, 새로운 element를 정렬 규칙이 깨지지 않도록 올바른 위치를 찾아서 삽입해주는 알고리즘이다.


Sorting Problem

Sorting 문제는 다음과 같이 구성된다.

  • Input: A sequence of $n$ numbers $<a_1, a_2, …, a_n>$
  • Output: A permutation (reordering) of the input sequence, $<b_1, b_2, …, b_n>$, such that $b_1 ≤ b_2 ≤ … ≤ b_n$


Code

Swap 알고리즘을 사용하는 방식과 사용하지 않는 방식, 두 가지 방식으로 Insertion Sort Algorithm 코드를 작성해볼 수 있다.

Insertion Sort with Swap

template <typename Type>
void Insertion_Sort(Type *_array, int _n)
{
    for(int i=1; i<_n; i++)
    {
        for int j=i; j>0; j--)
        {
            if(_array[j-1] > _array[j])
                std::swap(_array[j-1], _array[j]);
            else
                break;
        }
    }
}

코드 설명:

image-20210826172800334


Complexity:

  • Swap Operation : $Θ(1)$
  • for Loop (j) : $O(1 + \sum_{j=0}^{i}{1}) = O(1+i) = O(i)$
  • for Loop (i) : $O(1 + \sum_{i=1}^{n}{i}) = O(1+\frac{n(n+1)}{2}) = O(n^2)$

결과적으로 Insertion Sort는 $O(n^2)$의 Time Complexity를 갖는다.


Insertion Sort without Swap

Swap Algorithm은 세 줄의 코드로 구성되어 있다.

Swap Algorithm:
	tmp = a;
	a = b;
	b = tmp;

이러한 Swap 알고리즘을 사용하지 않으면 보다 최적화된 알고리즘을 얻을 수 있다.

template <typename Type>
void Insertion_Sort_without_Swap(Type *_array, int _n)
{
    for(int i=1; i<_n; i++)
    {
        Type tmp = _array[i];
        for(int j=i; j>0; j--)
        {
            if(_array[j-1] > tmp) // 오름차순이 아닌 경우
                _array[j] = _array[j-1];
            else
            {
                _array[j] = tmp;
	            break;
            }
        }
        
        if(_array[0] > tmp)
            _array[0] = tmp;
    }
}

코드 설명:

image-20210826174751795


합병 정렬, Merge Sort

Merge Sort Algorithm은 divide and conquer 알고리즘이다.


Divide and Conquer 알고리즘

Divide and Conquer 알고리즘이란, 문제를 쪼개어 각각을 따로 처리한 다음 결과를 하나로 합치는 알고리즘을 말한다.

Merge Sort 알고리즘에서는, 주어진 하나의 array를 반으로 나누어 각각을 sort한 다음 merge operation을 통해 합쳐준다.


Merging Example

아래의 예시를 통해 Merging을 수행하는 방법에 대해 살펴보자.

image-20210826190803166

  1. 두 array의 포인터가 가리키는 index 값을 비교한다.
  2. 더 작은 값을 갖는 array의 값을 result array에 넣고, 해당 array의 포인터를 오른쪽으로 이동시킨다.
  3. 위 과정을 반복한다.


<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.4.1/css/bootstrap.min.css">
<script src="https://ajax.googleapis.com/ajax/libs/jquery/3.5.1/jquery.min.js"></script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.4.1/js/bootstrap.min.js"></script>

<button type="button" class="btn btn-info" data-toggle="collapse" data-target="#demo">Code Run</button>
<div id="demo" class="collapse">
  <iframe src="https://code.sololearn.com/ct5m9F874CWD" style="width:100%; heigth:100%; resize: vertical;"></iframe>
</div>


단점

Merging Algorithm은 in-place로 동작하지 않는다는 단점이 있다. 즉, 병합하기 전에 언제나 병합된 결과를 담는 array를 memory allocation해야한다.

in-place란?
새로운 메모리 없이 구동될 수 있는 알고리즘을 의미한다.
in-place가 아닌 알고리즘은, 언제나 memory allocation을 해야만 한다.


Code

image-20210826195102050

알고리즘은 대략 다음과 같다.

  1. list를 절반 정도씩 쪼개어 두 개로 나눈다.
  2. 두 sub lists에 대해 merge sort를 재귀적으로 호출한다(Recursively call).
  3. sorted lists 결과를 merge한다.


■ Problem: Recursively Call

이론상으로는 sub-list를 하나의 element가 남을 때 까지 재귀적으로 merge sort하여 합치는 것이 맞다. 하지만 이러한 방식은 function call에 의해 발생하는 overhead 문제가 있다. 따라서 실질적으로는 어떠한 threshold를 이용하여 threshold 이하의 element가 남을 때 다른 sorting algorithm(e.g., insertion sort)을 사용하기도 한다.


Merge Sort

template <typename Type>
void Merge_Sort(Type *_array, int _first, int _last)
{
    if(_last-_first <= NUM_THRESHOLD)
    {
        Insertion_Sort<Type>(_array, _first, _last);
    }
    else
    {
        int midpoint = (_first + _last)/2;
        
        Merge_Sort<Type>(_array, _first, midpoint);
		Merge_Sort<Type>(_array, midpoint, _last);
        Merge(_array, _first, midpoint, _last);
    }
}


■ Complexity

  • if절(_last-_first<=NUM_THRESHOLD) : $T(\text{NUM_THRESHOLD})=Θ(1)$
  • else절
    • int midpoint : $Θ(1)$
    • Merge_Sort() : $T(\frac{n-1}{2})$
    • Merge_Sort() : $T(\frac{n-1}{2})$
    • Merge() : $Θ(n)$

Merge Sort의 Time Complexity $T$는 아래와 같이 recursive하게 나타낼 수 있다.

\(T(n) = \begin{cases} Θ(1) & \text{if $n=1$}\\ 2T(\frac{n}{2})+Θ(n) & \text{if $n>1$} \end{cases}\) 위의 재귀적으로 표현된 Time Complexity는 recursion tree 기법을 이용하여 Asymptotic Analysis를 할 수 있다.


■ Recursion Tree

Recursion Tree를 이용하여 Asymptotic Analysis를 하는 방법은 다음과 같다.

  1. 위의 재귀적으로 표현된 Time Complexity를 아래와 같이 표현한다.

    \[T(n)= \begin{cases} c & \text{if $n=1$}\\ 2T(\frac{n}{2})+cn & \text{if $n>1$} \end{cases}\]

  2. 위의 표현식을 recursion tree로 표현한다.

    image-20210827011809452

  3. recursion tree의 모든 nodes의 합을 구한다. \(T(n)=cn·\log(n)+cn\)

결과적으로 Time Complexity가 $O(n^2)$인 Insertion Sort보다 $O(n\log(n))$인 Merge Sort 알고리즘이 더 효율적이다.


References

  1. [집콕]인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고-비선형 자료구조, K-MOOC: http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/courseware/1158909c057347478d7386a2b7e97214/e9d736660cad4f76bcb9a05974fe0bf2/1?activate_block_id=block-v1%3ASKKUk%2BSKKU_46%2B2021_T1%2Btype%40vertical%2Bblock%4052b62ff6da2147c9a8a65a6056681d91



참고