Sắp xếp nhanh¶

Sắp xếp nhanh (quick sort) là một thuật toán sắp xếp hiệu quả và được sử dụng rộng rãi dựa trên chiến lược chia để trị.

Thao tác cốt lõi của sắp xếp nhanh là "phân hoạch lính canh" (sentinel partitioning), với mục tiêu là chọn một phần tử làm "chốt" (pivot), di chuyển tất cả các phần tử nhỏ hơn chốt sang bên trái của nó và di chuyển tất cả các phần tử lớn hơn chốt sang bên phải của nó. Cụ thể, quy trình này được mô tả trong hình dưới đây.

Chọn phần tử ngoài cùng bên trái làm chốt, và khởi tạo hai con trỏ i và j ở hai đầu của mảng.
Bắt đầu vòng lặp. Trong mỗi vòng, sử dụng i (j) để tìm phần tử đầu tiên lớn hơn (nhỏ hơn) chốt, rồi hoán đổi hai phần tử này.
Lặp lại bước 2. cho đến khi i và j gặp nhau, sau đó hoán đổi chốt vào vị trí ranh giới giữa hai mảng con.

Sau khi phân hoạch lính canh, mảng ban đầu được chia thành ba phần: mảng con bên trái, chốt, và mảng con bên phải, sao cho "bất kỳ phần tử nào ở mảng con bên trái \(\leq\) chốt \(\leq\) bất kỳ phần tử nào ở mảng con bên phải". Do đó, tiếp theo chúng ta chỉ cần sắp xếp hai mảng con này.

Chiến lược chia để trị của sắp xếp nhanh

Bản chất của phân hoạch lính canh là đơn giản hóa bài toán sắp xếp một mảng dài thành bài toán sắp xếp hai mảng ngắn hơn.

[file]{quick_sort}-[class]{quick_sort}-[func]{partition}

Quy trình thuật toán¶

Quy trình tổng thể của sắp xếp nhanh được thể hiện trong hình dưới đây.

Đầu tiên, thực hiện một lần "phân hoạch lính canh" trên mảng ban đầu để thu được mảng con bên trái và mảng con bên phải chưa được sắp xếp.
Sau đó, thực hiện đệ quy "phân hoạch lính canh" lần lượt trên mảng con bên trái và mảng con bên phải.
Tiếp tục đệ quy cho đến khi độ dài mảng con bằng 1, tại thời điểm đó việc sắp xếp toàn bộ mảng hoàn tất.

[file]{quick_sort}-[class]{quick_sort}-[func]{quick_sort}

Đặc điểm của thuật toán¶

Độ phức tạp thời gian là \(O(n \log n)\), sắp xếp không thích ứng: Trung bình, phân hoạch lính canh tạo ra \(\log n\) tầng đệ quy, và tổng số lần lặp vòng lặp ở mỗi tầng là \(n\), do đó độ phức tạp thời gian tổng thể là \(O(n \log n)\). Trong trường hợp xấu nhất, mỗi vòng phân hoạch lính canh chia mảng có độ dài \(n\) thành các mảng con có độ dài \(0\) và \(n - 1\). Độ sâu đệ quy khi đó đạt tới \(n\), với \(n\) lần lặp vòng lặp ở mỗi tầng, dẫn đến độ phức tạp thời gian tổng thể là \(O(n^2)\).
Độ phức tạp không gian là \(O(n)\), sắp xếp tại chỗ: Trong trường hợp mảng đầu vào bị đảo ngược hoàn toàn, độ sâu đệ quy xấu nhất đạt tới \(n\), sử dụng \(O(n)\) không gian khung ngăn xếp (stack frame space). Thao tác sắp xếp được thực hiện trực tiếp trên mảng ban đầu mà không cần sự trợ giúp của mảng bổ sung.
Sắp xếp không ổn định: Trong bước cuối cùng của phân hoạch lính canh, chốt có thể bị hoán đổi sang bên phải của một phần tử bằng nó.

Tại sao sắp xếp nhanh lại nhanh?¶

Đúng như tên gọi của nó, sắp xếp nhanh có những ưu thế rõ rệt về hiệu quả. Mặc dù độ phức tạp thời gian trung bình của nó tương đương với "sắp xếp trộn" (merge sort) và "sắp xếp vun đống" (heap sort), nhưng sắp xếp nhanh thường chạy nhanh hơn trong thực tế vì các lý do sau.

