Algorithm JS - 합병 정렬

jiny·2022년 9월 24일

JavaScript Algorithm

목록 보기

12/23

합병 정렬 & 합병 정렬의 특징

합병 정렬

하나의 리스트를 두 개의 균등한 크기로 분할 후 분할 된 부분 리스트를 정렬

두 개의 정렬 된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 법

합병 정렬의 특징

분할 정복 알고리즘 중 하나
=> 분할 정복 - 문제를 작은 2개의 문제로 분리 후 각각 해결하고 결과를 모아 원래의 문제를 해결하는 전략

안정 정렬 중 하나

재귀함수가 사용 됨

추가 적인 저장 공간이 필요하여 메모리 문제가 발생할 수도 있음

Big O

최악 시간 복잡도

O(Nlogn)

최선 시간 복잡도

O(Nlogn)

평균 시간 복잡도

O(Nlogn)

공간 복잡도

O(n)

알고리즘

한 배열에 대해 배열 길이의 절반을 pivot으로 잡음

pivot까지의 값들의 배열 = left, pivot보다 큰 값들의 배열 = right

배열의 요소가 1개가 될 때까지 계속 쪼갬

쪼개진 배열들(left, right)에 대해 left 첫번째 요소와 right 첫 번째 요소를 비교 하여 작은 값을 새로운 배열에 추가 => left, right의 길이가 0이 될 때까지 반복(이때, 값이 추가되면 기존 배열에 있던 추가된 값은 삭제 되어야 함)

반복하여 하나의 정렬된 배열을 생성

소스 코드

const arr = [8, 1, 2, 9, 4, 6, 5, 7];

function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] < right[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;
}

function mergeSort(array = arr) {
  if (array.length < 2) return array;
  const pivot = Math.floor(array.length / 2);
  const left = array.slice(0, pivot);
  const right = array.slice(pivot, array.length);
  return merge(mergeSort(left), mergeSort(right));
}

console.log(mergeSort(arr));

mergeSort(arr)에서 최대한 쪼개져서 merge를 통해 합쳐지는 걸 생각해보았다.

merge(mergeSort(left), mergeSort(right));

배열길이가 8인 경우 처음에 mergeSort(arr)의 return은 merge(mergeSort(left), mergeSort(right))이다.
merge안에 있는 mergeSort 함수는 left, right의 길이가 4이기 때문에 더 쪼개게 됨

merge(
  merge(mergeSort(left), mergeSort(right)),
  merge(mergeSort(left), mergeSort(right))
);

merge안 merge의 mergeSort 함수에 있는 left,right의 길이는 2이기 때문에 한번 더 쪼개 짐

merge(
  merge(
    merge(mergeSort(left), mergeSort(right)),
    merge(mergeSort(left), mergeSort(right))
  ),
  merge(
    merge(mergeSort(left), mergeSort(right)),
    merge(mergeSort(left), mergeSort(right))
  )
);