병합 정렬 알고리즘 | JavaScript 코딩 튜토리얼

소개

이 랩에서는 JavaScript 에서 병합 정렬 (Merge Sort) 알고리즘을 탐구해 보겠습니다. 병합 정렬은 효율적이고 실제로 널리 사용되는 분할 정복 (divide-and-conquer) 정렬 알고리즘입니다. 이 랩을 마치면 병합 정렬의 작동 방식과 자체 JavaScript 프로젝트에서 구현하는 방법에 대한 확실한 이해를 갖게 될 것입니다.

병합 정렬 (Merge Sort) 알고리즘

병합 정렬 알고리즘을 사용하여 코딩을 연습하려면 다음 단계를 따르세요.

터미널/SSH 를 열고 node를 입력합니다.
재귀 (recursion) 를 사용하여 숫자 배열을 정렬합니다.
배열의 length가 2 미만이면 배열을 반환합니다.
Math.floor()를 사용하여 배열의 중간 지점을 계산합니다.
Array.prototype.slice()를 사용하여 배열을 두 부분으로 나누고, 생성된 하위 배열에 대해 mergeSort()를 재귀적으로 호출합니다.
마지막으로 Array.from()과 Array.prototype.shift()를 사용하여 정렬된 두 하위 배열을 하나로 결합합니다.

다음은 코드입니다.

const mergeSort = (arr) => {
  if (arr.length < 2) return arr;
  const mid = Math.floor(arr.length / 2);
  const l = mergeSort(arr.slice(0, mid));
  const r = mergeSort(arr.slice(mid, arr.length));
  return Array.from({ length: l.length + r.length }, () => {
    if (!l.length) return r.shift();
    else if (!r.length) return l.shift();
    else return l[0] > r[0] ? r.shift() : l.shift();
  });
};

다음 예시로 시도해 보세요.

mergeSort([5, 1, 4, 2, 3]); // [1, 2, 3, 4, 5]

JavaScript 에서의 병합 정렬

소개

병합 정렬 (Merge Sort) 알고리즘

요약