merge-insertion sort, 혹은 Ford–Johnson algorithm 찬찬히 뜯어보기(1)

개요

1. 소개

2. merge sort

3. insertion sort

4. binary search (이진 탐색)

4. Tim sort 

 

1. 소개

꽤나 느린 알고리즘이고 특정 자료구조가 필요하다. (쌍으로 묶는... )

하지만 컴퓨터 과학적인 관점에서 꽤나 흥미롭다 : 숫자 비교를 아주 최적화해서 하지는 못하지만, 비교의 횟수를 최소로 만드는 면에서는 가장 널리 알려진 알고리즘이다.

 

The Art of Computer Programming, Volume 3 by Donald Knuth 에서 소개 되어있는 알고리즘이다. 

이해하는데 이틀 ~ 삼일 정도 걸렸고 여태 알고 있던 알고리즘으로만 사고방향이 흘러서 그 틀을 깨는데 가장 시간이 오래걸렸다...

 

그래도 찬찬히 뜯어본만큼 기록으로 남겨두고 싶어서 글을 적게 되었다. 

 

merge -insertion sort 라고 불리는 만큼, merge sort 와 insertion sort를 combine 한 방식이다.

 

 

 

 

각 알고리즘에 대해 먼저 알아보자. 

 

2. merge sort 

분할 정복 알고리즘이다. 

해야하는 수행을 작은 단위로 나누어서 작게 수행하다보면, 결국 전체 수행이 끝난다. 

보통 재귀를 사용하는 알고리즘이 분할 정복 알고리즘인데, 추상적으로 설명하면 다음과 같다. 

 

그림을 보면서 글을 따라오면 된다. 

전체 [27. 10. 12. 20. 25. 13. 15. 22] 배열의 숫자를 정렬하고 싶은 상황이다. 

먼저 이 리스트를 분할한다. 2등분씩 해나간다. [27 10 12 20] [25 13 15 22] 로 자른다. 그리고 그 다음은 [27 10] [12 20][25 13][15 22], .. 

 

그럼 마지막에는 [27] [10] [12] [20] [25] [13] [15] [22] 로 하나씩 모두 분할되고 만다. 

그러고나면 그때부터 'merge, 합병'을 시작한다. 

 

즉 merge 하는 과정이 곧 정렬하게 되는 과정이다. 

이 부분을 자세하고 눈 크게 뜨고 이해해보자.

 

[27] [10] [12] [20] [25] [13] [15] [22] 를 2 개씩 다시 붙이는데, 작은 것- 큰 것 순서대로 붙인다. 

 

[10 27] [12 20] [13 25] [15 22] 로 merge 된다. 

 

그 다음에는 4개씩 다시 붙인다. 역시 작은 것- 큰 것 순서대로 붙인다. 

[10 12 20 27] [13 15 22 25] 가 된다. 

 

마지막으로 8개 전부를 다시 붙인다. 

[10 12 13 15 20 22 25 27] 가 된다. 

작은 것 - 큰 것 순서대로 붙이는 과정에서 흔히 알고 있는, '버블 정렬'을 이용하면  이건 분할 정복을  이용하는 의미가 없다. 

무슨 말이냐면

[10 27] [12 20] [13 25] [15 22]  이 4개의 쌍을 2개씩 이어붙이려고 할 때 한 가지 중요한 사항은

각 [ ] 안의 수들이 이미 '정렬 되어있다는 거다. 

 

merge할 때 정렬하는 방식은 다음과 같다. 

이렇게 생각해보면 된다. 

두개의 화살표가 있다고 생각하면 편하다.

각 화살표 하나는 각 배열의 처음에 위치한다. 각 배열의 가장 작은 값을 가리키는 용도이다. 

두 화살표가 가리키는 두 값을 비교해서 더 작은 값을 S에 넣고, 고른 화살표는 한칸 옆으로 이동시킨다.

 

다음은  [10 27] [12 20] 두 배열을 merge하는 과정이다.  각 화살표가 두 배열의 처음인 10, 12를 가리키고 있다.

 

 

그리고 화살표가 각 배열중 하나라도 마지막에 다다랐으면, 아직 덜 담은 배열을 마저 넣어준다.

 

