JS 노트(merge sort() 를 만들어보자)

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

// 분할부분

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

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

//정렬해서 합치는 부분

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;
}

// const array = prompt().split(" ").map(n => parseInt(n, 10));
const array = [1, 3, 5, 4, 8, 6, 7, 2]
console.log(array);
console.log(mergeSort(array))


mergeSort() 란 합병정렬 // 또는 정렬합병 똑같은말이다..

음 ..

첫 [1, 3, 5, 4, 8, 6, 7, 2] 이 배열을
반으로 나누고 나누고 나누고 더 이상 못나눌때까지 계속 나누고
그 다음에 하나하나로 나뉜 배열을 left 0번째와 right 0번째와 비교한뒤
shift 해주면서 숫자들을 작은 수부터 큰 수까지 정렬해준다.

처음 접해봤는데
꽤.. 로직은 단순한거 같은데
음.. 그래 그냥 단순한거 같은데 어렵다.

분할부분에서는 재귀함수를 다루고 있다.
재귀함수도 처음 접해봐서 이해하려고 노력했으나 시간이 좀 걸릴 것 같다.

지금 내가 이해 한 재귀함수는 

종료조건을 정해놓고 그 종료조건이 될 때 까지 돌리는 for문인데 그게 for문이 아니라 함수형이라는 것.

저기 위에 분할부분에서도 arr.length 가 1이 될 때까지 loop를 돈다.
즉 재귀함수라는 것!

이전 글에 포스팅 해놨으니 여러번 보면서 감을 익히면 좋을 것 같다.