การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก
วิทยานิพนธ์ (วท.ม. )--จุฬาลงกรณ์มหาวิทยาลัย, 2552
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Theses and Dissertations |
| Language: | Thai |
| Published: |
จุฬาลงกรณ์มหาวิทยาลัย
2012
|
| Subjects: | |
| Online Access: | http://cuir.car.chula.ac.th/handle/123456789/16597 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chulalongkorn University |
| Language: | Thai |
| id |
th-cuir.16597 |
|---|---|
| record_format |
dspace |
| spelling |
th-cuir.165972012-01-25T14:06:28Z การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก Improvement of quicksort with predecessor and successor of pivot ศิวัช เรืองพิภพ กรุง สินอภิรมย์สราญ จุฬาลงกรณ์มหาวิทยาลัย. คณะวิทยาศาสตร์ การเรียงลำดับ (คอมพิวเตอร์) วิทยานิพนธ์ (วท.ม. )--จุฬาลงกรณ์มหาวิทยาลัย, 2552 ควิกซอร์ตเป็นขั้นตอนวิธีการเรียงลำดับภายในที่นิยมใช้กันมาก และมีงานวิจัยมากมายได้เสนอวิธีการปรับปรุงควิกซอร์ตให้มีประสิทธิภาพดีขึ้นเรื่อยมา งานวิจัยนี้เสนอ ควิกซอร์ตด้วยตัวประชิดตัวหลัก (APQsort) เป็นการปรับปรุงควิกซอร์ตให้มีประสิทธิภาพดีขึ้นสำหรับข้อมูลที่มีสมาชิกซ้ำกัน โดยการลดจำนวนครั้งที่เรียกฟังก์ชันเวียนเกิด APQsort ใช้ประโยชน์จากตัวนำหน้าตัวหลักหรือตัวตามหลังตัวหลัก ร่วมกับการแบ่งกั้นข้อมูลแบบสปลิตเอ็นสำหรับจัดการกับข้อมูลที่มีสมาชิกซ้ำกัน โดยเพิ่มการเก็บสมาชิกที่มีค่าเท่ากับตัวนำหน้าตัวหลักหรือตัวตามหลังตัวหลัก แทนการเก็บเพียงสมาชิกที่มีค่าเท่ากับตัวหลัก และ APQsort สามารถตรวจสอบการเรียงลำดับของข้อมูลย่อยได้โดยพิจารณาจากตัวชี้ของตัวนำหน้าตัวหลักหรือตัวตามหลังตัวหลัก การทดสอบประสิทธิภาพของ APQsort ใช้ข้อมูลสี่แบบ ได้แก่ ข้อมูลแบบสุ่ม ข้อมูลที่เกือบเรียงลำดับ ข้อมูลที่เกือบเรียงลำดับแบบย้อนกลับ และข้อมูลแบบสุ่มที่มีสมาชิกซ้ำกัน โดยนำมาเปรียบเทียบกับ Mergesort Heapsort Quicksort (ควิกซอร์ตดั้งเดิม) qsort ซึ่งเป็นควิกซอร์ตที่ใช้การแบ่งกั้นข้อมูลแบบสปลิตเอ็น และ SWQuicksort ซึ่งเป็นขั้นตอนวิธีที่ปรับปรุงมาจากควิกซอร์ต จากการทดลองพบว่า APQsort ประมวลผลได้เร็วกว่า Mergesort Heapsort Quicksort qsort และ SWQuicksort สำหรับข้อมูลแบบสุ่มที่มีสมาชิกซ้ำกันเป็นจำนวนมาก และข้อมูลเรียงลำดับหรือข้อมูลเรียงลำดับแบบย้อนกลับ 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 2012-01-25T14:06:28Z 2012-01-25T14:06:28Z 2552 Thesis http://cuir.car.chula.ac.th/handle/123456789/16597 th จุฬาลงกรณ์มหาวิทยาลัย 1332569 bytes application/pdf application/pdf จุฬาลงกรณ์มหาวิทยาลัย |
| institution |
Chulalongkorn University |
| building |
Chulalongkorn University Library |
| country |
Thailand |
| collection |
Chulalongkorn University Intellectual Repository |
| language |
Thai |
| topic |
การเรียงลำดับ (คอมพิวเตอร์) |
| spellingShingle |
การเรียงลำดับ (คอมพิวเตอร์) ศิวัช เรืองพิภพ การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก |
| description |
วิทยานิพนธ์ (วท.ม. )--จุฬาลงกรณ์มหาวิทยาลัย, 2552 |
| author2 |
กรุง สินอภิรมย์สราญ |
| author_facet |
กรุง สินอภิรมย์สราญ ศิวัช เรืองพิภพ |
| format |
Theses and Dissertations |
| author |
ศิวัช เรืองพิภพ |
| author_sort |
ศิวัช เรืองพิภพ |
| title |
การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก |
| title_short |
การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก |
| title_full |
การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก |
| title_fullStr |
การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก |
| title_full_unstemmed |
การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก |
| title_sort |
การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก |
| publisher |
จุฬาลงกรณ์มหาวิทยาลัย |
| publishDate |
2012 |
| url |
http://cuir.car.chula.ac.th/handle/123456789/16597 |
| _version_ |
1681413048702599168 |