이렇게 두 배열이 정렬된 채로 merge 되었다!

 

이런 방식으로 4개짜리 배열을 옆 동네에도 만들어 주면, [13 15 22 25] 가 되어있을 것이다.

 

그 다음 8개 짜리 배열을 만들기 위해 위의 과정을 한번 더 반복해주면, 

[10 12 13 15 20 22 25] 가 된다!

 

 

이런 방식으로 하는게 merge sort다. 

시간 복잡도는 log(NlogN)이다. 

 

미리 말하자면 merge-insertion sort 는 merge sort 에서 배열을 분할하고나서, 병합할 때 정렬을 수행한다는 점에서 이름을 가져왔다.

 

 

3. insertion sort

이미 정렬된 배열을 대상으로 한 숫자 하나씩 정렬된 배열중 어느 곳에 위치할 지 찾는 과정이다. 

 

8, 5, 6, 2, 4 5개의 숫자를 정렬한다고 생각해보자 . 아래 그림을 참고하면서 글을 읽어보자. 

  (출처  :https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html)

 

8은 그대로 놔두고 5, 6, 2, 4, 5순으로 각 숫자가 위치할 지점을 찾는다. 

자신의 왼쪽 지점부터 자신이 삽입될 위치를 찾아나간다. 

 

1. 5는 8보다 작으므로 8 왼쪽에 위치한다. [5]

2. 6은 5보다 크므로 5보다 큰 곳에 위치시킨다.  [5 6]

3. 2는 5보다 작으므로 5 왼쪽에 위치시킨다. [2 5 6]

4. 4는 5보다 작으므로 5왼쪽에 위치시킨다. [2 4 5 6]

5. 5는 5와 같으므로 같은 위치에 위치시킨다. [2 4 5 5 6]

8은 결국 자기가 있어야 할 곳에 위치하게 된다.  [2 4 5 5 6 8]

 

 

시간 복잡도는 log(N^2)이다. 

 

모든 원소가 이미 정렬이 되어있는 경우, 외부 루프를 N-1번 도는 동안 비교 연산은 1번씩 수행된다.

따라서 best case에는 O(n) = n 이 된다.

 

모든 원소가 역순으로 정렬되어 있는 경우, 외부 루프를 N-1번 도는 동안 비교연산은 1, 2, ... , (N-1)번 수행된다. 

따라서 wort case 에는 O(n) = n^2 이 된다.

 

 merge-insertion sort 는 merge sort 처럼 배열을 분할하고나서, 병합할 때 정렬을 수행(merge sort 개념 )할 때 insertion sort처럼 원래 정렬되어있는 배열에 한 원소씩 제 위치에 삽입한다는 개념이 붙어서 insertion이라는 단어를 가져왔다. 

 

한가지 들 수 있는 의문점은, O(nlogn) 의 시간복잡도를 가진 merge sort 가 어째서 O(n^2) 의 시간복잡도를 가진 알고리즘인 insertion sort 을 사용하냐는 것이다. 

 

그 이유는, insertion sort 는 인접한 메모리와의 비교를 반복하기에 참조 지역성의 원리를 매우 잘 만족하기 때문이다.

- 참조 지역성의 원리 : CPU가 미래에 원하는 데이터를 예측하여 속도가 빠른 장치인 캐시 메모리에 담아 놓는데 이때의 예측률을 높이기 위하여 사용하는 원리로, 한번 참조한 데이터는 그 근처의 위치가 다시 재참조될 확률이 높다는 가정하에 캐싱한다는 것이다. CS 지식이 결합하여 탄생한 알고리즘인 것!!! 

즉, 병합 정렬 알고리즘이 정렬할 원소의 크기를 줄이기 때문에, 작은 원소 수에 대해 insertion sort 의 시간 복잡도가 더 작을 것이라고 기대하는 것이다. 

 

 

insertion sort 개념을 알아봤지만 사실 이진 탐색 개념이 더 중요하다. 

4.  이진탐색 binary search

 

first ~ last 범위의 정렬되어있는 배열 (정렬되어있다는 점이 중요하다) 이 있다.

