ผสาน-เรียงลำดับ
การเรียงลำดับการผสานเป็นตัวอย่างของอัลกอริธึมการเรียงลำดับประเภทการแบ่งและพิชิต การป้อนข้อมูลของการเรียงลำดับการผสานคืออาร์เรย์ขององค์ประกอบบางอย่าง ซึ่งโดยทั่วไปจะต้องจัดเรียงจากน้อยไปมาก
ขั้นตอนที่ต้องปฏิบัติตามในการผสานการเรียงลำดับ
- การจัดเรียงแบบผสานแบ่งอาร์เรย์ออกเป็นสองอาร์เรย์ย่อย และต่อมาแบ่งแต่ละอาร์เรย์ออกเป็นอีก 2 อาร์เรย์ และอื่นๆ จนกว่าจะเหลืออาร์เรย์ขององค์ประกอบเดี่ยวจำนวนมาก ตัวอย่างเช่น ในตัวอย่างต่อไปนี้ อาร์เรย์ [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
