[Algorithm] 분할 정복 / 병합 정렬 알고리즘

분할 정복 (Devide & Conquer)

---

개념

분할 정복은 “큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식"이다. 미국 수학자 폰노이만이 1945년에 개발한 알고리즘이다. 퀵소트, 병합 정렬이 분할 정복 방법을 통해 구현한다.

예전엔 테이프를 이용해 데이터를 저장했다. 테이프 드라이브에 저장된 데이터는 항상 처음부터 순차적으로 읽어야 하기 때문에 데이터를 정렬하기 어려웠다. 이런 테이프 드라이브의 문제점을 극복하기 위해 병합 정렬 알고리즘이 탄생했다.

 

1. 분할 : 문제를 더 이상 분할할 수 없을 때까지 동일 유형의 여러 하위 문제로 나눈다
2. 정복 : 가장 작은 단위의 하위 문제를 해결하며 정복한다
3. 조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다

 

예시

분할 정복은 구조는 동일하지만 더 작은 문제를 해결하는 방식이 반복되는 재귀라고 볼 수 있다. 5의 계승(5!)을 재귀로 계산하는 factorial 함수가 전형적인 분할 정복의 예다. 5의 계승은 5 × 4 × 3 × 2 × 1의 결과이므로 5부터 -1씩 문제를 쪼깬 후(분할), 가장 작은 단위의 하위 문제인 2 × 1 부터 문제를 해결하며(정복/조합) 결과를 도출한다.

 

• $5 \times (4 \times 3 \times 2 \times 1) = 5 \times \text{fact}(5-1) = (5 \times 24)$
• $4 \times (3 \times 2 \times 1) = 4 \times \text{fact}(4-1) = (4 \times 6)$
• $3 \times (2 \times 1) = 3 \times \text{fact}(3-1) = (3 \times 2)$
• $2 \times 1 = 2 \times \text{fact}(2-1) = (2 \times 1)$
• $1\,\text{(Base Case)}$

 

function fac(n) {
  // Base Case 재귀가 멈추는 조건
  if (n === 1) return 1;
  
  // Recursive Case
  return n * fac(n - 1);
}

fac(5); // 120

 

병합 정렬

---

알고리즘 개념

➊, ➋ 같은 원형 번호는 진행 순서 / 파란색 블록은 주어진 데이터들이 정렬된 상태

병합 정렬은 1개 배열을 ➊2개의 작은 배열로 분할하여 ➋각 배열을 정렬(정복)한 후 ➌다시 병합(결합)하는 과정을 반복하며 정렬하는 알고리즘이다.

 

1. 분할 : 입력 받은 배열을 동일 길이의 2개 배열로 분할
2. 정복 : 분할한 배열 정렬. 분할한 배열 길이가 2 이상이면 재귀 호출로 분할 정복 다시 적용
3. 결합 : 정렬한 2개의 배열을 하나의 배열에 병합

 

구현

💡 병합 정렬 구현은 크게 분할 단계 / 병합 단계로 나눌 수 있다

 

유틸 함수

const swap = (arr, a, b) => {
  /* const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp; */
  [arr[a], arr[b]] = [arr[b], arr[a]];
};

const Compare = { LESS_THAN: -1, BIGGER_THAN: 1 };

const defaultCompare = (a, b) => {
  if (a === b) return 0;
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
};

 

• swap : 배열과 a, b 인덱스를 인자로 받아 배열[a], 배열[b] 요소 순서를 바꾸는 함수
• Compare : 값 비교시 사용하는 상수.
• defaultCompare : a, b 값을 인자로 받아 어느 값이 더 큰지 비교하는 함수

 

병합

left, right 2개의 정렬된 리스트(배열)를 받아 병합하는 함수. 두 리스트의 요소를 0번 인덱스부터 비교해서 더 작은 값을 result 배열에 추가한다. left 혹은 right의 모든 요소를 result 배열에 추가했다면, 남은 요소를 result 배열에 추가한 후 종료한다.

