การเรียงลำดับภายนอก

การเรียงลำดับภายนอก (อังกฤษ: external sorting) หรือขั้นตอนวิธีผสานหลายเส้นทาง (k-way Merge Algorithm) เป็นการแก้ปัญหาโดยใช้หลักการแก้ที่เรียกว่า การแบ่งแยกและเอาชนะ (Divide & Conquer) โดยขั้นตอนนี้ใช้เพื่อเรียงลำดับข้อมูลที่รับมาจากน้อยไปมาก โดยสมมติว่าข้อมูลที่รับเข้ามาเป็นรายการที่มีสมาชิก n ตัว หากเราเรียงลำดับแบบปกติคือไล่จับคู่ทีละคู่ เพื่อเปรียบเทียบว่าตัวใดน้อยกว่า แล้วเรียงลำดับจนครบทุกคู่ จะมีประสิทธิภาพเชิงเวลาคือ O(n²) ซึ่งถือว่าค่อนข้างมากเลยทีเดียว เราสามารถลดเวลาที่ใช้ได้โดยเราจะแบ่งข้อมูลออกเป็น k รายการ โดยแต่ละรายการจะมีจำนวนข้อมูลเท่า ๆ กัน คือ ⌊n / k⌋ ซึ่งหากแบ่งเท่า ๆ กันไม่ได้ อาจจะมีบางรายการมีจำนวนข้อมูลเป็น ⌊n / k⌋ + 1 จากนั้นทำการเรียงลำดับข้อมูลทั้ง k รายการ แล้วนำกลับมาผสานกันกลายเป็นรายการเดียวที่มีการเรียงลำดับเรียบร้อย

การอธิบายขั้นตอน

หลังจากทำการเรียงลำดับข้อมูลทั้ง k รายการแล้ว เรามีอัลกอริธึมสำหรับผสานข้อมูลทั้ง k รายการเป็นรายการเดียวอยู่ 3 แบบ

1. ผสานโดยการค้นหาแบบเชิงเส้น นำค่าที่น้อยที่สุดของแต่ละรายการมาหาค่าน้อยทีสุด เมื่อได้ค่านั้นแล้วให้ทำการลบค่านั้นของจากรายการที่มันอยู่แล้วไปใส่ไว้รายการคำตอบ จากนั้นทำการจัดลำดับรายการที่เอาค่านั้นออกมาใหม่ (ในกรณีที่รายการนั้นไม่มีสมาชิกเหลือแล้วให้ใส่เป็นค่า null โดยค่า null จะไม่ถูกนำมาเปรียบเทียบเพื่อหาค่าน้อยที่สุด) แล้วกลับไปเริ่มพิจารณาหาค่าที่น้อยที่สุดของแต่ละรายการอีกรอบ ทำแบบนี้ไปเรื่อย ๆ จนกว่าข้อมูลของแต่ละรายการจะหมด จะได้รายการคำตอบที่ข้อมูลภายในนั้นเป็นข้อมูลที่มีการจัดเรียงไว้เรียบร้อยแล้ว
2. ผสานโดยการใช้ฮีป นำค่าน้อยที่สุดของทั้ง k รายการมาใส่ลงในฮีปน้อยสุด (จากคุณสมบัติของฮีปน้อยสุดจะได้ค่าที่น้อยที่สุดเป็นรากเสมอ) จากนั้นนำค่าของรากนั้นไปใส่ในรายการคำตอบ แล้วแทนที่ค่าของรากนั้นด้วยค่าที่น้อยเป็นอันดับถัดมาจากรายการที่รากนั้นอยู่ ทำการปรับต้นไม้ จากนั้นกลับไปดึงค่าของรากไปใส่ในรายการคำตอบอีกรอบ ทำแบบนี้ไปเรื่อยจนกว่าฮีปจะมีสมาชิกเป็น 0
3. ผสานโดยใช้หลักการแบ่งแยกและเอาชนะ ใช้หลักการเวียนเกิด โดยแบ่งรายการออกเป็น 2 ส่วนไปเรื่อย ๆ จนกว่าจะเป็นกรณีเล็กที่สุดเท่าที่กำหนด จากนั้นค่อยผสานผลลัพธ์ทีละ 2 ส่วนเข้าด้วยกันจนกลับมาเป็นก้อนใหญ่เท่าตอนแรก

รหัสเทียมและประสิทธิภาพเชิงเวลา

ผสานโดยการค้นหาแบบเชิงเส้น

ต้องใช้เวลาในการวนจนครบข้อมูลทุกตัวจึงเสียเวลา n รอบ โดยแต่ละรอบต้องวนเปรียบเทียบค่าน้อยที่สุดของแต่ละรายการเพื่อหาค่าน้อยที่สุดมาใส่รายการคำตอบ เนื่องจากมีทั้งหมด k รายการ เวลาที่มากที่สุดในการวนตรวจสอบจึงเป็น k รอบ

→ ประสิทธิภาพเชิงเวลาของวิธีนี้จึงเป็น O(nk)

ผสานโดยการใช้ฮีป

ข้อมูลทุกตัวต้องถูกนำมาใส่ในฮีปจึงเสียเวลาทั้งหมด n รอบ โดยแต่ละรอบเมื่อมีการดึงค่ารากออกไปใส่ในรายการคำตอบ แล้วแทนที่ค่าของรากนั้นด้วยค่าที่น้อยกว่าเป็นอันดับรองลงมาจากรายการเดียวกับที่ค่ารากนั้นอยู่ ทำให้ต้องเสียเวลาในการปรับฮีปเป็นเวลาอย่างมาก log k

→ ประสิทธิภาพเชิงเวลาของวิธีนี้จึงเป็น O(n log k)

ผสานโดยใช้หลักการแบ่งแยกและเอาชนะ

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

→ ประสิทธิภาพเชิงเวลาของวิธีนี้จึงเป็น O(n log k)

พิสูจน์ความถูกต้อง

หากค่าที่น้อยที่สุดของข้อมูลแต่ละรายการเป็น min₁ , min₂ , min₃ , … , min_k ค่าที่น้อยที่สุดของค่าเหล่านี้ย่อมเป็นค่าที่น้อยที่สุดของข้อมูลด้วย

จากหลักการนี้ ทั้งวิธี ผสานโดยการค้นหาแบบเชิงเส้น และ ผสานโดยการใช้ฮีป ใช้หลักการแบบเดียวกัน คือหาค่าที่น้อยที่สุดจากค่าที่น้อยสุดของทั้ง k รายการมาเติมลงในรายการคำตอบเรื่อย ๆ ดังนั้นรายการคำตอบจะถูกเติมเรื่อย ๆ จากน้อยไปมากจนครบข้อมูลทุกตัว

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

ตัวอย่างการประยุกต์ใช้งาน

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

เช่น ในการเรียงลำดับของข้อมูลของสินค้าต่าง ๆ ในคลังเก็บสินค้า เราสามารถเรียงได้หลายแบบ

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

จะเห็นได้ว่าวิธีการผสานหลายเส้นทางจะมีส่วนช่วยลดเวลาในส่วนของการเรียงลำดับได้มากทีเดียว

อ้างอิง

• Greene, William A. (1993), "k-way merging and k-ary sorts", Computer Science Department , University of New Orleans (PDF).
• Black, Paul E. (2009), "k-way merge sort", Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology.