ควิกซอร์ต

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

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

อ้างอิง[แก้]

  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.