ควิกซอร์ต (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) รวมทั้งแถวลำดับที่ช่วยในการเรียงอีกเท่าตัว

อ้างอิง แก้

  1. "Sir Antony Hoare". Computer History Museum. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 3 April 2015. สืบค้นเมื่อ 22 April 2015.
  2. Hoare, C. A. R. (1961). "Algorithm 64: Quicksort". Comm. ACM. 4 (7): 321. doi:10.1145/366622.366644.
  3. Skiena, Steven S. (2008). The Algorithm Design Manual. Springer. p. 129. ISBN 978-1-84800-069-8.