[알고리즘] MergeSort

MergeSort

• 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다.
  
  • 분할 정복(divide and conquer) 방법
    
    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
    • 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
• 과정 설명
  
  1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
  2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
• 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 합병 정렬은 다음의 단계들로 이루어진다.
  
  • 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  • 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
  • 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
• 합병 정렬의 과정
  
  • 추가적인 리스트가 필요하다.
  • 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
  • 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다.

Mergesort 방식

Mergesort 알고리즘 구현 예제

• 배열에 27, 10, 12, 20, 25, 13, 15, 22이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
• 2개의 정렬된 리스트를 합병(merge)하는 과정
  
  1. 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮긴다.
  2. 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다.
  3. 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다.
  4. 새로운 리스트(sorted)를 원래의 리스트(list)로 옮긴다.

참고 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

Mergesort Typescript 구현 예제

  mergeSort(): number[] {
    const startTime = Date.now();
    const answer = this.divideAndMerge(this.arr);
    const endTime = Date.now();
    console.log(endTime - startTime, "ms");
    return answer;
  }

  private divideAndMerge(arr: number[]): number[] {
    if (arr.length <= 1) {
      return arr;
    }
    // 중간값 확인
    // 반올림 진행
    let mid = Math.round(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    return this.merge(this.divideAndMerge(left), this.divideAndMerge(right));
  }

  private merge(arrLeft: number[], arrRight: number[]): number[] {
    let result: number[] = [];
    let i: number = 0; // 정렬된 왼쪽 리스트에 대한 인덱스
    let j: number = 0; // 정렬된 오른쪽 리스트에 대한 인덱스

    // i 혹은 j가 각각의 최종 인덱스값까지 도달하면 멈추는 반복문
    while (i < arrLeft.length && j < arrRight.length) {
      // 왼쪽과 오른쪽의 값을 비교하여 Result에 넣습니다.
      // 왼쪽을 넣는다면 i를 증가, 오른쪽을 넣는다면 j를 증가
      if (arrLeft[i] < arrRight[j]) {
        result.push(arrLeft[i]);
        i++;
      } else {
        result.push(arrRight[j]);
        j++;
      }
    }
    // 다 끝나고 왼쪽 배열이 남은 경우
    while (i < arrLeft.length) {
      result.push(arrLeft[i]);
      i++;
    }
    // 오른쪽 배열이 남은 경우
    while (j < arrRight.length) {
      result.push(arrRight[j]);
      j++;
    }
    return result;
  }

Mergesort 알고리즘의 특징

• 장점
  
  • 안정적인 정렬 방법
    
    • 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)
  • 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
    
    • 제자리 정렬(in-place sorting)로 구현할 수 있다.
  • 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.
• 단점
  
  • 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
    
    • 제자리 정렬(in-place sorting)이 아니다.
  • 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

Mergesort의 시간복잡도 O(nlog₂n)

분할 단계

• 비교 연산과 이동 연산이 수행되지 않는다.

합병 단계

• 비교 횟수
  
  • 순환 호출의 깊이 (합병 단계의 수)
    
    • 레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k)했을 때, n=2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다. 이것을 일반화하면 n=2^k의 경우, k(k=log₂n)임을 알 수 있다.
    • k=log₂n
  • 각 합병 단계의 비교 연산
    
    • 크기 1인 부분 배열 2개를 합병하는 데는 최대 2번의 비교 연산이 필요하고, 부분 배열의 쌍이 4개이므로 24=8번의 비교 연산이 필요하다. 다음 단계에서는 크기 2인 부분 배열 2개를 합병하는 데 최대 4번의 비교 연산이 필요하고, 부분 배열의 쌍이 2개이므로 42=8번의 비교 연산이 필요하다. 마지막 단계에서는 크기 4인 부분 배열 2개를 합병하는 데는 최대 8번의 비교 연산이 필요하고, 부분 배열의 쌍이 1개이므로 8*1=8번의 비교 연산이 필요하다. 이것을 일반화하면 하나의 합병 단계에서는 최대 n번의 비교 연산을 수행함을 알 수 있다.
    • 최대 n번
  • 순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 비교 연산 = nlog₂n
• 이동 횟수
  
  • 순환 호출의 깊이 (합병 단계의 수)
    
    • k=log₂n
  • 각 합병 단계의 이동 연산
    
    • 임시 배열에 복사했다가 다시 가져와야 되므로 이동 연산은 총 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드의 이동이 2n번 발생한다.
  • 순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 이동 연산 = 2nlog₂n

참조

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog