Chulalongkorn University Theses and Dissertations (Chula ETD)

การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก

Other Title (Parallel Title in Other Language of ETD)

Improvement of quicksort with predecessor and successor of pivot

Year (A.D.)

2009

Document Type

Thesis

First Advisor

กรุง สินอภิรมย์สราญ

Faculty/College

Faculty of Science (คณะวิทยาศาสตร์)

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาการคณนา

DOI

10.58837/CHULA.THE.2009.1020

Abstract

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

Other Abstract (Other language abstract of ETD)

Quicksort is one of the most popular internal sorting algorithms. Many researches suggested various improvements of Quicksort. In this research, we propose Adjacent Pivot Quicksort (APQsort) which improves the performance of Quicksort for data with repeated elements by reducing the number of recursive calls. APQsort utilizes additional elements called “pivot predecessor" or “pivot successor" combined with the Split-end partition to handles the repeated elements keeping the elements which are equal to predecessor pivot or successor pivot instead of keeping only the elements which are equal to the pivot. APQsort can check the sorted sublist by consider pointer of predecessor pivot or successor pivot. We compare the performance of APQsort with the performance of Mergesort, Heapsort, the original Quicksort, qsort which is the Quicksort with split-end partition and SWQuicksort which is improvement of Quicksort in four different data sets; completely random data, nearly sorted data, nearly reverse sorted data and repeated element data. Our experiments show that APQsort significantly exhibits the faster running time for random data with a lot of repeat elements, sorted data and reverse sorted data than Mergesort, Heapsort, Quicksort, qsort and SWQuicksort

Link to Full Text

Share

COinS