(JS) Merge Sort(병합 정렬) 구현하기
sorting 알고리즘 중 병합 정렬에 대해서 알아보자.
병합 정렬은 크게 두 가지 함수로 이루어져 있다.
- function merge(left, right): 이미 소팅된 배열 left, right로 받아서 하나로 합치는 순수한 함수
- function mergeSort(arr) : 배열을 반으로 쪼개서 merge 함수에게 left, right 인자를 넘겨주는 함수
이때, merge 함수는 순수한 함수이고, mergeSort는 재귀로 함수를 콜한다는 것을 인지해야 한다.
merge function
merge 함수는 이미 정렬된 left(배열), right(배열)을 인자로 받아서 하나로 합치는 기능이다.
const merge = function (left, right) // 정렬된 왼쪽과 오른쪽 배열을 받아서 하나로 합치는 순수한 함수
// left, rights는 이미 sorted
const result = [];
while (left.length !== 0 && right.length !== 0) {
left[0] <= right[0] ? result.push(left.shift()) : result.push(right.shift())
}
return [...reulst, ...left, ...right]; // 아래 세 줄의 코드와 같은 역할
// if (left.length === 0) result.push(...right);
// if (right.length === 0) result.push(...left);
// return results;
}
mergeSort function
const mergeSort = function(array) {
// ending condition: length === 1 인 배열이 들어올 때, 정렬이 끝난 것.
if (array.length === 1) return array;
// 2로 나누고 내림을 해야
// length 가 2일 때도 안전하게 배열을 slice할 수 있다.
const middleIndex = Math.floor(array.length / 2);
const left = array.slice(0, middleIndex);
const right = array.slice(middleIndex);
// 재귀로 계속해서 반으로 나누며 length가 1이 될때까지 쪼개고,
// 거꾸로 올라오면서 순수한 함수인 merge에 인자로 넣어서 다시 병합되어서 최종값을 리턴한다.
return merge(mergeSort(left), mergeSort(right));
}
Author And Source
이 문제에 관하여((JS) Merge Sort(병합 정렬) 구현하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunsungyang-omc/JS-Merge-Sort병합-정렬-구현하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)