여기에 value 라는 값을 삽입해서 여전히 정렬된 배열을 만들고 싶을 때, 그 삽입 위치를 어떻게 하면 찾을 수 있을까?

1. 

 첫번째로는  그냥 한칸씩 가면서 작은 값이 나오면 그냥 지나가고, value 보다 더 큰 값이 나오면 그 직전 위치에 넣으면 될 것이다. 

이 경우에는 한 원소의 위치를 찾는데 시간 복잡도가 O(N) 일 것이고,

전체 배열을 이런 식으로 한다고 생각하면 전체 정렬의 시간복잡도는 O(N^2) 일 것이다. 

(앞서 설명한 삽입 정렬도 이것과 비슷하다.)

 

2. 

두번쨰로는 이미 배열이 정렬되어있다는 점을 이용할 수 있다. 중간 값을 바로 알아낼 수 있으면, 그 중간 값을 살펴서 value가 중간값보다 크면 중간~ last 범위로 value의 위치 탐색 범위를 좁힐 수 있다.

아래 그림을 보면 파란색으로 칠한 부분이 탐색 범위인데, 절반씩 줄여나가는 것이 보인다.

그림에서는 24를 찾지 못해서 didn't search를 내뱉었지만, 마지막 mid 위치가 25인 걸 보면 알 수 있듯, 정렬할 떄 삽입 위치를 알아내는데에도 사용되는 것이 이진탐색이다. 

 

 

이렇게 한다면 한 원소의 위치를 찾는데 시간 복잡도는 (log2(N)) 일 것이고,

전체 배열을 이런 식으로 한다고 생각하면 전체 정렬의 시간복잡도는 O(N(log2(N))) 일 것이다. 

 

 

 

 

 

 

 merge-insertion sort 는 merge sort 처럼 배열을 분할하고나서, 병합할 때 정렬을 수행(merge sort 개념 )할 때 insertion sort처럼 원래 정렬되어있는 배열에 한 원소씩 제 위치에 삽입하는데, 그때 삽입 방식은 binary search를 사용한다. 

 

이름이랑은 딴판으로 시간복잡도에 가장 큰 영향을 미치고, 핵심적인 사항이 있는 게 binary search 이다. 

4. 코드

그래서 merge sort 와 insertion sort, binary search 의 구현된 코드는 다음과 같다. (C++)

 

merge sort

