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) เวลา.