การรวมและการจัดเรียงแบบปรับได้ในโครงสร้างข้อมูล

การจัดเรียงการผสานแบบปรับได้

Adaptive Merge Sort ทำการผสานการเรียงลำดับการผสานรายการย่อยที่เรียงลำดับแล้ว อย่างไรก็ตาม ขนาดของรายการย่อยเริ่มต้นขึ้นอยู่กับการมีอยู่ของการจัดลำดับในรายการองค์ประกอบ แทนที่จะมีรายการย่อยขนาด 1 ตัวอย่างเช่น พิจารณารายการในรูป

ประกอบด้วยรายการย่อยที่จัดเรียง 2 รายการ

• รายการย่อย 1 ที่มีองค์ประกอบ 16,15,14,13.
• รายการย่อย 2 ที่มีองค์ประกอบ 9,10,11,12.

รายการย่อย 1 ถูกจัดเรียงแต่ในลำดับที่กลับกัน ดังนั้นรายการย่อย 1 จึงกลับรายการดังแสดงในรูป

เมื่อพบรายการย่อยแล้ว กระบวนการรวมจะเริ่มขึ้น การเรียงลำดับการผสานแบบปรับเปลี่ยนได้เริ่มการผสานรายการย่อย การเรียงลำดับการผสานแบบปรับเปลี่ยนได้จะต้องมีขั้นตอนการผสานเพียงขั้นตอนเดียว เนื่องจากมีเพียง 2 รายการย่อยเท่านั้น ผลลัพธ์ของการรวมแสดงในรูป

แนวคิดการออกแบบ

• เริ่มต้นด้วยการค้นหารายการย่อยที่จัดเรียงไว้แล้วในลำดับที่จำเป็นหรือย้อนกลับ
• หากมีรายการย่อยที่มีองค์ประกอบในลำดับที่กลับกัน ให้กลับรายการย่อยโดยการแลกเปลี่ยนองค์ประกอบที่ 1 กับองค์ประกอบสุดท้าย องค์ประกอบที่ 2 กับองค์ประกอบที่ 2 รายการสุดท้ายและจะดำเนินต่อไป
• รวมรายการย่อยต่อไปเพื่อสร้างรายการย่อยใหม่จนกว่าจะเหลือเพียง 1 รายการย่อยเท่านั้น

การวิเคราะห์การจัดเรียงการผสานแบบปรับได้

การเรียงลำดับการผสานแบบปรับเปลี่ยนได้แทนที่จะเริ่มต้นด้วยรายการย่อยขนาด 1 จะค้นหารายการย่อยที่จัดเรียงไว้แล้วในลำดับที่จำเป็นหรือย้อนกลับ ขนาดของรายการย่อยที่พบในช่วงแรกจะน้อยที่สุด 2 และสูงสุด m (m คือจำนวนขององค์ประกอบ)

อย่างไรก็ตาม หากรายการย่อยมีองค์ประกอบในลำดับย้อนกลับ ก็จะกลับรายการก่อนที่จะเริ่มดำเนินการผสาน การกลับรายการต้องมีการดำเนินการแลกเปลี่ยน (m/2)

กรณีที่ดีที่สุด

ถ้ารายการอยู่ในลำดับที่เรียงลำดับแล้วหรือในลำดับที่กลับกัน การเรียงลำดับการผสานแบบปรับเปลี่ยนจะมีเพียงรายการเดียวและจะไม่ต้องดำเนินการผสานใดๆ อย่างไรก็ตาม การค้นหาว่ารายการถูกจัดเรียงแล้วจะต้องมีการดำเนินการเปรียบเทียบ O(m) และการดำเนินการแลกเปลี่ยน (m/2) หากรายการถูกเรียงลำดับในลำดับที่กลับกัน ซึ่งจะทำให้การจัดเรียง Adaptive Merge ปรับเปลี่ยนได้แม้ว่ารายการจะเรียงลำดับกลับกัน

ดังนั้นความซับซ้อนของเวลาสำหรับกรณีที่ดีที่สุดจึงคำนวณได้ดังนี้ −

T(m) = (m-1)+(m/2)
T(m) = (2m-2+m)/2
T(m) = O(m).

อย่างไรก็ตาม Adaptive merge sort ใช้พื้นที่เพิ่มเติมของ O(m) ในการเปรียบเทียบการเรียงลำดับการผสาน

แย่ที่สุด

การเรียงลำดับการผสานแบบปรับเปลี่ยนได้จะค้นหารายการย่อยที่เรียงลำดับตามความจำเป็นหรือลำดับย้อนกลับแล้ว อย่างไรก็ตาม ในกรณีที่เลวร้ายที่สุด ไม่มีองค์ประกอบการจัดลำดับบางส่วนหรือทั้งหมด ดังนั้น รายการย่อยที่พบตั้งแต่แรกจะมีขนาด 2 เมื่อพบรายการย่อยแล้ว กระบวนการรวมจะเริ่มต้นขึ้น

• การรวมรายการย่อยของขนาด 2 ผลลัพธ์ในการเรียงลำดับรายการย่อยของขนาด 4
• การรวมรายการย่อยของขนาด 4 ผลลัพธ์ในการเรียงลำดับรายการย่อยของขนาด 8
• กระบวนการรวมจะดำเนินต่อไปจนถึงและเว้นแต่ 2k

เนื่องจากขั้นตอนการผสานในกรณีที่เลวร้ายที่สุดของการเรียงลำดับการผสานแบบปรับเปลี่ยนได้จะเหมือนกับการเรียงลำดับการผสาน ดังนั้น ความซับซ้อนของเวลาสำหรับกรณีที่เลวร้ายที่สุดของการเรียงลำดับการผสานแบบปรับเปลี่ยนได้จึงคล้ายกับการเรียงลำดับการผสาน –

T(m) = O(m log m).