Hợp nhất-Sắp xếp
Sắp xếp hợp nhất là một ví dụ về thuật toán sắp xếp kiểu chia để trị. Đầu vào của sắp xếp hợp nhất là một mảng của một số phần tử, chúng cần được sắp xếp thường từ nhỏ nhất đến lớn nhất.
Các bước cần thực hiện trong Sắp xếp Hợp nhất
- Sắp xếp hợp nhất chia mảng thành hai mảng con và sau đó chia từng mảng cho hai mảng khác và cứ tiếp tục như vậy cho đến khi còn lại một loạt các mảng phần tử đơn lẻ. Ví dụ:trong ví dụ sau, mảng [4,7,5,9,1,3,8,2] chia thành các phần tử mảng đơn như [4], [7], [5], [9], [1], [3], [8], [2].
- Nó bắt đầu so sánh các mảng theo cách mà hai mảng được so sánh và nối. Trong ví dụ sau, nó so sánh hai mảng tại một thời điểm là [4], [7] được so sánh và nối sau đó [5], [9] được so sánh và nối và cứ như vậy các mảng [4,7], [ 5,9], [1,3], [2,8] được hình thành.
- Nó theo cùng một cách đó là hai mảng được so sánh và nối để tạo thành hai mảng. Trong ví dụ sau [4,7] và [5,9] được so sánh và nối để có được một mảng là [4,5,7,9] và trường hợp tương tự với hai mảng khác để tạo thành một mảng là [1, 2,3,8].
- Quy tắc tương tự có thể áp dụng ở đây là hai mảng còn lại so sánh và nối để có được mảng cuối cùng là [1,2,3,4,5,7,8,9].
Ví dụ
<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> Đầu ra
1,2,3,4,5,7,8,9