DAA - Sắp xếp nhanh

Nó được sử dụng theo nguyên tắc chia để trị. Sắp xếp nhanh là một thuật toán được lựa chọn trong nhiều trường hợp vì nó không khó thực hiện. Đây là một kiểu sắp xếp có mục đích chung tốt và nó tiêu tốn ít tài nguyên hơn trong quá trình thực thi.

Ưu điểm

Nó ở đúng vị trí vì nó chỉ sử dụng một ngăn xếp phụ trợ nhỏ.
Nó chỉ yêu cầu n (log n) thời gian để sắp xếp n mặt hàng.
Nó có một vòng lặp bên trong cực kỳ ngắn.
Thuật toán này đã được phân tích toán học kỹ lưỡng, một tuyên bố rất chính xác có thể được đưa ra về các vấn đề hiệu suất.

Nhược điểm

Nó là đệ quy. Đặc biệt, nếu không có đệ quy thì việc thực hiện vô cùng phức tạp.
Nó yêu cầu thời gian bậc hai (tức là n2) trong trường hợp xấu nhất.
Nó rất dễ hỏng, tức là một sai lầm đơn giản trong quá trình thực hiện có thể không được chú ý và khiến nó hoạt động không tốt.

Sắp xếp nhanh hoạt động bằng cách phân vùng một mảng nhất định A[p ... r] thành hai mảng con không trống A[p ... q] và A[q+1 ... r] sao cho mọi chìa khóa trong A[p ... q] nhỏ hơn hoặc bằng mọi khóa trong A[q+1 ... r].

Sau đó, hai mảng con được sắp xếp bằng các lệnh gọi đệ quy để Sắp xếp nhanh. Vị trí chính xác của phân vùng phụ thuộc vào mảng và chỉ mục nhất địnhq được tính như một phần của thủ tục phân vùng.

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)

Lưu ý rằng để sắp xếp toàn bộ mảng, lệnh gọi ban đầu phải là Quick-Sort (A, 1, length[A])

Bước đầu tiên, Sắp xếp Nhanh chọn một trong các mục trong mảng để được sắp xếp theo trục xoay. Sau đó, mảng được phân vùng ở hai bên của trục. Các phần tử nhỏ hơn hoặc bằng pivot sẽ di chuyển về phía bên trái, trong khi các phần tử lớn hơn hoặc bằng pivot sẽ di chuyển sang bên phải.

Phân vùng mảng

Thủ tục phân vùng sắp xếp lại các mảng con tại chỗ.

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

Phân tích

Độ phức tạp trong trường hợp xấu nhất của thuật toán Sắp xếp Nhanh là O(n²). Tuy nhiên, bằng cách sử dụng kỹ thuật này, trong các trường hợp trung bình, chúng ta thường nhận được kết quảO(n log n) thời gian.