[20221110] recursion으로 merge sort 구현

Merge Sort는 배열을 하나의 요소가 개별 배열이 될때까지 쪼개고, 쪼개진 배열 두개씩 값을 비교하여 merge sort하는 알고리즘이다.

[8, 7, 3, 2]

[8, 7] [3, 2]

[8] [7] [3] [2]

[7, 8] [2, 3]

[2, 3, 7 8]

 

아래 사이트를 참고하면 시각적인 이해를 돕는다.

https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

merge sort를 코드로 직접 구현하려면 기능을 두개로 나누고 재귀를 사용한다.

첫 번째는 두 array의 각 요소를 비교하여 정렬하며 병합하는 것.

두 번째는 하나의 array를 요소가 1개 이하일때까지 쪼갠 뒤 첫 번째 작성한 함수를 사용해 병합하는 것.

두 번째 기능을 달성하기 위해서는 recursion에 대한 이해가 있어야만 했다.

function merge(arr1, arr2) {
  let result = [];
  let i = 0;
  let j = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      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) {
  if (arr.length <= 1) return arr
  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

mergeSort([10, 1, 3, 14]);

 

솔직히 recursion은 이해하기가 쉽지 않다.

솔직히 스스로 해내지 못했다.

정답을 보고도 잘 이해가 가지 않았다.

그래서 직접 손으로 적어봤다.

 

손으로 전체 프로세스를 적어보니 이해가 간다.

컴퓨터는 메모리에 순서를 메겨 left와 right를 저장하고 (left(1), left(2)와 같은 식으로..) 역순으로 merge를 하는 것이다.

이렇게 직접 그려보니 컴퓨터의 프로세스가 조금은 이해되는 것 같다.

컴퓨터의 처리 방식을 이해하려면 앞으로도 많은 연습이 필요할 듯 하다.