병합 정렬 javascript / merge sort

병합 정렬은 배열을 일정 크기로 분할한 다음 정렬하고 합치는 방식이다.

 

[8,7,6,5,4,3,2,1] 이렇게 숫자가 있다면

 

[8,7,6,5]   [4,3,2,1]

 

[8,7] [6,5]   [4,3] [2,1] 이렇게 나눈다.

 

그리고 나눠진 배열을 정렬한다.

[7,8]  [5,6]   [3,4]  [1,2]

 

 

앞에서부터 하나씩 비교하고 빼내서 결과를 만든다.

 

[7,8]  [5,6]   5가 더 작다. 5를 빼낸다.   [5]

[7,8]  [6]     6이 더 작다. 6을 빼낸다.   [5,6]

[7,8]   []      배열에 7,8을 넣는다.       [5,6,7,8]

 

이렇게 분할 된 두 배열을 합친다.

 

앞쪽의 5,6,7,8이 정렬되었다.

 

뒤쪽의 4,3,2,1도 마찬가지로 해본다.

 

 

[3,4]  [1,2]   1이 더 작다. 1을 빼낸다.    [1]

[3,4]  [2]     2가 더 작다. 2를 빼낸다.   [1,2]

[3,4]  []       배열에 [3,4]를 넣는다.  [1,2,3,4]

 

이제 2개의 배열이 생겼다.

[5,6,7,8]    [1,2,3,4]

 

두 배열도 비교해서 합친다.

 

[5,6,7,8]    [1,2,3,4]    1이 더 작다. 1을 빼낸다.   [1]

[5,6,7,8]    [2,3,4]      2가 더 작다. 2를 빼낸다.   [1,2]

[5,6,7,8]    [3,4]        3이 더 작다. 3을 빼낸다.   [1,2,3]

[5,6,7,8]    [4]           4가 더 작다. 4를 빼낸다.   [1,2,3,4]

[5,6,7,8]    []            [5,6,7,8]을 배열에 넣는다.  [1,2,3,4,5,6,7,8]

 

정렬이 완료되었다.

 

병합 정렬의 구현은 이렇다.

 

/**
 * 나눈 배열 합치면서 정렬하기
 * @param {Array} left
 * @param {Array} right
 */
const merge = (left, right) => {
  const 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;
}
/**
 * 재귀적으로 배열 나누기
 * @param {Array} arr
 */
const mergeSort = (arr) => {
  if (arr.length < 2) {
    return arr;
  }
  const pivot = arr.length / 2;
  const left = arr.slice(0, pivot);
  const right = arr.slice(pivot, arr.length);
  return merge(mergeSort(left), mergeSort(right));
}

왜 이렇게 작성했는지 하나씩 살펴본다.

 

먼저 재귀적으로 배열을 나누는 부분부터 보자.

 

들어온 배열의 길이가 2보다 작다면 더 나눌수 없으므로 배열을 리턴한다.

 if (arr.length < 2) {
    return arr;
  }

 

그 다음 배열을 반씩 나눈다.

 const pivot = arr.length / 2;
  const left = arr.slice(0, pivot);
  const right = arr.slice(pivot, arr.length);

이제 배열을 합치는 함수를 호출한다.

 

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

 

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

 

이렇게 하면 merge 이전에 mergeSort가 재귀적으로 호출된다.

arr.length 가 2보다 작을때까지 호출하면 가장 작게 나눠진 배열을 merge 에서 쓰게 된다.

 

코드를 아래와 같이 바꾸고 콘솔에 출력해봤다.

/**
 * 나눈 배열 합치면서 정렬하기
 * @param {Array} left
 * @param {Array} right
 */
const merge = (left, right) => {
  const result = [];
  console.log(`left ${left}`);
  console.log(`right ${right}`);
  // 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;
}
/**
 * 재귀적으로 배열 나누기
 * @param {Array} arr
 */
const mergeSort = (arr) => {
  if (arr.length < 2) {
    return arr;
  }
  const pivot = arr.length / 2;
  const left = arr.slice(0, pivot);
  const right = arr.slice(pivot, arr.length);
  return merge(mergeSort(left), mergeSort(right));
}

console.log를 적고 아래 부분을 주석처리 했다.

출력은 이렇다.

앞에서부터 하나씩 전달되고 있다.

 

전체 배열이 [8,7,6,5,4,3,2,1] 일때

 

left 8 , right 7

left 6 , right 5

left 4 , right 3

left 2 , right 1

 

이렇게 전달되고 있다.

이 배열을 하나씩 비교해서 result 에 담고 리턴한다.

left 8 , right 7 은 7,8 을 리턴한다.

/**
 * 나눈 배열 합치면서 정렬하기
 * @param {Array} left
 * @param {Array} right
 */
const merge = (left, right) => {
  const 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());
  console.log(`result ${result}`);
  return result;
}
/**
 * 재귀적으로 배열 나누기
 * @param {Array} arr
 */
const mergeSort = (arr) => {
  if (arr.length < 2) {
    console.log(arr);
    return arr;
  }
  const pivot = arr.length / 2;
  const left = arr.slice(0, pivot);
  const right = arr.slice(pivot, arr.length);
  return merge(mergeSort(left), mergeSort(right));
}

mergeSort([8, 7, 6, 5, 4, 3, 2, 1]);

이렇게 코드를 작성하고 출력해보면 하나씩 어떻게 출력되는지 알 수 있다.

[8] , [7] 을 가지고 7,8을 만든다.

6,5를 가지고 5,6 을 만든다.

그 다음엔 5,6,7,8이 된다.

3,4 / 1,2 정렬 후 합쳐서 1,2,3,4를 만든다.

그리고 1,2,3,4,5,6,7,8을 만든다.