Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/16597
| Title: | การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก |
| Other Titles: | Improvement of quicksort with predecessor and successor of pivot |
| Authors: | ศิวัช เรืองพิภพ |
| Advisors: | กรุง สินอภิรมย์สราญ |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิทยาศาสตร์ |
| Advisor's Email: | krung@math.sc.chula.ac.th |
| Subjects: | การเรียงลำดับ (คอมพิวเตอร์) |
| Issue Date: | 2552 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | ควิกซอร์ตเป็นขั้นตอนวิธีการเรียงลำดับภายในที่นิยมใช้กันมาก และมีงานวิจัยมากมายได้เสนอวิธีการปรับปรุงควิกซอร์ตให้มีประสิทธิภาพดีขึ้นเรื่อยมา งานวิจัยนี้เสนอ ควิกซอร์ตด้วยตัวประชิดตัวหลัก (APQsort) เป็นการปรับปรุงควิกซอร์ตให้มีประสิทธิภาพดีขึ้นสำหรับข้อมูลที่มีสมาชิกซ้ำกัน โดยการลดจำนวนครั้งที่เรียกฟังก์ชันเวียนเกิด APQsort ใช้ประโยชน์จากตัวนำหน้าตัวหลักหรือตัวตามหลังตัวหลัก ร่วมกับการแบ่งกั้นข้อมูลแบบสปลิตเอ็นสำหรับจัดการกับข้อมูลที่มีสมาชิกซ้ำกัน โดยเพิ่มการเก็บสมาชิกที่มีค่าเท่ากับตัวนำหน้าตัวหลักหรือตัวตามหลังตัวหลัก แทนการเก็บเพียงสมาชิกที่มีค่าเท่ากับตัวหลัก และ APQsort สามารถตรวจสอบการเรียงลำดับของข้อมูลย่อยได้โดยพิจารณาจากตัวชี้ของตัวนำหน้าตัวหลักหรือตัวตามหลังตัวหลัก การทดสอบประสิทธิภาพของ APQsort ใช้ข้อมูลสี่แบบ ได้แก่ ข้อมูลแบบสุ่ม ข้อมูลที่เกือบเรียงลำดับ ข้อมูลที่เกือบเรียงลำดับแบบย้อนกลับ และข้อมูลแบบสุ่มที่มีสมาชิกซ้ำกัน โดยนำมาเปรียบเทียบกับ Mergesort Heapsort Quicksort (ควิกซอร์ตดั้งเดิม) qsort ซึ่งเป็นควิกซอร์ตที่ใช้การแบ่งกั้นข้อมูลแบบสปลิตเอ็น และ SWQuicksort ซึ่งเป็นขั้นตอนวิธีที่ปรับปรุงมาจากควิกซอร์ต จากการทดลองพบว่า APQsort ประมวลผลได้เร็วกว่า Mergesort Heapsort Quicksort qsort และ SWQuicksort สำหรับข้อมูลแบบสุ่มที่มีสมาชิกซ้ำกันเป็นจำนวนมาก และข้อมูลเรียงลำดับหรือข้อมูลเรียงลำดับแบบย้อนกลับ |
| Other Abstract: | 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 |
| Description: | วิทยานิพนธ์ (วท.ม. )--จุฬาลงกรณ์มหาวิทยาลัย, 2552 |
| Degree Name: | วิทยาศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิทยาการคณนา |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/16597 |
| URI: | http://doi.org/10.14457/CU.the.2009.295 |
| metadata.dc.identifier.DOI: | 10.14457/CU.the.2009.295 |
| Type: | Thesis |
| Appears in Collections: | Sci - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Siwat_ru.pdf | 1.3 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.