DAA - จัดเรียงด่วน
ใช้กับหลักการแบ่งแยกและพิชิต การเรียงลำดับด่วนเป็นอัลกอริทึมที่สามารถเลือกใช้ได้ในหลายสถานการณ์เนื่องจากไม่ยากที่จะนำไปใช้ เป็นการจัดเรียงตามวัตถุประสงค์ทั่วไปที่ดีและใช้ทรัพยากรน้อยกว่าในระหว่างการดำเนินการ
ข้อดี
อยู่ในสถานที่เนื่องจากใช้สแต็กเสริมขนาดเล็กเท่านั้น
ต้องใช้เท่านั้น n (log n) ถึงเวลาจัดเรียง n รายการ
มีวงในที่สั้นมาก
อัลกอริทึมนี้อยู่ภายใต้การวิเคราะห์ทางคณิตศาสตร์อย่างละเอียดสามารถระบุคำแถลงที่แม่นยำมากเกี่ยวกับปัญหาด้านประสิทธิภาพ
ข้อเสีย
เป็นแบบวนซ้ำ โดยเฉพาะอย่างยิ่งหากไม่มีการเรียกซ้ำการใช้งานจะซับซ้อนมาก
ต้องใช้เวลากำลังสอง (เช่น n2) ในกรณีที่เลวร้ายที่สุด
มีความเปราะบางกล่าวคือความผิดพลาดง่ายๆในการใช้งานอาจไม่มีใครสังเกตเห็นและทำให้เกิดการทำงานที่ไม่ดี
การเรียงลำดับด่วนทำงานโดยการแบ่งพาร์ติชันอาร์เรย์ที่กำหนด A[p ... r] ออกเป็นสองอาร์เรย์ย่อยที่ไม่ว่างเปล่า A[p ... q] และ A[q+1 ... r] เพื่อให้ทุกคีย์เข้า A[p ... q] น้อยกว่าหรือเท่ากับทุกคีย์ใน A[q+1 ... r].
จากนั้นอาร์เรย์ย่อยทั้งสองจะถูกจัดเรียงตามการเรียกซ้ำไปยังการเรียงลำดับด่วน ตำแหน่งที่แน่นอนของพาร์ติชันขึ้นอยู่กับอาร์เรย์และดัชนีที่กำหนดq คำนวณเป็นส่วนหนึ่งของขั้นตอนการแบ่งพาร์ติชัน
Algorithm: Quick-Sort (A, p, r)
if p < r then
q Partition (A, p, r)
Quick-Sort (A, p, q)
Quick-Sort (A, q + r, r)โปรดทราบว่าในการจัดเรียงอาร์เรย์ทั้งหมดการเรียกเริ่มต้นควรเป็น Quick-Sort (A, 1, length[A])
ในขั้นแรก Quick Sort จะเลือกรายการใดรายการหนึ่งในอาร์เรย์ที่จะจัดเรียงเป็นเดือย จากนั้นอาร์เรย์จะถูกแบ่งพาร์ติชันที่ด้านใดด้านหนึ่งของเดือย องค์ประกอบที่น้อยกว่าหรือเท่ากับเดือยจะเคลื่อนที่ไปทางซ้ายในขณะที่องค์ประกอบที่มากกว่าหรือเท่ากับเดือยจะเคลื่อนที่ไปทางขวา
การแบ่งพาร์ติชัน Array
ขั้นตอนการแบ่งพาร์ติชันจะจัดเรียงอาร์เรย์ย่อยในตำแหน่งใหม่
Function: Partition (A, p, r)
x ← A[p]
i ← p-1
j ← r+1
while TRUE do
Repeat j ← j - 1
until A[j] ≤ x
Repeat i← i+1
until A[i] ≥ x
if i < j then
exchange A[i] ↔ A[j]
else
return jการวิเคราะห์
ความซับซ้อนของกรณีที่แย่ที่สุดของอัลกอริทึมการเรียงลำดับด่วนคือ O(n2). อย่างไรก็ตามการใช้เทคนิคนี้โดยเฉลี่ยแล้วเราจะได้ผลลัพธ์เป็นO(n log n) เวลา.