[알고리즘] 병합 정렬 (merge sort)

 병합 정렬 (merge sort) 

1. 병합 정렬이란?

병합 정렬(merge sort)은 어떤 문제를 2개의 작은 문제로 분리해 각각 해결한 다음, 이걸 모아서 원래 문제를 해결하는 분할 정복 알고리즘 중 하나다.

 

 

병합 정렬 알고리즘은 다음 개념들을 바탕으로 진행된다.

• 분할(Divide) : 입력된 배열을 같은 크기의 부분 배열 2개로 분할한다.
• 정복(Conquer) : 부분 배열의 크기가 충분히 작지 않으면(리스트의 길이가 0 또는 1이 아니면) 다시 분할을 한다.
• 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 병합한다.

병합 정렬은 다음 단계들로 진행된다.

• 부분 배열의 요소들을 결합할 빈 배열이 필요하다.
• 부분 배열의 크기(length)가 1이 될 때까지 쪼개준다.
• 부분 배열의 0번째 인덱스 값을 비교해 더 작은 값을 빈 배열에 넣어준다.
• 이 과정을 반복하여 최종적으로 정렬된 배열을 만들어준다.

 

예시를 살펴보자.

1. [21, 10, 12, 20, 25, 13, 15, 22]를 크기가 1인 부분 배열로 쪼개준다.
2. [21], [10], [12], [20] 앞에 4개의 부분 배열의 경우, 1번째와 2번째 배열의 0번째 요소를 서로 비교하고 작은 것을 먼저 빈 배열에 넣어 [10, 21]로 만들어주고, [12]와 [20]도 같은 방식으로 [12, 20]으로 만들어준다.
3. [10, 21]과 [12, 20]의 경우 0번째 요소를 비교해 빈 배열에 10을 넣어 [10]을 만들어주면 [21]과 [12, 20]이 남는데, 다시 0번째 21과 12를 비교해 [10, 12]를 만들어주면 [21]과 [20]이 남는다. 이 과정을 반복해 [10, 12, 20, 21]을 만들어준다.
4. 이처럼 0번째 인덱스 값을 비교해 빈 배열에 넣어주는 과정을 반복하여 최종적으로 정렬된 배열을 만들어준다.

 

728x90

 

---

2. 병합 정렬 구현 코드

위와 같은 과정을 구현한 코드는 다음과 같다.

arr라는 정렬되지 않은 배열이 입력되었고, 이것을 부분 배열로 쪼개주는 함수 mergeSort와 부분 분열의 0번째 인덱스 값을 비교해주는 함수 merge로 구성되어져 있다.

function merge(left, right) {
  const result = [];

  while (left.length && right.length) {
    if (left[0] <= right[0]) {     // 0번째 요소끼리 비교
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;
}

// 정렬되지 않은 배열 arr를 요소 1개만 가진 배열이 될 때까지 쪼개기
function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const mid = Math.ceil(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid, arr.length));

  return merge(left, right);
}

 

---

위 코드를 좀 더 이해하기 쉽게 하기 위해 중간중간  console.log() 로 각각의 값들을 찍어보기로 했다.

 

const arr = [21, 10, 12, 20];

mergeSort(arr);


function merge(left, right) {
  const result = [];

  while (left.length && right.length) {
    if (left[0] <= right[0]) {     // 0번째 요소끼리 비교
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  console.log(`결과: ${result}`);
  return result;
}


// 정렬되지 않은 배열 arr를 요소 1개만 가진 배열이 될 때까지 쪼개기
function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const mid = Math.ceil(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  console.log(`왼쪽: ${left}`)
  const right = mergeSort(arr.slice(mid, arr.length));
  console.log(`오른쪽: ${right}`)

  return merge(left, right);
}

 

[21, 10, 12, 20]의 배열을 예시로 넣었을 때, 콘솔창 결과는 다음과 같았다.

 

일단 반으로 쪼개면 left는 [21, 10], right는 [12, 20]이 된다.

이걸 다시 재귀적으로 돌리기에 left가 [21], right가 [10]이 되고, 이것이 함수 merge()에 들어가서 result가 [10, 21]이 된다. 그래서 왼쪽에는 [10, 21]이 할당된다.

right도 마찬가지로 left에 [12], right에 [20]이 할당되고, 함수 merge()로 오른쪽에 [12, 20]이 할당된다.

마지막으로, left에 [10, 21], right에 [12, 20]이 merge() 함수에 들어가 인덱스 0번째 값이 비교되면서 result는 [10, 12, 20, 21]이 된다.

 

왼쪽: 21
오른쪽: 10
결과: 10,21
왼쪽: 10,21
왼쪽: 12
오른쪽: 20
결과: 12,20
오른쪽: 12,20
결과: 10,12,20,21

 

 

---

만약 배열의 요소가 홀수일 경우는 어떻게 될까?

[5, 4, 1, 3, 2]를 예시로 결과값을 출력해보았다.

 

일단 [5, 4, 1]와 [3, 2]로 나눠진다.

left는 홀수이기에 [5, 4]와 [1]로 나눈 뒤, [5, 4]를 정렬해 왼쪽에 할당해주고, 오른쪽 [1]과 비교해서 [1, 4, 5]로 정렬해준다.

right는 앞선 짝수 과정을 통해 [2, 3]이 할당된다.

마지막으로, left [1, 4, 5]와 right [2, 3]을 서로 비교해 [1, 2, 3, 4, 5]를 출력해준다.

왼쪽: 5
오른쪽: 4
결과: 4,5
왼쪽: 4,5
오른쪽: 1
결과: 1,4,5
왼쪽: 1,4,5
왼쪽: 3
오른쪽: 2
결과: 2,3
오른쪽: 2,3
결과: 1,2,3,4,5

 

반응형

 

---

3. 병합 정렬의 장단점

장점

1. 안정적인 정렬 방법
   - 입력된 데이터(배열)가 무엇이든 간에 정렬하는 데 걸리는 시간은 동일하다 (O(nlog₂n)로 동일)
2. 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
   - 제자리 정렬(in-place sorting)로 구현할 수 있다.
3. 따라서 크기가 큰 레코드를 정렬할 경우, 연결 리스트를 사용한다면 병합 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 알고리즘보다 효율적이다

 

단점

1. 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
   - 제자리 정렬(in-place sorting)이 아니다.
2. 레코드들의 크기가 큰 경우에는 이동 횟수가 많아지므로 시간적 낭비가 매우 크다.

 

---

</> 끊임없이 성장하기 위해 공부한 내용을 글로 작성하고 있습니다. 틀린 부분이나 추가해야 할 부분이 있다면 언제든 댓글로 남겨주세요❗️

 

---

References

 

• https://evan-moon.github.io/2018/10/13/sort-algorithm/
• https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html