Chulalongkorn University Theses and Dissertations (Chula ETD)
Multikey Quicksort for Sorting String Using Predecessor and Successor Pivots
Other Title (Parallel Title in Other Language of ETD)
มัลติคีย์ควิกซอร์ตสำหรับการเรียงลำดับสายอักขระด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก
Year (A.D.)
2012
Document Type
Thesis
First Advisor
Krung Sinapiromsaran
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Computer Science and Information Technology
DOI
10.58837/CHULA.THE.2012.939
Abstract
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.
Other Abstract (Other language abstract of ETD)
ควิกซอร์ตเป็นขั้นตอนวิธีการเรียงลำดับภายในที่นิยมใช้กันมาก งานวิจัยนี้เราเสนอ การปรับปรุงควิกซอร์ตสำหรับจำนวนเต็มและสายอักขระด้วยตัวนำหน้าตัวหลัก ตัวตามหลังตัวหลักและการแบ่งกั้นแบบ collect-center การใช้ตัวนำหน้าตัวหลักและตัวตามหลังตัวหลักช่วยลดจำนวนครั้งที่เรียกฟังก์ชันเวียนเกิดในขณะที่การแบ่งกั้นแบบ collect-center ช่วยลดจำนวนการสลับที่ เราเปรียบเทียบประสิทธิภาพของอัลกอริทึมของเราซึ่งเรียกว่า CC5sort กับควิกซอร์ตด้วยตัวประชิด และการแบ่งกั้นต้นแบบของ collect-center เราทดสอบประสิทธิภาพของ CC5sort ในข้อมูลสี่แบบ ได้แก่ ข้อมูลที่เกือบเรียงลำดับ ข้อมูลที่เกือบเรียงลำดับแบบย้อนกลับ ข้อมูลแบบสุ่มที่มีสมาชิกซ้ำกันแบบเอกภาพและข้อมูลแบบสุ่ม จากการทดลองของเราพบว่า CC5sort ประมวลผลได้เร็วกว่า Collect-center partitioning และ APQsort สำหรับข้อมูลแบบสุ่มที่มีสมาชิกซ้ำกันเป็นจำนวนมาก
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Borisuttinant, Purika, "Multikey Quicksort for Sorting String Using Predecessor and Successor Pivots" (2012). Chulalongkorn University Theses and Dissertations (Chula ETD). 61969.
https://digital.car.chula.ac.th/chulaetd/61969