const merge = (left, right, compare) => {
  let i = 0; // left 리스트 인덱스
  let j = 0; // right 리스트 인덱스
  const result = [];
  // left 혹은 right의 모든 요소가 result 배열에 추가될 때까지 반복
  while (i < left.length && j < right.length) {
    const isLeft = compare(left[i], right[j]) === Compare.LESS_THAN;
    result.push(isLeft ? left[i++] : right[j++]);
  }
  // 남은 요소를 result 배열에 추가
  return result.concat(i < left.length ? left.slice(i) : right.slice(j));
};

 

merge 함수를 통해 이미 “정렬”된 두 분할 배열을 병합하는 과정

 

분할

배열 길이가 1이 될때까지 절반씩(left, right) 분할한 후, merge 함수를 통해 분할한 배열을 오름차순(작은 숫자부터)으로 정렬하면서 병합하는 과정을 반복하는 함수.

const mergeSort = (arr, compare = defaultCompare) => {
  if (arr.length > 1) {
    // 배열 길이가 1이 될때까지 배열 분할
    const { length } = arr;
    const middle = Math.floor(length / 2); // [분할] | [5, 4, 3, 2, 1] -> middle: 2, ...
    const left = mergeSort(arr.slice(0, middle)); // [정복] | [5, 4], ...
    const right = mergeSort(arr.slice(middle, length)); // [정복] | [3, 2, 1], ...
    arr = merge(left, right, compare); // [결합]
  }
  return arr;
};

[21, 10, 12, 20, 25, 13, 15, 22] 배열을 병합 정렬하는 과정

분할 / 정복 ▼

f([21, 10, 12, 20, 25, 13, 15, 22])
===================================
middle = 4
⑴ left = f([21, 10, 12, 20]) | [L-1] -> [10, 12, 20, 21]
⑾ right = f([25, 13, 15, 22]) | [R-4] -> [13, 15, 22, 25]
㉑ arr = merge([10, 12, 20, 21], [13, 15, 22, 25]) | [M-7] -> [10, 12, 13, 15, 20, 21, 22, 25]
---------------------------------------
return [10, 12, 13, 15, 20, 21, 22, 25]

[L-1] f([21, 10, 12, 20])
=========================
middle = 2
⑵ left = f([21, 10]) | [L-2] -> [10, 21]
⑹ right = f([12, 20]) | [R-2] -> [12, 20]
⑽ arr = merge([10, 21], [12, 20]) | [M-3] -> [10, 12, 20, 21]
-----------------------
return [10, 12, 20, 21]

[L-2] f([21, 10])
=================
middle = 1
⑶ left = f([21]) -> [L-3] -> [21]
⑷ right = f([10]) -> [R-1] -> [10]
⑸ arr = merge([21], [10]) | [M-1] -> [10, 21]
---------------
return [10, 21]

[R-2] f([12, 20])
=================
middle = 1
⑺ left = f([12]) -> [L-4] -> [12]
⑻ right = f([20]) -> [R-3] -> [20]
⑼ arr = merge([12], [20]) | [M-2] -> [12, 20]
---------------
return [12, 20]

[R-4] f([25, 13, 15, 22])
=========================
middle = 2
⑿ left = f([25, 13]) | [L-5] -> [13, 25]
⒃ right = f([15, 22]) | [R-6] -> [15, 22]
⒇ arr = merge([13, 25], [15, 22]) | [M-6] -> [13, 15, 22, 25]
-----------------------
return [13, 15, 22, 25]

[L-5] f([25, 13])
=================
middle = 1
⒀ left = f([25]) -> [L-6] -> [25]
⒁ right = f([13]) -> [R-5] -> [13]
⒂ arr = merge([25], [13]) | [M-4] -> [13, 25]
---------------
return [13, 25]

[R-6] f([15, 22])
=================
middle = 1
⒄ left = f([15]) -> [L-7] -> [15]
⒅ right = f([22]) -> [R-7] -> [22]
⒆ arr = merge([15], [22]) -> [M-5] -> [15, 22]
---------------
return [15, 22]

 

