วิทยานิพนธ์ (วท.ม. )--จุฬาลงกรณ์มหาวิทยาลัย, 2552

ควิกซอร์ตเป็นขั้นตอนวิธีการเรียงลำดับภายในที่นิยมใช้กันมาก และมีงานวิจัยมากมายได้เสนอวิธีการปรับปรุงควิกซอร์ตให้มีประสิทธิภาพดีขึ้นเรื่อยมา งานวิจัยนี้เสนอ ควิกซอร์ตด้วยตัวประชิดตัวหลัก (APQsort) เป็นการปรับปรุงควิกซอร์ตให้มีประสิทธิภาพดีขึ้นสำหรับข้อมูลที่มีสมาชิกซ้ำกัน โดยการลดจำนวนครั้งที่เรียกฟังก์ชันเวียนเกิด APQsort ใช้ประโยชน์จากตัวนำหน้าตัวหลักหรือตัวตามหลังตัวหลัก ร่วมกับการแบ่งกั้นข้อมูลแบบสปลิตเอ็นสำหรับจัดการกับข้อมูลที่มีสมาชิกซ้ำกัน โดยเพิ่มการเก็บสมาชิกที่มีค่าเท่ากับตัวนำหน้าตัวหลักหรือตัวตามหลังตัวหลัก แทนการเก็บเพียงสมาชิกที่มีค่าเท่ากับตัวหลัก และ APQsort สามารถตรวจสอบการเรียงลำดับของข้อมูลย่อยได้โดยพิจารณาจากตัวชี้ของตัวนำหน้าตัวหลักหรือตัวตามหลังตัวหลัก การทดสอบประสิทธิภาพของ APQsort ใช้ข้อมูลสี่แบบ ได้แก่ ข้อมูลแบบสุ่ม ข้อมูลที่เกือบเรียงลำดับ ข้อมูลที่เกือบเรียงลำดับแบบย้อนกลับ และข้อมูลแบบสุ่มที่มีสมาชิกซ้ำกัน โดยนำมาเปรียบเทียบกับ Mergesort Heapsort Quicksort (ควิกซอร์ตดั้งเดิม) qsort ซึ่งเป็นควิกซอร์ตที่ใช้การแบ่งกั้นข้อมูลแบบสปลิตเอ็น และ SWQuicksort ซึ่งเป็นขั้นตอนวิธีที่ปรับปรุงมาจากควิกซอร์ต จากการทดลองพบว่า APQsort ประมวลผลได้เร็วกว่า Mergesort Heapsort Quicksort qsort และ SWQuicksort สำหรับข้อมูลแบบสุ่มที่มีสมาชิกซ้ำกันเป็นจำนวนมาก และข้อมูลเรียงลำดับหรือข้อมูลเรียงลำดับแบบย้อนกลับ