20_mergeSort
문제 🙋
정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
입력 🔜
인자 1 : arr
number타입을 요소로 갖는 배열arr[i]는 정수arr.length100,000 이하
출력 🔚
number타입을 요소로 갖는 배열을 리턴해야 합니다.- 배열의 요소는 오름차순으로 정렬되어야 합니다.
arr[i] <= arr[j] (i < j)
주의사항 ⚠️
- 병합 정렬을 구현해야 합니다.
arr.sort사용은 금지됩니다.- 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.
입출력 예시 ⌨️
let output = mergeSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]힌트 💡
-
병합 정렬은 표준 라이브러리에서 정렬을 구현할 때 퀵 정렬이나 힙 정렬의 대안으로 사용하는 최적화된 정렬 알고리즘입니다. 병합 정렬은 다음과 같은 알고리즘을 사용합니다.
- N의 길이를 가진 배열 리스트를 1의 길이를 가진 "부분 리스트"가 N개 모인 것으로 취급합니다.
- 인접한 부분 리스트들을 정렬하여 2의 길이를 가진 부분 리스트로 병합합니다.
- 2의 길이를 가진 인접한 부분 리스트들을 4의 길이를 가진 부분 리스트로 합칩니다.
- 하나의 정렬된 리스트가 될 때까지 위 과정을 반복합니다.
- N이 홀수라면, 첫 번째 병합 때 1의 길이를 가진 부분 리스트를 남깁니다.
-
병합 정렬은 두 가지 방식으로 구현 가능합니다. 재귀적 접근(위->아래) 그리고 반복적 접근(아래->위)
반복적 접근
1. 주어진 배열이 "정렬된" 부분 리스트로 나뉘어집니다.
[4,7,4,3,9,1,2] -> [[4],[7],[4],[3],[9],[1],[2]]
2. 인접한 부분 리스트 2개가 정렬된 부분 리스트로 병합됩니다.
[[4],[7],[4],[3],[9],[1],[2]] -> [[4,7],[3,4],[1,9],[2]]
2. 병합 과정 (반복) :
[[4,7],[3,4],[1,9],[2]] -> [[3,4,4,7], [1,2,9]]
2. 병합 과정 (반복) :
[[3,4,4,7], [1,2,9]] -> [[1,2,3,4,4,7,9]]
3. 마무리 : 정렬된 배열이 리턴됩니다.
[1,2,3,4,4,7,9]재귀적 접근
주어진 배열을 절반으로 나눕니다.
4, 7, 4, 3, 9, 1, 2 -> 4, 7, 4, 3, 9, 1, 2
두 배열이 재귀적으로 정렬됩니다.
4, 7, 4 -> 4, 4, 7 -> 1, 2, 3, 9
두 배열이 병합됩니다.
4, 7, 4, 3, 9, 1, 2 -> 1, 2, 3, 4, 4, 7, 9
2단계에서 나뉘어진 각각의 배열 4, 7, 4에 대해서도 1-3번의 과정이 재귀적으로 똑같이 진행됩니다.
주어진 배열을 절반으로 나눕니다.
4, 7, 4 -> 4, 7, 4
두 배열이 재귀적으로 정렬됩니다.
4 -> 4 -> 4, 7
두 배열이 병합됩니다.
4, 4, 7 -> 4, 4, 7
이 과정의 2단계에서 나뉘어진 4, 7에 대해서도 재귀가 호출됩니다.
4는 원소가 하나이기 때문에 정렬하지 않아도 되겠죠?
주어진 배열을 절반으로 나눕니다.
7, 4 -> 7, 4
두 배열이 재귀적으로 정렬됩니다.
7 -> 7 -> 4
두 배열이 병합됩니다.
7, 4 -> 4, 7
모든 재귀 호출이 완료되면 3단계에서 병합이 되기 때문에 최종적으로 정렬된 하나의 배열이 리턴됩니다.
Pseudo Code ✍️
arr.length < 2 => return arr
절반 값을 구하고 그 절반을 기초로 left arr right arr 구하기
정렬 함수를 새로 만들고 그 함수에 각각의 배열들을 넣어준다.Code 💻
const mergeSort = function (arr) {
// 쪼갠 배열에서 오름차순으로 정렬시켜줄 함수 merge 생성
const merge = (left, right) => {
const resultArr = [];
let leftIndex = 0;
let rightIndex = 0;
while(leftIndex < left.length && rightIndex < right.length) {
if(left[leftIndex] < right[rightIndex]){
resultArr.push(left[leftIndex]);
leftIndex++;
} else {
resultArr.push(right[rightIndex]);
rightIndex++;
}
}
// left, right 둘 중 하나의 배열의 숫자가 남고 while문이 끝날 수 있기 때문에
// 마지막으로 concat으로 뒤에 남은 큰 숫자들을 넣어준다.
// silce(Index)에서 배열의 마지막 Index라면 빈 배열을 넣게됨.
return resultArr.concat(left.slice(leftIndex), right.slice(rightIndex));
}
if(arr.length < 2) return arr;
let mid = Math.floor(arr.length/2);
let leftArr = arr.slice(0, mid);
let rightArr = arr.slice(mid);
// 기존배열을 쪼개고 쪼개는 과정(썸네일 참고)
return merge(mergeSort(leftArr), mergeSort(rightArr));
}