Trường hợp xấu nhất rất ít khi xảy ra: Mặc dù độ phức tạp thời gian trong trường hợp xấu nhất của sắp xếp nhanh là \(O(n^2)\) và hiệu suất của nó khó dự đoán hơn so với sắp xếp trộn, nhưng sắp xếp nhanh vẫn chạy với thời gian \(O(n \log n)\) trong phần lớn các trường hợp.
Hiệu suất bộ nhớ đệm (cache) cao: Trong quá trình phân hoạch lính canh, hệ thống có thể nạp toàn bộ mảng con vào bộ nhớ đệm, do đó việc truy cập các phần tử diễn ra tương đối hiệu quả. Ngược lại, các thuật toán như "sắp xếp vun đống" yêu cầu truy cập không liên tục các phần tử và vì vậy không có được lợi thế này.
Hệ số hằng số nhỏ: Trong ba thuật toán trên, sắp xếp nhanh thực hiện ít phép so sánh, phép gán và hoán đổi nhất trên tổng thể. Điều này tương tự như lý do tại sao "sắp xếp chèn" nhanh hơn "sắp xếp nổi bọt".

Tối ưu hóa chọn chốt¶

Sắp xếp nhanh có thể trở nên kém hiệu quả về thời gian đối với một số dữ liệu đầu vào nhất định. Hãy cân nhắc một ví dụ cực đoan khi mảng đầu vào được sắp xếp theo thứ tự giảm dần hoàn toàn. Vì chúng ta chọn phần tử ngoài cùng bên trái làm chốt, sau khi hoàn thành phân hoạch lính canh, chốt sẽ được hoán đổi về phía ngoài cùng bên phải của mảng, để lại mảng con bên trái có độ dài \(n - 1\) và mảng con bên phải có độ dài \(0\). Nếu quá trình này tiếp tục đệ quy, mỗi vòng phân hoạch lính canh sẽ tạo ra một mảng con có độ dài \(0\), chiến lược chia để trị bị phá vỡ, và sắp xếp nhanh sẽ thoái hóa thành một thuật toán gần giống với "sắp xếp nổi bọt".

Để giảm thiểu khả năng xảy ra điều này, chúng ta có thể tối ưu hóa chiến lược chọn chốt được sử dụng trong phân hoạch lính canh. Ví dụ, chúng ta có thể chọn ngẫu nhiên một chốt. Tuy nhiên, nếu không may mắn chọn phải các chốt tồi liên tục, hiệu suất vẫn có thể không đạt yêu cầu.

Cần lưu ý rằng các ngôn ngữ lập trình thường tạo ra "số giả ngẫu nhiên" (pseudo-random numbers). Nếu chúng ta xây dựng một trường hợp kiểm thử đặc biệt nhắm vào chuỗi giả ngẫu nhiên này, sắp xếp nhanh vẫn có thể bị suy giảm hiệu suất.

Để cải thiện hơn nữa, chúng ta có thể chọn ba phần tử ứng viên từ mảng, thường là phần tử đầu tiên, phần tử cuối cùng và phần tử ở giữa, và sử dụng trung vị (median) của ba phần tử này làm chốt. Điều này làm tăng đáng kể cơ hội chọn được chốt "không quá nhỏ cũng không quá lớn". Chúng ta cũng có thể chọn nhiều phần tử ứng viên hơn để tăng cường hơn nữa tính bền vững (robustness) của thuật toán. Với phương pháp này, xác suất độ phức tạp thời gian bị thoái hóa về \(O(n^2)\) giảm đi đáng kể.

Mã nguồn ví dụ như sau:

[file]{quick_sort}-[class]{quick_sort_median}-[func]{partition}

Tối ưu hóa độ sâu đệ quy¶

Sắp xếp nhanh cũng có thể sử dụng nhiều không gian hơn đối với một số dữ liệu đầu vào nhất định. Hãy cân nhắc một mảng đầu vào đã được sắp xếp hoàn toàn. Giả sử độ dài của mảng con hiện tại trong đệ quy là \(m\). Mỗi vòng phân hoạch lính canh tạo ra một mảng con bên trái có độ dài \(0\) và một mảng con bên phải có độ dài \(m - 1\), nghĩa là mỗi lời gọi đệ quy chỉ giảm kích thước bài toán đi một phần tử. Cây đệ quy do đó có thể đạt tới chiều cao \(n - 1\), yêu cầu \(O(n)\) không gian khung ngăn xếp (stack frame space).

Để ngăn các khung ngăn xếp tích tụ, chúng ta có thể so sánh độ dài của hai mảng con sau mỗi vòng phân hoạch lính canh, và chỉ thực hiện gọi đệ quy trên mảng con ngắn hơn. Vì mảng con ngắn hơn có độ dài tối đa là \(n / 2\), phương pháp này đảm bảo độ sâu đệ quy không vượt quá \(\log n\), giảm độ phức tạp không gian trong trường hợp xấu nhất xuống còn \(O(\log n)\). Mã nguồn được hiển thị dưới đây:

[file]{quick_sort}-[class]{quick_sort_tail_call}-[func]{quick_sort}