ควิกซอร์ต
ควิกซอร์ต (Quicksort) หรือ การเรียงลำดับแบบรวดเร็ว คือ อัลกอริทึมเรียงลำดับ (sorting algorithm) แบบแทนที่ มีลักษณะเด่นคือ เป็นอัลกอริทึมแบบแบ่งแยกและเอาชนะ (divide and conquer) ในการจัดเรียง คิดค้นขึ้นในปี ค.ศ. 1959 โดยนักวิทยาศาสตร์คอมพิวเตอร์ชาวบริเตน โทนี ฮอร์ (Tony Hoare)[1] และตีพิมพ์ในปี ค.ศ. 1961[2] ควิกซอร์ตเป็นอัลกอรึทึมสำหรับการจัดเรียงที่ใช้งานทั่วไป ในการใช้งานจริง ควิกซอร์ตมีความเร็วในการจัดเรียงเร็วกว่า เมิร์จซอร์ต (Merge sort) และ เร็วกว่าฮีพซอร์ต (Heapsort) ซึ่งใช้โครงสร้างข้อมูลแบบฮีพ (Heap) 2 ถึง 3 เท่า[3]
 อนิเมชั่นอัลกอริธึมควิกซอร์ต (Quicksort) ที่จัดเรียงอาร์เรย์แบบสุ่ม แถบสีแดงคือจุดหมุน (Pivot) ในช่วงเริ่มต้น องค์ประกอบที่อยู่ทางด้านขวามือสุดจะถูกเลือกเป็นจุดหมุน | |
| ประเภท | ขั้นตอนวิธีการเรียงลำดับ |
|---|---|
| โครงสร้างข้อมูล | แถวลำดับ (Array) |
| ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | O(n log n) |
| ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด | O(n log n) โดยทั่วไป O(n) เมื่อใส่เงื่อนไขพิเศษ |
| ประสิทธิภาพเมื่อเกิดกรณีทั่วไป | O(n log n) |
| ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด | O(n) รวมทั้งแถวลำดับที่ช่วยในการเรียงอีกเท่าตัว |
อ้างอิง
แก้- ↑ "Sir Antony Hoare". Computer History Museum. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 3 April 2015. สืบค้นเมื่อ 22 April 2015.
- ↑ Hoare, C. A. R. (1961). "Algorithm 64: Quicksort". Comm. ACM. 4 (7): 321. doi:10.1145/366622.366644.
- ↑ Skiena, Steven S. (2008). The Algorithm Design Manual. Springer. p. 129. ISBN 978-1-84800-069-8.