[Algorithm] 병합 정렬(Merge Sort) 구현하기 Node.js

병합 정렬(Merge Sort)이란?

 

병합정렬(Merge Sort)는 합병 정렬이라고도 부르며 안정 정렬에 속하는 알고리즘입니다. 분할 정복(Divide and Conquer) 알고리즘의 하나로 1945년 존 폰 노이만이 개발하였습니다. 즉, 하나의 문제를 2개의 작은 문제로 분할한 다음 해당 결과를 모아 전체 문제의 답을 구해나가는 방식을 차용합니다.

 

 

 

 

병합 정렬은 안정 정렬로 데이터 분포에 영향을 거의 받지 않고, 입력 데이터에 상관없이 동일한 시간복잡도(O(N log N)을 가집니다. 분할 단계에서는 비교연산과 이동 연산을 수행하지 않지만, 분할된 데이터들을 특정 조건에 맞춰 병합하는 과정에서 호출의 깊이 Log N 번과 입력 데이터의 길이 N을 곱한 O(N log N) 시간복잡도가 소요됩니다.

 

병합 정렬 구현

 

병합 정렬은 크게 분할과 합병 두 단계로 진행됩니다. 우선 입력된 데이터를 절반씩 쪼개면서 최소 단위까지 분할을 진행합니다. 분할이 완료 된 후 가장 마지막 레벨에서 쪼개진 데이터를 합병하게 되는데, 이 때 오름차순 정렬 기준을 사용하면서 두개의 데이터를 합치기 시작합니다.

 

 

 

데이터를 쪼갠 깊이(log N) 만큼 병합이 역순으로 이뤄지며 데이터 길이 만큼 연산되므로 시간복잡도가 N x Log N이 됩니다. 또한 병합 정렬은 안정정렬로 입력 데이터에 성능 영향을 받지 않으며, 최선, 최악, 평균 시간복잡도 모두 N Log N의 성능을 보이고 있습니다.

 

ⓐ 분할(Divide)

입력 데이터를 LEFT와 RIGHT로 쪼개는 재귀 함수를 구현합니다. 만약 시작점이 종료지점과 같거나 큰 경우 입력 데이터의 첫번째 요소를 반환합니다. 가장 마지막 단계까지 분할이 된 이후 부터 aux() 함수의 반환값인 merge() 함수가 작동하면서 병합되기 시작하고, 입력데이터의 루트 레벨까지 올라오게 됩니다. 

const mergeSort = (arr, comparator) =>{
  const aux = (start, end) => {
    
    if(start >= end) return [arr[start]];

    const mid = Math.floor((start+end)/2);
    const left = aux(start, mid);
    const right = aux(mid+1, end);
    
    return merge(left, right, comparator);
  }
  return aux(0, arr.length-1);
}

 

ⓑ 병합(Merge)

병합 단계에서는 새로운 배열을 담을 임시 배열이 필요합니다. 입력데이터의 길이 만큼 데이터 순회가 일어나고, LEFT의 index와 RIGHT의 index를 증가 시키면서 병합될 데이터를 정렬합니다.

디폴트 조건은 RIGHT를 먼저 추가하는 것이지만, LEFT의 요소가 RIGHT 요소보다 작은 경우 LEFT를 우선적으로 추가합니다. 즉 오름차순 정렬을 구현합니다. 

const merge = (left, right, comparator = (item) => item) => {
  let merged = [];
  let leftIdx = 0, rightIdx = 0;
  const size = left.length + right.length;

  for(let i=0; i<size; i++){
    if(leftIdx >= left.length){
      merged.push(right[rightIdx]);
      rightIdx++;
    }else if(
      rightIdx >= right.length ||
      comparator(left[leftIdx]) <= comparator(right[rightIdx])
    ){
      merged.push(left[leftIdx]);
      leftIdx++;
    }else{
      merged.push(right[rightIdx]);
      rightIdx++;
    }
  }
  return merged;
}

 

 

입출력 예시

// 입력 데이터
[5,2,7,4,4,6,1];

// 병합 과정
left : 5,
right : 2,


left : 7,
right : 4,


left : 2,5,
right : 4,7,


left : 4,
right : 6,


left : 4,6,
right : 1,


left : 2,4,5,7,
right : 1,4,6,
    
// 출력 데이터
[ 1, 2, 4, 4, 5, 6, 7 ]

 

 

 

[Algorithm] 백준 2580 스도쿠 Node.js

 

[Algorithm] 힙 정렬(Heap Sort) 구현하기 Node.js/Javascript

 

[Algorithm] Gossip Protocol 알고리즘 문제 Node.js