병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

• 대표적인 divide and conquer(분할정복)알고리즘을 이용하여 구현한 정렬 알고리즘 입니다.
• 분할 : 해결하고자 하는 문제를 가장 작은 단위로 쪼개는 과정
• 정복 : 가장 작은 단위로 쪼개진 문제들을 해결하고 합치는 과정

구현 방법

• 정렬하고자 하는 배열을 단일 요소를 가진 배열이 될 때 까지 나눕니다.(분할)
• 단일 요소의 배열들을 상황에 맞게 합치면서 정렬합니다.(정복)

장점

• 불규칙한 정렬 상태여도 정렬되는 시간은 동일합니다.
• 안정 정렬에 속합니다.
• 다른 정렬들에 비해 빠른 정렬로 분류됩니다.

단점

• 임시의 배열이 필요하기 때문에 메모리 낭비를 하게 된다
• 배열의 크기가 큰 경우 이동 횟수가 많기때문에 시간적 낭비를 초래할 수 있다.

Code

function merge(leftArr, rightArr) {
  var result = [];
  var leftIndex = 0;
  var rightIndex = 0;

  while(leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if(leftArr[leftIndex] < rightArr[rightIndex]) {
      result.push(leftArr[leftIndex++]);
    } else {
      result.push(rightArr[rightIndex++]);
    }
  }

  var leftRemain = leftArr.slice(leftIndex);
  var rightRemain = rightArr.slice(rightIndex);

  return result.concat(leftRemain).concat(rightRemain)
}

function mergeSort(arr) {
  if(arr.length == 1) {
    return arr;
  }
  var midNum = Math.floor(arr.length/2);
  var leftArr = arr.slice(0, midNum);
  var rightArr = arr.slice(midNum);

  return merge(mergeSort(leftArr), mergeSort(rightArr))
}

console.log(mergeSort([6,1,23,4,2,3]))

설명

function merge(leftArr, rightArr) {
  var result = [];
  var leftIndex = 0;
  var rightIndex = 0;
  console.log("")
  console.log('정복 함수 실행')
  console.log('left', leftArr, 'right', rightArr)

  console.log("")
  console.log('왼쪽 배열 오른쪽 배열 값 비교후 정렬 하는 반복문 실행')
  while(leftIndex < leftArr.length && rightIndex < rightArr.length) {

    if(leftArr[leftIndex] < rightArr[rightIndex]) {
      console.log('result:', result, leftArr[leftIndex], '<', rightArr[rightIndex], '왼쪽 배열 요소 추가')
      result.push(leftArr[leftIndex++]);
    } else {
      console.log('result:', result, leftArr[leftIndex], '>', rightArr[rightIndex], '오른쪽 배열 요소 추가')
      result.push(rightArr[rightIndex++]);
    }
  }

  // slice(index) => index부터 끝까지 추출
  // (만약)
  // leftArr == [2,3,4]
  // leftArr.slice(3) 이면 []빈배열 추출됌
  var leftRemain = leftArr.slice(leftIndex);
  var rightRemain = rightArr.slice(rightIndex);

  console.log('')
  console.log('result, leftArr, rightArr 합치는 과정')
  console.log(result, leftRemain, rightRemain)
  console.log('결과물 : ', result.concat(leftRemain).concat(rightRemain))

  return result.concat(leftRemain).concat(rightRemain)
}

function mergeSort(arr) {
  if(arr.length == 1) {
    return arr;
  }
  var midNum = Math.floor(arr.length/2);
  var leftArr = arr.slice(0, midNum);
  var rightArr = arr.slice(midNum);
  console.log('분할 시작')
  console.log(leftArr, rightArr)
  return merge(mergeSort(leftArr), mergeSort(rightArr))
}

console.log(mergeSort([5,1,33,27,10,2]))

// 1. 첫번째 분할 시작
// [ 5, 1, 33 ] [ 27, 10, 2 ]

// (-------------------- 초기 배열의 왼쪽 부분 -------------------- )

// 분할 시작
// [ 5 ] [ 1, 33 ]
// 분할 시작
// [ 1 ] [ 33 ]
//
// 정복 함수 실행
// left [ 1 ] right [ 33 ]
//
// 왼쪽 배열 오른쪽 배열 값 비교후 정렬 하는 반복문 실행
// result: [] 1 < 33 왼쪽 배열 요소 추가
//
// result, leftArr, rightArr 합치는 과정
// [ 1 ] [] [ 33 ]
// 결과물 :  [ 1, 33 ]
//
// 정복 함수 실행
// left [ 5 ] right [ 1, 33 ]
//
// 왼쪽 배열 오른쪽 배열 값 비교후 정렬 하는 반복문 실행
// result: [] 5 > 1 오른쪽 배열 요소 추가
// result: [ 1 ] 5 < 33 왼쪽 배열 요소 추가
//
// result, leftArr, rightArr 합치는 과정
// [ 1, 5 ] [] [ 33 ]
// 결과물 :  [ 1, 5, 33 ]

// (---------------- 초기 배열의 오른쪽 부분 ----------------)
// 분할 시작
// [ 27 ] [ 10, 2 ]
// 분할 시작
// [ 10 ] [ 2 ]
//
// 정복 함수 실행
// left [ 10 ] right [ 2 ]
//
// 왼쪽 배열 오른쪽 배열 값 비교후 정렬 하는 반복문 실행
// result: [] 10 > 2 오른쪽 배열 요소 추가
//
// result, leftArr, rightArr 합치는 과정
// [ 2 ] [ 10 ] []
// 결과물 :  [ 2, 10 ]
//
// 정복 함수 실행
// left [ 27 ] right [ 2, 10 ]
//
// 왼쪽 배열 오른쪽 배열 값 비교후 정렬 하는 반복문 실행
// result: [] 27 > 2 오른쪽 배열 요소 추가
// result: [ 2 ] 27 > 10 오른쪽 배열 요소 추가
//
// result, leftArr, rightArr 합치는 과정
// [ 2, 10 ] [ 27 ] []
// 결과물 :  [ 2, 10, 27 ]
//

// (---------------- 초기 배열의 왼쪽, 오른쪽 부분 정복----------------)
// 정복 함수 실행
// left [ 1, 5, 33 ] right [ 2, 10, 27 ]
//
// 왼쪽 배열 오른쪽 배열 값 비교후 정렬 하는 반복문 실행
// result: [] 1 < 2 왼쪽 배열 요소 추가
// result: [ 1 ] 5 > 2 오른쪽 배열 요소 추가
// result: [ 1, 2 ] 5 < 10 왼쪽 배열 요소 추가
// result: [ 1, 2, 5 ] 33 > 10 오른쪽 배열 요소 추가
// result: [ 1, 2, 5, 10 ] 33 > 27 오른쪽 배열 요소 추가
//
// result, leftArr, rightArr 합치는 과정
// [ 1, 2, 5, 10, 27 ] [ 33 ] []
// 결과물 :  [ 1, 2, 5, 10, 27, 33 ]
// [ 1, 2, 5, 10, 27, 33 ]