자바스크립트(JavaScript)로 병합 정렬을 구현하고, 이를 테스트하는 방법을 설명하겠습니다. 이를 통해 분할 정복 알고리즘의 원리를 JavaScript에서 어떻게 구현하는지 살펴보겠습니다.
병합 정렬 (Merge Sort) in JavaScript
병합 정렬은 다음과 같은 단계로 이루어집니다:
- 배열을 반으로 나눕니다.
- 각 하위 배열을 재귀적으로 병합 정렬합니다.
- 정렬된 하위 배열들을 병합하여 최종 정렬된 배열을 만듭니다.
다음은 병합 정렬의 JavaScript 구현 예제와 이를 테스트하는 방법입니다:
javascript
코드 복사
// 병합 정렬 함수 function mergeSort(arr) { if (arr.length <= 1) { return arr; } const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); const right = mergeSort(arr.slice(mid)); return merge(left, right); } // 병합 함수 function merge(left, right) { let sortedArray = []; let i = 0, j = 0; while (i < left.length && j < right.length) { if (left[i] < right[j]) { sortedArray.push(left[i]); i++; } else { sortedArray.push(right[j]); j++; } } return sortedArray.concat(left.slice(i)).concat(right.slice(j)); } // 테스트 함수 function testMergeSort() { const testCases = [ { input: [38, 27, 43, 3, 9, 82, 10], expected: [3, 9, 10, 27, 38, 43, 82] }, { input: [5, 2, 9, 1, 5, 6], expected: [1, 2, 5, 5, 6, 9] }, { input: [0], expected: [0] }, { input: [], expected: [] } ]; testCases.forEach(({input, expected}, index) => { const result = mergeSort(input); console.log(`테스트 ${index + 1}:`, arraysEqual(result, expected) ? "통과" : "실패"); }); } // 배열 비교 함수 function arraysEqual(a, b) { if (a.length !== b.length) return false; for (let i = 0; i < a.length; i++) { if (a[i] !== b[i]) return false; } return true; } // 테스트 실행 testMergeSort();
설명
- mergeSort 함수:
- 배열의 길이가 1 이하인 경우, 이미 정렬된 상태이므로 그대로 반환합니다.
- 배열을 두 개의 하위 배열로 나눕니다.
- 두 하위 배열을 재귀적으로 정렬합니다.
- merge 함수를 사용하여 두 정렬된 하위 배열을 병합합니다.
- merge 함수:
- 두 정렬된 배열을 병합하여 하나의 정렬된 배열을 만듭니다.
- 각 배열의 요소들을 비교하면서 작은 요소를 결과 배열에 추가합니다.
- 한쪽 배열의 요소가 모두 소진되면, 나머지 배열의 요소들을 결과 배열에 추가합니다.
- testMergeSort 함수:
- 여러 테스트 케이스를 정의합니다. 각 케이스는 입력 배열과 예상 결과 배열을 포함합니다.
- 각 테스트 케이스에 대해 mergeSort 함수를 호출하고, 결과가 예상과 일치하는지 확인합니다.
- 결과를 출력하여 테스트 통과 여부를 확인합니다.
- arraysEqual 함수:
- 두 배열이 동일한지 비교하는 헬퍼 함수입니다. 길이와 각 요소를 비교합니다.
이 예제는 분할 정복의 원리를 JavaScript로 어떻게 구현하고, 테스트하는지 잘 보여줍니다. 병합 정렬은 시간 복잡도가 O(n log n)으로, 안정적인 정렬 알고리즘입니다.