การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก

ศิวัช เรืองพิภพ

Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/16597

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	กรุง สินอภิรมย์สราญ	-
dc.contributor.author	ศิวัช เรืองพิภพ	-
dc.contributor.other	จุฬาลงกรณ์มหาวิทยาลัย. คณะวิทยาศาสตร์	-
dc.date.accessioned	2012-01-25T14:06:28Z	-
dc.date.available	2012-01-25T14:06:28Z	-
dc.date.issued	2552	-
dc.identifier.uri	http://cuir.car.chula.ac.th/handle/123456789/16597	-
dc.description	วิทยานิพนธ์ (วท.ม. )--จุฬาลงกรณ์มหาวิทยาลัย, 2552	en
dc.description.abstract	ควิกซอร์ตเป็นขั้นตอนวิธีการเรียงลำดับภายในที่นิยมใช้กันมาก และมีงานวิจัยมากมายได้เสนอวิธีการปรับปรุงควิกซอร์ตให้มีประสิทธิภาพดีขึ้นเรื่อยมา งานวิจัยนี้เสนอ ควิกซอร์ตด้วยตัวประชิดตัวหลัก (APQsort) เป็นการปรับปรุงควิกซอร์ตให้มีประสิทธิภาพดีขึ้นสำหรับข้อมูลที่มีสมาชิกซ้ำกัน โดยการลดจำนวนครั้งที่เรียกฟังก์ชันเวียนเกิด APQsort ใช้ประโยชน์จากตัวนำหน้าตัวหลักหรือตัวตามหลังตัวหลัก ร่วมกับการแบ่งกั้นข้อมูลแบบสปลิตเอ็นสำหรับจัดการกับข้อมูลที่มีสมาชิกซ้ำกัน โดยเพิ่มการเก็บสมาชิกที่มีค่าเท่ากับตัวนำหน้าตัวหลักหรือตัวตามหลังตัวหลัก แทนการเก็บเพียงสมาชิกที่มีค่าเท่ากับตัวหลัก และ APQsort สามารถตรวจสอบการเรียงลำดับของข้อมูลย่อยได้โดยพิจารณาจากตัวชี้ของตัวนำหน้าตัวหลักหรือตัวตามหลังตัวหลัก การทดสอบประสิทธิภาพของ APQsort ใช้ข้อมูลสี่แบบ ได้แก่ ข้อมูลแบบสุ่ม ข้อมูลที่เกือบเรียงลำดับ ข้อมูลที่เกือบเรียงลำดับแบบย้อนกลับ และข้อมูลแบบสุ่มที่มีสมาชิกซ้ำกัน โดยนำมาเปรียบเทียบกับ Mergesort Heapsort Quicksort (ควิกซอร์ตดั้งเดิม) qsort ซึ่งเป็นควิกซอร์ตที่ใช้การแบ่งกั้นข้อมูลแบบสปลิตเอ็น และ SWQuicksort ซึ่งเป็นขั้นตอนวิธีที่ปรับปรุงมาจากควิกซอร์ต จากการทดลองพบว่า APQsort ประมวลผลได้เร็วกว่า Mergesort Heapsort Quicksort qsort และ SWQuicksort สำหรับข้อมูลแบบสุ่มที่มีสมาชิกซ้ำกันเป็นจำนวนมาก และข้อมูลเรียงลำดับหรือข้อมูลเรียงลำดับแบบย้อนกลับ	en
dc.description.abstractalternative	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	en
dc.format.extent	1332569 bytes	-
dc.format.mimetype	application/pdf	-
dc.language.iso	th	es
dc.publisher	จุฬาลงกรณ์มหาวิทยาลัย	en
dc.relation.uri	http://doi.org/10.14457/CU.the.2009.295	-
dc.rights	จุฬาลงกรณ์มหาวิทยาลัย	en
dc.subject	การเรียงลำดับ (คอมพิวเตอร์)	en
dc.title	การปรับปรุงควิกซอร์ตด้วยตัวนำหน้าและตัวตามหลังของตัวหลัก	en
dc.title.alternative	Improvement of quicksort with predecessor and successor of pivot	en
dc.type	Thesis	es
dc.degree.name	วิทยาศาสตรมหาบัณฑิต	es
dc.degree.level	ปริญญาโท	es
dc.degree.discipline	วิทยาการคณนา	es
dc.degree.grantor	จุฬาลงกรณ์มหาวิทยาลัย	en
dc.email.advisor	krung@math.sc.chula.ac.th	-
dc.identifier.DOI	10.14457/CU.the.2009.295	-
Appears in Collections:	Sci - Theses

Files in This Item:

File	Description	Size	Format
Siwat_ru.pdf		1.3 MB	Adobe PDF	View/Open

Show simple item record