3. 배열을 길이가 0 또는 1인 요소의 더 작은 배열로 분해한 다음, 새로 정렬된 배열을 빌드하는 방식으로 작동한다(분류 -> 합병).
동작 방법?
분할
정렬
배열 합병 소개
1. 병합 정렬을 구현하려면 먼저 정렬된 두 배열을 병합하는 기능을 구현하는 것이 유용하다.
2. 정렬된 두 배열이 주어지면, helper함수는 정렬된 두 입력 배열의 모든 요소로 구성된 새 배열을 생성해야 한다.
3. 이 기능은 O(n + m) 시간 및 O(n + m) 공간 복잡도에서 실행되어야 하며 전달된 파라미터를 수정해서는 안된다.
배열 합병 의사코드
1. 빈 배열을 만들고 각 입력 배열에서 가장 작은 값을 살펴본다.
2-1. 첫 번째 배열의 값이 두 번째 배열의 값보다 작으면 첫 번째 배열의 값을 결과에 밀어넣고 첫 번째 배열의 다음 값으로 이동한다. 2-2. 첫 번째 배열의 값이 두 번째 배열의 값보다 크면 두 번째 배열의 값을 결과에 밀어넣고 두 번째 배열의 다음 값으로 이동한다. 2-3. 한 배열이 소진되면 다른 배열의 나머지 값을 모두 밀어 넣는다.
// Merges two already sorted arrays
function merge(arr1, arr2){
let results = [];
let i = 0;
let j = 0;
while(i < arr1.length && j < arr2.length){
if(arr2[j] > arr1[i]){
results.push(arr1[i]);
i++;
} else {
results.push(arr2[j])
j++;
}
}
while(i < arr1.length) {
results.push(arr1[i])
i++;
}
while(j < arr2.length) {
results.push(arr2[j])
j++;
}
return results;
}
merge([100,200], [1,2,3,5,6])
합병 정렬 작성하기 1부
합병정렬(mergeSort) 의사코드
1. 배열이 비어 있거나 하나의 요소가 있을 때까지 배열을 반으로 나눈다.
2. 정렬된 배열이 더 작으면 배열의 전체 길이로 돌아갈 때까지 다른 정렬된 배열과 병합한다.
3. 배열이 다시 병합되면 병합된(및 정렬됨!) 배열을 반환한다.
합병 정렬 작성하기 2부
// Merge function from earlier
function merge(arr1, arr2){
// 위에 있음
}
// Recrusive Merge Sort
function mergeSort(arr){
if(arr.length <= 1) return arr;
let mid = Math.floor(arr.length/2);
let left = mergeSort(arr.slice(0,mid));
let right = mergeSort(arr.slice(mid));
return merge(left, right);
}
mergeSort([10,24,76,73]);
