Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/62805
| Title: | การพัฒนาอัลกอริทึมการเรียงลำดับข้อมูลแบบควิกซอร์ต ด้วยวิธีโคดเวิร์ด |
| Other Titles: | Development of quicksort algorithm with codeword scheme |
| Authors: | สุกัญญา ชัยมงคลเจริญ |
| Advisors: | ศุภชัย ตั้งวงศ์ศานต์ สุเมธ วัชระชัยสุรพล |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. บัณฑิตวิทยาลัย |
| Subjects: | คอมพิวเตอร์อัลกอริทึม การเรียงลำดับ (คอมพิวเตอร์) อัลกอริทึม การเขียนโปรแกรม (คอมพิวเตอร์) Computer algorithms Sorting (Electronic computers) Algorithms Computer programming |
| Issue Date: | 2534 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | จุดประสงค์การวิจัยนี้ เพื่อศึกษาอัลกอริทึมการเรียงลำดับข้อมูลควิกซอร์ตด้วยวิธีโคดเวิร์ดสำหรับการเรียงลำดับข้อมูลที่มีคีย์เป็นชุดลำดับตัวอักษร และหาโครงสร้างข้อมูลที่เหมาะสมในการทำงานของอัลกอริทึมเพื่อให้ทำงานมีประสิทธิภาพดีขึ้น จากผลงานวิจัยของ Baer และ Lin การปรับปรุงประสิทธิภาพของควิกซอร์ตโดยการใช้ค่าโคดเวิร์ดทำให้มีประสิทธิภาพดีขึ้น แต่วิธีการนำค่าโคดเวิร์ดไปใช้งานยังคงให้ผลการเรียงลำดับข้อมูลที่ไม่เสถียรภาพอยู่ งานวิจัยนี้เพื่อหาแนวทางปรับปรุงการทำงานการเรียงลำดับข้อมูลที่ใช้โคดเวิร์ด โดยการใช้โครงสร้างข้อมูลรายการเชื่อมโยง เพื่อให้การทำงานของค่าโคดเวิร์ดที่ทำให้การแบ่งส่วนข้อมูลได้เป็นกลุ่มย่อยมากกว่า 2 ส่วน เป็นการทำให้เกิดประสิทธิภาพดียิ่งขึ้น และยิ่งกว่านั้นผลการเรียงลำดับของข้อมูลที่ได้มีเสถียรภาพด้วย ผลการทดสอบเพื่อวัดการทำงานของอัลกอริทึมที่ปรับปรุงขึ้นใหม่ พบว่ามีการใช้จำนวนรอบในการแบ่งส่วนข้อมูลน้อยลง จำนวนการเปรียบเทียบข้อมูลน้อยลง จำนวนไบต์ที่ใช้เปรียบเทียบน้อยลงทำให้อัลกอริทึมที่ปรับปรุงใหม่ใช้เวลาในการเรียงลำดับน้อยลงเป็น 50%-60% ของอัลกอริทึมควิกซอร์ตและเมื่อเปรียบเทียบกับวิธีการของ Bear และ Lin แล้วอัลกอริทึมที่ปรับปรุงใหม่ใช้เวลาในการเรียงลำดับเป็น 55%-70% |
| Other Abstract: | This research is to study the Quicksort algorithm with codeword scheme for application of alphanumeric key sorting, and to investigate the appropriate data structure for implementation which can further improve the sorting performance. The present work is, in principle, based on the study of Baer and Lin for improving Quicksort algorithm. Although their technique shows significant improvement in efficiency by using codewords, but in the implementation, the result still produces unstable sorted list that needed further investigation. The work here proposes a modified Quicksort routine (MQS) with codewords and the implementation by using a linked list structure. The codewords can be partitioned, not only into two groups as the previous work, but also into three or more groups, that shows even better improvement. Furthermore with linked list structure, the sorted result is proved to be stable! The experimental results show that the MQS required fewer call to the partition procedure, also the number of comparisons and bytes compared are greatly reduced. For the speed is concerned, the MQS takes approximately 50-60% of the time used by the Quicksort, and 55-70% by the Quicksort codeword based routine proposed by Baer and Lin. |
| Description: | วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2534 |
| Degree Name: | วิศวกรรมศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิศวกรรมคอมพิวเตอร์ |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/62805 |
| ISBN: | 9745789623 |
| Type: | Thesis |
| Appears in Collections: | Grad - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Sukanya_cha_front_p.pdf | 7.58 MB | Adobe PDF | View/Open | |
| Sukanya_cha_ch1_p.pdf | 3.7 MB | Adobe PDF | View/Open | |
| Sukanya_cha_ch2_p.pdf | 4.81 MB | Adobe PDF | View/Open | |
| Sukanya_cha_ch3_p.pdf | 18 MB | Adobe PDF | View/Open | |
| Sukanya_cha_ch4_p.pdf | 4.17 MB | Adobe PDF | View/Open | |
| Sukanya_cha_ch5_p.pdf | 7.77 MB | Adobe PDF | View/Open | |
| Sukanya_cha_ch6_p.pdf | 3.73 MB | Adobe PDF | View/Open | |
| Sukanya_cha_back_p.pdf | 1.86 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.