Quicksort เป็นการเรียงลำดับแบบแบ่งเพื่อชนะที่เลือก pivot แบ่งองค์ประกอบออกเป็นองค์ประกอบที่เล็กกว่า และใหญ่กว่านั้น จากนั้นเรียงลำดับแต่ละด้านแบบเรียกซ้ำ โดยทั่วไป O(n log n) กรณีที่เลวร้ายที่สุด O(n²)
การแบ่งส่วนวางจุด pivot ในตำแหน่งเรียงลำดับสุดท้าย ทุกอย่างทางซ้ายเล็กกว่า ทุกอย่างทางขวาใหญ่กว่า เรียกซ้ำทั้งสองด้าน
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # pick a pivot
left = [x for x in arr if x < pivot] # smaller
mid = [x for x in arr if x == pivot] # equal
right = [x for x in arr if x > pivot] # larger
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(การแบ่งส่วนในตำแหน่ง (in-place) ใช้ในทางปฏิบัติเพื่อประหยัดหน่วยความจำ)
| กรณี | เวลา | สาเหตุ |
|---|---|---|
| Best/Average | O(n log n) | การแบ่งส่วนแบบสมดุล |
| Worst | O(n²) | เรียงลำดับแล้ว pivot ที่ไม่ดี |
Quicksort ในตำแหน่งใช้พื้นที่ stack O(log n)
มักจะ เร็วที่สุดในทางปฏิบัติ เนื่องจากเป็นมิตรกับแคช และมีค่าใช้จ่ายต่ำ และอยู่ในตำแหน่ง กรณีที่เลวร้ายที่สุด O(n²) หลีกเลี่ยงได้ด้วย pivot แบบสุ่ม หรือ ค่ามัธยฐาน-สาม ไม่ เสถียร
Quicksort เป็นค่าเริ่มต้นในไลบรารีมาตรฐานจำนวนมากเนื่องจากความเร็วของกรณีเฉลี่ยที่ยอดเยี่ยม และการใช้หน่วยความจำต่ำ
การเข้าใจว่าเหตุใดการเลือก pivot จึงทำให้เกิดกรณีที่เลวร้ายที่สุด O(n²) เป็นการสอนบทเรียนสำคัญ: กรณีเฉลี่ยและที่เลวร้ายที่สุดสามารถแตกต่างกันอย่างมาก
มันเป็นหัวข้อการสัมภาษณ์ที่เป็นที่ชื่นชอบก็เพราะเหตุนี้แหละ