ควิกซอร์ต

ควิกซอร์ต (Quicksort) หรือ การเรียงลำดับแบบรวดเร็ว คือ อัลกอริทึมเรียงลำดับ (sorting algorithm) แบบแทนที่ มีลักษณะเด่นคือ เป็นอัลกอริทึมแบบแบ่งแยกและเอาชนะ (divide and conquer) ในการจัดเรียง คิดค้นขึ้นในปี ค.ศ. 1959 โดยนักวิทยาศาสตร์คอมพิวเตอร์ชาวบริเตน โทนี ฮอร์ (Tony Hoare) และตีพิมพ์ในปี ค.ศ. 1961 ควิกซอร์ตเป็นอัลกอรึทึมสำหรับการจัดเรียงที่ใช้งานทั่วไป ในการใช้งานจริง ควิกซอร์ตมีความเร็วในการจัดเรียงเร็วกว่า เมิร์จซอร์ต (Merge sort) และ เร็วกว่า (Heapsort) ซึ่งใช้โครงสร้างข้อมูลแบบฮีพ (Heap) 2 ถึง 3 เท่า

ควิกซอร์ต

อนิเมชั่นอัลกอริธึมควิกซอร์ต (Quicksort) ที่จัดเรียงอาร์เรย์แบบสุ่ม แถบสีแดงคือจุดหมุน (Pivot) ในช่วงเริ่มต้น องค์ประกอบที่อยู่ทางด้านขวามือสุดจะถูกเลือกเป็นจุดหมุน
ประเภท	ขั้นตอนวิธีการเรียงลำดับ
โครงสร้างข้อมูล	แถวลำดับ (Array)
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด	O(n log n)
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด	O(n log n) โดยทั่วไป O(n) เมื่อใส่เงื่อนไขพิเศษ
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป	O(n log n)
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด	O(n) รวมทั้งแถวลำดับที่ช่วยในการเรียงอีกเท่าตัว

อ้างอิง

1. . Computer History Museum. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 3 April 2015. สืบค้นเมื่อ 22 April 2015.
2. (1961). "Algorithm 64: Quicksort". . 4 (7): 321. doi:10.1145/366622.366644.
3. (2008). The Algorithm Design Manual. Springer. p. 129. ISBN .