Multikey Quicksort for Sorting String Using Predecessor and Successor Pivots
Thesis (M.Sc.)--Chulalongkorn University, 2012
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | Book |
| Published: |
Chulalongkorn University,
2015-06-24T04:12:48Z.
|
| Subjects: | |
| Online Access: | http://cuir.car.chula.ac.th/handle/123456789/42527 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Thesis (M.Sc.)--Chulalongkorn University, 2012 Quicksort is one of the most popular internal sorting algorithms. In this research, we propose multikey quicksort for sorting sequence of integers and strings using predecessor pivots, successor pivots and the collect-center partition. Predecessor pivots and successor pivots are used to reduce the recursive calls while the collect-center partitioning is used to reduce the number of swaps. We compare the performance of our algorithm, called CC5sort, with the performance of the quicksort using adjacent pivot quicksort and the original collect-center partition. We tested an efficiency of CC5sort in four different types of data sets; nearly sorted data, nearly reverse sorted data, repeated element data and random ordered data. Our experiments show that CC5sort significantly exhibits the faster running time for random ordered data with a lot of repeated elements than collect-center partitioning and APQsort. ควิกซอร์ตเป็นขั้นตอนวิธีการเรียงลำดับภายในที่นิยมใช้กันมาก งานวิจัยนี้เราเสนอ การปรับปรุงควิกซอร์ตสำหรับจำนวนเต็มและสายอักขระด้วยตัวนำหน้าตัวหลัก ตัวตามหลังตัวหลักและการแบ่งกั้นแบบ collect-center การใช้ตัวนำหน้าตัวหลักและตัวตามหลังตัวหลักช่วยลดจำนวนครั้งที่เรียกฟังก์ชันเวียนเกิดในขณะที่การแบ่งกั้นแบบ collect-center ช่วยลดจำนวนการสลับที่ เราเปรียบเทียบประสิทธิภาพของอัลกอริทึมของเราซึ่งเรียกว่า CC5sort กับควิกซอร์ตด้วยตัวประชิด และการแบ่งกั้นต้นแบบของ collect-center เราทดสอบประสิทธิภาพของ CC5sort ในข้อมูลสี่แบบ ได้แก่ ข้อมูลที่เกือบเรียงลำดับ ข้อมูลที่เกือบเรียงลำดับแบบย้อนกลับ ข้อมูลแบบสุ่มที่มีสมาชิกซ้ำกันแบบเอกภาพและข้อมูลแบบสุ่ม จากการทดลองของเราพบว่า CC5sort ประมวลผลได้เร็วกว่า Collect-center partitioning และ APQsort สำหรับข้อมูลแบบสุ่มที่มีสมาชิกซ้ำกันเป็นจำนวนมาก |
|---|---|
| Item Description: | http://cuir.car.chula.ac.th/handle/123456789/42527 |