병합 ▼

[M-1] merge([21], [10])
=======================
i = 0 / j = 0 -> 21 vs 10 -> [10] | i++
---------------
return [10, 21]

[M-2] merge([12], [20])
=======================
i = 0 / j = 0 -> 12 vs 20 -> [12] | i++
---------------
return [12, 20]

[M-3] merge([10, 21], [12, 20])
===============================
i = 0 / j = 0 -> 10 vs 12 -> [10] | i++
i = 1 / j = 0 -> 21 vs 12 -> [10, 12] | j++
i = 1 / j = 1 -> 21 vs 20 -> [10, 12, 20] | j++
-----------------------
return [10, 12, 20, 21]

[M-4] merge([25], [13])
=======================
i = 0 / j = 0 -> 25 vs 13 -> [13] | j++
---------------
return [13, 25]

[M-5] merge([15], [22])
=======================
i = 0 / j = 0 -> 15 vs 22 -> [15] | i++
---------------
return [15, 22]

[M-6] merge([13, 25], [15, 22])
===============================
i = 0 / j = 0 -> 13 vs 15 -> [13] | i++
i = 1 / j = 0 -> 25 vs 15 -> [13, 15] | j++
i = 1 / j = 1 -> 25 vs 22 -> [13, 15, 22] | j++
-----------------------
return [13, 15, 22, 25]

[M-7] merge([10, 12, 20, 21], [13, 15, 22, 25])
===============================================
i = 0 / j = 0 -> 10 vs 13 -> [10] | i++
i = 1 / j = 0 -> 12 vs 13 -> [10, 12] | i++
i = 2 / j = 0 -> 20 vs 13 -> [10, 12, 13] | j++
i = 2 / j = 1 -> 20 vs 15 -> [10, 12, 13, 15] | j++
i = 2 / j = 2 -> 20 vs 22 -> [10, 12, 13, 15, 20] | i++
i = 3 / j = 2 -> 21 vs 22 -> [10, 12, 13, 15, 20, 21] | i++
---------------------------------------
return [10, 12, 13, 15, 20, 21, 22, 25]

 

로그(Logarithm) 참고 내용

시간 복잡도에서 로그는 밑(base)을 표기하지 않지만, 밑이 2인 로그라고 생각하면 된다(log₂N).

 

• 로그는 지수(exponent)의 정반대 개념. 2를 몇 번 거듭제곱해야 32가 나오는지 계산하는게 지수, 32는 2를 몇 번 나눠야 1이 나오는지 계산하는게 로그. 참고로 로그는 지수 방정식으로 바꿔서 계산하면 편함(logₐ(b) → a를 몇 번 제곱해야 b가 나올지 계산해본다).
  • 지수 : 2ⁿ = 32 → 32는 2를 5번 거듭제곱해야 나오므로 n = 5
  • 로그 : log₂(32) = n → 32는 2를 5번 나눠야 1이 나오므로 n = 5
• 즉, O(logN)은 데이터 원소가 N개 있을 때 알고리즘이 log₂N 단계가 걸린다는 의미. 요소가 8개라면 log₂8 = 3 이므로 O(logN) 알고리즘은 3단계가 필요한 것으로 해석할 수 있다.

 

시간 복잡도

병합 정렬은 크게 분할 단계와 병합 단계로 나눌 수 있다. 분할 단계에선 비교 / 이동 연산(임시 배열에 복사했다가 다시 가져오는 것)을 하지 않으므로 시간 복잡도에 포함되지 않는다.

 

• Worst Case(정렬이 안됐을 때) : O(nlog₂n)
• Best Case(이미 정렬됐을 때) : O(nlog₂n)

 

병합 단계의 수 (재귀 호출의 깊이)

이미지 및 설명 출처 - gmlwjd9405

• 레코드의 개수 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

$k = log₂n$ (데이터 길이 n이 8이라고 가정, 8은 2를 3번 제곱해야 나오므로 재귀 호출의 깊이 k는 3)

 

