ควิกซอร์ต
ควิกซอร์ต (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) รวมทั้งแถวลำดับที่ช่วยในการเรียงอีกเท่าตัว |
อ้างอิง
🔥 Top keywords: วชิรวิชญ์ ไพศาลกุลวงศ์หน้าหลักองค์การกระจายเสียงและแพร่ภาพสาธารณะแห่งประเทศไทยยูฟ่าแชมเปียนส์ลีกชนกันต์ อาพรสุทธินันธ์สโมสรฟุตบอลแมนเชสเตอร์ซิตีพิเศษ:ค้นหาดวงใจเทวพรหม (ละครโทรทัศน์)กรงกรรมอสมทลิซ่า (แร็ปเปอร์)จีรนันท์ มะโนแจ่มสโมสรฟุตบอลอาร์เซนอลสโมสรฟุตบอลเรอัลมาดริดธี่หยดฟุตซอลชิงแชมป์เอเชีย 2024เฟซบุ๊กสโมสรฟุตบอลบาร์เซโลนาประเทศไทยเอเชียนคัพ รุ่นอายุไม่เกิน 23 ปี 2024วิทยุเสียงอเมริกาสโมสรฟุตบอลลิเวอร์พูลพระราชวัชรธรรมโสภณ (ศิลา สิริจนฺโท)พระบาทสมเด็จพระวชิรเกล้าเจ้าอยู่หัวรักวุ่น วัยรุ่นแสบวันไหลนริลญา กุลมงคลเพชรสโมสรฟุตบอลเชลซีสมเด็จพระกนิษฐาธิราชเจ้า กรมสมเด็จพระเทพรัตนราชสุดาฯ สยามบรมราชกุมารีหลานม่าสุภาพบุรุษจุฑาเทพ (ละครโทรทัศน์)สโมสรฟุตบอลไบเอิร์นมิวนิกกรุงเทพมหานครสโมสรฟุตบอลแมนเชสเตอร์ยูไนเต็ดคิม ซู-ฮย็อนภาวะโลกร้อนสาธุ (ละครโทรทัศน์)รายชื่ออักษรย่อของจังหวัดในประเทศไทยสโมสรฟุตบอลปารีแซ็ง-แฌร์แม็ง