병합 정렬
병합 정렬은 분할 정복 유형 정렬 알고리즘의 한 예입니다. 병합 정렬의 입력은 일반적으로 최소에서 최대로 정렬되어야 하는 일부 요소의 배열입니다.
병합 정렬에서 따라야 할 단계
- 병합 정렬은 배열을 두 개의 하위 배열로 나눈 다음 나중에 각 배열을 다른 두 개의 배열로 나누는 식으로 단일 요소 배열이 많이 남을 때까지 계속됩니다. 예를 들어 다음 예에서 배열 [4,7,5,9,1,3,8,2]는 [4], [7], [5], [9]와 같은 단일 배열 요소로 나뉩니다. [1], [3], [8], [2].
- 두 개의 배열을 비교하여 연결하는 방식으로 배열 비교를 시작합니다. 다음 예에서는 한 번에 두 개의 배열을 비교하며 [4], [7]을 비교하여 연결한 다음 [5], [9]를 비교하여 연결하는 식으로 배열 [4,7], [ 5,9], [1,3], [2,8]이 형성됩니다.
- 두 개의 배열을 비교하고 연결하여 두 개의 배열을 형성하는 것과 동일한 방식을 따릅니다. 다음 예에서는 [4,7]과 [5,9]를 비교 및 연결하여 [4,5,7,9]와 같은 배열을 얻습니다. 다른 두 배열도 [1, 2,3,8].
- 나머지 두 배열을 비교하고 연결하여 [1,2,3,4,5,7,8,9]와 같은 최종 배열을 얻는 것과 동일한 규칙이 여기에 적용됩니다.
예시
<html>
<body>
<script>
function mSort (array) {
if (array.length === 1) {
return array // return once we hit an array with a single item
}
const middle = Math.floor(array.length / 2) // get the middle item of the array rounded down
const left = array.slice(0, middle) // items on the left side
const right = array.slice(middle) // items on the right side
document.write(middle);
return merge(
mSort(left),
mSort(right)
)
}
// compare the arrays item by item and return the concatenated result
function merge (left, right) {
let result = []
let leftIndex = 0
let rightIndex = 0
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex])
leftIndex++
document.write("</br>");
} else {
result.push(right[rightIndex])
rightIndex++
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
}
const list = [4,7,5,9,1,3,8,2]
document.write(mSort(list));
</script>
</body>
</html> 출력
1,2,3,4,5,7,8,9