병합 정렬 및 퀵 정렬은 데이터 길이가 1이 될때까지 절반씩 분할한다. 데이터 길이가 8이라면 4(8/2) → 2(4/2) → 1(2/2) 분할 과정을 거치므로 깊이는 3이 된다. [21, 10, 12, 20, 25, 13, 15, 22] 배열을 예를 들어보면…

 

• 1 depth : 8 / 2 = 4 → n / 2 크기의 부분 배열 1쌍 비교 (부분 배열 개수 2개)
  • ( [21, 10, 12, 20] — L
  • [25, 13, 15, 22] )① — R
• 2 depth : 4 / 2 = 2 → n / 4 크기의 부분 배열 2쌍 비교 (부분 배열 개수 4개)
  • ( [21, 10] [12, 20] )① — L
  • ( [25, 13] [15, 22] )② — R
• 3 depth : 2 / 2 = 1 → n / 8 크기의 부분 배열 4쌍 비교 (부분 배열 개수 8개)
  • ( [21] [10] )① ( [12] [20] )② — L
  • ( [25] [13] )③ ( [15] [22] )④ — R

 

병합 단계의 크기 비교 연산

각 병합 단계(재귀 호출의 깊이)마다 최대 n번(데이터 길이)의 비교 연산 수행을 수행한다.

 

아래는 [21, 10, 12, 20, 25, 13, 15, 22] 배열에 대한 예시.

 

• 3 depth : 길이가 1인(n/8) 부분 배열 4쌍 비교
  • 길이가 1인 부분 배열 2개(1쌍) 병합시 최대 2번(1×2)의 비교 연산 필요
  • 길이가 1인 부분 배열이 8개(4쌍)이므로 4(쌍)×2(연산)=8(번) 연산 필요
• 2 depth : 길이가 2인(n/4) 부분 배열 2쌍 비교
  • 길이가 2인 부분 배열 2개(1쌍) 병합시 최대 4번(2×2)의 비교 연산 필요
  • 길이가 2인 부분 배열이 4개(2쌍)이므로 2(쌍)×4(연산)=8(번) 연산 필요
• 1 depth : 길이가 4인(n/2) 부분 배열 1쌍 비교
  • 길이가 4인 부분 배열 2개(1쌍) 병합시 최대 8번(4×2)의 비교 연산 필요
  • 길이가 4인 부분 배열이 2개(1쌍)이므로 1(쌍)×8(연산)=8(번) 연산 필요

 

각 병합 단계(depth)마다 최대 n번의 비교 연산을 수행하므로 시간 복잡도는…
각 병합 단계의 비교 연산(n) × 병합 단계의 수(log₂n) = nlog₂n
데이터 길이가 8이라면 최대 24번의 작업 수행

 

장단점

Stable 정렬 : 중복 데이터는 순서를 바꾸지 않는 방식(Unstable 정렬은 중복 데이터도 순서 바꿈)
In-place 정렬 : 새로운 배열 생성 없이 기존 배열만 사용하거나, 충분히 무시할만한 저장 공간만 더 사용하는 정렬 방식(Not In-place 정렬은 요소 개수에 비례하는 저장공간을 더 사용함)

 

1. 장점
   • 최선 / 최악 모두 동일한 시간 소요(어떤 입력 데이터든 정렬 시간 동일 / 데이터 분포 영향 덜받음)
   • Stable 정렬 방식
2. 단점
   • In-place 알고리즘이 아니므로 추가 메모리 공간 필요
   • 데이터 양이 많아질 수록 이동 횟수 늘어남 → 문제 해결 시간 증가

 

레퍼런스

---

• [알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog
• Common Sorting Algorithms in JavaScript
• 第18章 排序算法 | JavaScript 数据结构与算法
• [JS/Sorting] 병합 정렬(Merge Sort)과 분할 정복 전략(Divide and Conquer) 개념에 대하여
• 로그란? (개념 이해하기) | 로그 | Khan Academy

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요