반응형
문제
정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
입력
인자 1 : arr
- number 타입을 요소로 갖는 배열
- arr[i]는 정수
- arr.length 100,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] [3, 9, 1, 2] -> [1, 2, 3, 9]
- 두 배열이 병합됩니다.
2단계에서 나뉘어진 각각의 배열 [4, 7, 4] [3, 9, 1, 2]에 대해서도 1-3번의 과정이 재귀적으로 똑같이 진행됩니다.
- 주어진 배열을 절반으로 나눕니다.
[4, 7, 4] -> [4], [7, 4] - 두 배열이 재귀적으로 정렬됩니다.
[4] -> [4] [7, 4] -> [4, 7] - 두 배열이 병합됩니다.
[4], [4, 7] -> [4, 4, 7]
이 과정의 2단계에서 나뉘어진 [4, 7]에 대해서도 재귀가 호출됩니다.
[4]는 원소가 하나이기 때문에 정렬하지 않아도 되겠죠?
- 주어진 배열을 절반으로 나눕니다.
[7, 4] -> [7], [4] - 두 배열이 재귀적으로 정렬됩니다.
[7] -> [7] [4] -> [4] - 두 배열이 병합됩니다.
[7], [4] -> [4, 7]
모든 재귀 호출이 완료되면 3단계에서 병합이 되기 때문에 최종적으로 정렬된 하나의 배열이 리턴됩니다.
코드
const merge = function (left, right) {
let merged = [];
let leftIdx = 0, rightIdx = 0;
const size = left.length + right.length;
for (let i = 0; i < size; i++) {
if (leftIdx >= left.length) {
merged.push(right[rightIdx]);
rightIdx++;
} else if (rightIdx >= right.length || left[leftIdx] <= right[rightIdx]) {
merged.push(left[leftIdx]);
leftIdx++;
} else {
merged.push(right[rightIdx]);
rightIdx++;
}
}
return merged;
};
// left : mergeSort([4,7,4]), right : mergeSort([3,9,1,2])
// mergeSort([4,7,4]) =>
// left: mergeSort([4]) => [4]
// right : mergeSort([7,4])=> (left: mergeSort([7]) = [7], right : mergeSort([4]) =[4]) => [4,7]
// merged = merge([4],[4,7]) => [4,4,7]
// 최종 merged 값이 [4,4,7]이 되어 left = [4,4,7]이 됨
// mergeSort([3,9,1,2]) =>
// left: mergeSort([3,9]) => (left: mergeSort([3]) = [3], right : mergeSort([9]) =[9]) => [3,9]
// right : mergeSort([1,2])=> (left: mergeSort([1]) = [1], right : mergeSort([2]) =[2]) => [1,2]
// merged = merge([3,9],[1,2]) => [1,2,3,9]
// 최종 merged 값이 [1,2,3,9]이 되어 right = [1,2,3,9]이 됨
// 최종 merged = merge([4,4,7],[1,2,3,9]) => [1,2,3,4,4,7,9]
const mergeSort = function (arr) {
if (arr.length < 2) return arr;
const middle = parseInt(arr.length / 2);
const left = mergeSort(arr.slice(0, middle));
const right = mergeSort(arr.slice(middle));
// 재귀적 접근
const merged = merge(left, right);
return merged;
};
반응형
'코드스테이츠 SEB FE 41기 > 데일리 코딩(Hard)' 카테고리의 다른 글
[알고리즘/javascript]radixSort (0) | 2022.12.09 |
---|---|
[알고리즘/javascript]rotateMatrix (0) | 2022.12.06 |
[알고리즘/javascript]quickSort (0) | 2022.11.29 |
[알고리즘/javascript]insertionSort (0) | 2022.11.29 |
[알고리즘/javascript]powerSet (0) | 2022.11.23 |