[Algorithm] 합병 정렬

김진영·2022년 12월 6일
0

Algorithm

목록 보기
10/15
post-thumbnail

📋 합병 정렬 알고리즘

지금까지 배운 정렬 알고리즘(버블, 선택, 삽입 정렬)은 큰 규모에 맞지 않는 알고리즘이다.

우리가 이제부터 알아볼 빠른 알고리즘 집합은 시간 복잡도를 O(n^2)에서 O(n log n)으로 향상시킬 수 있는 알고리즘이다.

그중 합병 정렬(Merge Sort)에 대해 먼저 알아보자.

합병 정렬에 대해 간단히 얘기하자면 n개의 숫자들을 n/2개씩 2개의 부분문제로 분할하고, 각각의 부분 문제를 순환적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복)한다.

이를 분할 정복(Divide and conquer)이라고 한다.

이번에도 글로만 봐서는 이해하기 힘들 수 있으니 작동방식을 직접 살펴보자.


📌 1. 합병 정렬 작동 방식

이번엔 개인적으로 visualgo에서 확인하는 것 보다 위 사진이 더 이해가 잘 된다고 생각하여 사진으로 준비했다.


📌 2. 합병 정렬 구현

  function merge(arr1: number[], arr2: number[]) {
    let result = [];
    let i = 0;
    let j = 0;
    while (i < arr1.length && j < arr2.length) {
      if (arr2[j] > arr1[i]) {
        result.push(arr1[i]);
        i++;
      } else {
        result.push(arr2[j]);
        j++;
      }
    }
    while (i < arr1.length) {
      result.push(arr1[i]);
      i++;
    }
    while (j < arr2.length) {
      result.push(arr2[j]);
      j++;
    }
    return result;
  }

  function mergeSort(arr: number[]) {
    if (arr.length <= 1) return arr;
    let mid: number = Math.floor(arr.length / 2);
    let left: number[] = mergeSort(arr.slice(0, mid));
    let right: number[] = mergeSort(arr.slice(mid));
    return merge(left, right);
  }

  mergeSort([16, 23, 9, 25, 5, 48]); // [5, 9, 16, 23, 25, 48]

먼저 merge 함수를 작성했다.
숫자가 담긴 2개의 배열을 순서를 정렬하여 합치는 배열이다.

그 다음, mergeSort 함수를 작성했다.
mergeSort 함수는 재귀적으로 배열을 반으로 자르고 merge하여 정렬된 배열을 반환하는 함수이다.


📌 3. 합병 정렬의 시간 복잡도

합병정렬의 시간복잡도 빅오는 최적의 경우, 최악의 경우, 보통 모두 시간복잡도가 O(n log n)으로 동일하다.

간단한 예시를 한번 살펴보자.

8
44
2222
11111111

이렇게 배열의 길이가 8일 시, 총 3번 분할되는것을 알 수 있다.

때문에 log n번만큼 분할되고 각 분할마다 합병할 때 n번 비교하기때문에 총 O(n log n) 이 되는것이다.

0개의 댓글