std::vector <long long> origin;
void  Merge(vector<long long> &arr, int low, int high, int depth){
    int mid = low + (high - low)/2;
    int n1 = mid - low + 1;
    int n2 = high - mid;

    vector<long long> leftArr(n1);
    vector<long long> rightArr(n2);
    //low ~ mid 까지의 배열과 mid + 1~ high 까지의 배열을 차례로 조합해서 정렬한다. 
    for(int i = 0; i < n1; i++)
        leftArr[i] = arr[low + i];
    for(int i = 0; i < n2; i++)
        rightArr[i] = arr[mid + 1 + i];
    int i = 0;
    int j = 0;
    int k = low;

    while(i < n1 && j < n2){
        if(leftArr[i] <= rightArr[j]){
            arr[k] = leftArr[i];
            i++;
        }
        else{
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    while(i < n1){
        arr[k++] = leftArr[i++];
    }
    while(j < n2){
        arr[k++] = rightArr[j++];
    }

}

void mergeSort(vector<int> &arr, int low, int high, int depth){
    // std::cout << "mergesort " << low << " " << high << "\n";
    if(low < high){
        int mid = low + (high - low)/2;
        mergeSort(arr, low, mid, depth +1);
        mergeSort(arr, mid +1, high, depth + 1);
        Merge(arr, low, high, depth + 1);
    }
  
}

 

insertion sort  

의사코드

자신의 왼쪽부터 뒤로 가면서 자신의 위치를 찾되, 자기가 삽입될 후보의 위치를 비워두면서, 즉 배열 내용을 뒤로 밀어내는 수행도 한다.

insertion_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다.
    for i <- 2 to N {
        loc = i - 1;
        newItem = A[i];

        # 이 지점에서 A[1..i-1]은 이미 정렬되어 있는 상태
        while (1 <= loc and newItem < A[loc]) {
            A[loc + 1] <- A[loc];
            loc--;
        }
        if (loc + 1 != i) then A[loc + 1] = newItem;
    }
}

 

 

binary search

int BinarySearch(int arr[], int target) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while(low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

재귀버전

int BinarySearchRecursive(int arr[], int target, int low, int high) {
    if (low > high)
        return -1;

    int mid = (low + high) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return BinarySearchRecursive(arr, target, low, mid-1);
    else
        return BinarySearchRecursive(arr, target, mid+1, high);
}

 

 

각 알고리즘에 대해서 이해했다면, 이 알고리즘들의 개념을 섞은 알고리즘을 알아볼 차례다.

미리 말했지만 이게 전부이기는 하다: 

 merge-insertion sort 는 merge sort 처럼 배열을 분할하고나서, 병합할 때 정렬을 수행(merge sort 개념 )하는데,  insertion sort처럼 원래 정렬되어있는 한 배열에 한 원소씩 제 위치에 삽입한다. 그때 삽입 방식은 binary search를 사용한다. 

 

 

 

4. Tim sort

 

두번째로 알아야 하는 사실은, merge sort 와 insertion sort 를 하이브리드 식으로 정렬하는 알고리즘이 이 알고리즘 뿐만이 아니라는 것이다.  python의 sort 나 java의 Arrays.sort() 에서 사용되는 Timsort 알고리즘도 존재한다 . 

 

Ford-Johnson 알고리즘 (Merge Insertion Sort)

• 목적: 주로 비교 기반 정렬 문제에 사용된다.  이 알고리즘의 목적은 주어진 데이터 세트를 가능한 한 적은 비교 횟수로 정렬하는 것이다. 
• 작동 방식: Ford-Johnson 알고리즘은 병합 삽입 정렬로도 알려져 있으며, 데이터를 반으로 나누고 각 부분을 재귀적으로 정렬한 다음, 병합하는 과정을 거친다. 이 알고리즘은 특히 작은 데이터 세트에 효율적이며, 최악의 경우 비교 횟수를 최소화한다. 
• 특징: 이 알고리즘은 비교적 복잡하며, 구현이 어려운 편이다.  그러나 이론적으로 최적의 비교 횟수를 제공한다. 

Timsort

• 목적: Timsort는 실제 세계 데이터의 정렬에 최적화되어 있으며, Python의 sort() 메서드와 Java의 Arrays.sort() 메서드에 사용된다. 
• 작동 방식: Timsort는 병합 정렬과 삽입 정렬의 하이브리드이다. 이 알고리즘은 데이터를 생성된 작은 순서대로 분할한 다음, 이러한 조각들을 병합하여 전체를 정렬한다.  (재귀적으로 일정한 크기로 나누어가다가, 특정 크기가 되면 삽입 정렬을 사용해서 크기를 늘린다. 더 자세한 내용은 https://d2.naver.com/helloworld/0315536 참고! .)
• 특징: Timsort는 안정적인 정렬 알고리즘으로, 최악의 시나리오에서도 효율적인 성능을 보인다. 실제 세계의 데이터에서 우수한 성능을 발휘하도록 설계되었다. 

차이점

• 사용 사례: Ford-Johnson 알고리즘은 이론적 최소 비교 횟수를 목표로 하는 반면, Timsort는 실제 세계 데이터의 정렬에 최적화되어 있다. 
• 알고리즘 유형: Ford-Johnson은 비교 최소화에 중점을 둔 병합 삽입 정렬이며, Timsort는 실용적인 성능을 위한 병합 정렬과 삽입 정렬의 조합이다. 
• 성능: Timsort는 다양한 데이터 유형과 크기에 대해 뛰어난 성능을 보이며, Ford-Johnson은 작은 데이터 세트에서 이론적으로 최적의 비교 횟수를 달성한다. 
• 복잡성과 구현: Timsort는 실제 사용에 적합하도록 설계되었으며, Ford-Johnson 알고리즘은 구현이 더 복잡한 편이다. 

 

다음 게시물에서 merge- insertion sort에 대해 진짜로 알아보자.

 

 

 

 

 

https://ebang.tistory.com/104

merge-insertion sort, 혹은 Ford–Johnson algorithm 찬찬히 뜯어보기(2)