Algorithm: Thuật toán sắp xếp nhanh (quick sort)

Hình động cảu thuật toán sắp xếp nhanh

Các thuật toán như sắp xếp nổi bọt, chèn và chọn đều có độ phức tạp trung bình về thời gian là O(n²). Với thuật toán sắp xếp nhanh trong trường hợp xuất nhất (khi danh sách đầu vào đã được sắp xếp rồi) thì độ phức tạp về thời gian sẽ là O(n²) còn trong trường hợp trung bình thì độ phức tạp về thời gian của nó là O(nlogn). Như vậy, trong các tình huống sắp xếp thông thường ta sẽ chọn thuật toán sắp xếp nhanh để cài đặt cho bài toán sắp xếp của mình. Quick sort cũng là một thuật toán đặc trưng của tư tưởng chia để trị.
Ý tưởng của thuật toán sắp xếp nhanh rất đơn giản. Gồm các bước sau:

1. Chọn một phần tử trong danh sách, phần tử này được gọi là chốt
2. Chuyển tất cả các phần tử nhỏ hơn chốt về bên trái (đầu danh sách) và lớn hơn chốt về bên phải (cuối danh sách).
3. Lúc này, danh sách ban đầu sẽ được chia thành hai phần, ta lặp lại thuật toán cho mỗi phần. Như vậy, phần bên trái gồm các số bé hơn hoặc bằng chốt và phần bên phải gồm các số lớn hơn hoặc bằng chốt. Khi hai phần này được sắp xếp theo cung chiều thì danh sách ban đầu cũng được sắp.

Ta sẽ thử hiện các bước của thuật toán sắp xếp nhanh với danh sách ví dụ sau:

a=[3, 6, 9, 2, 6, 8, 9, 1, 7, 21, 7, 12]

Với ý tưởng của thuật toán như trên, bước thứ nhất là ta sẽ chọn chốt. Chốt sẽ được chọn như thế nào? Thực sự là có rất nhiều cách, chỉ cần chọn một phần tử bất kỳ trong danh sách là được, có thể là phần tử đầu tiên, cuối cùng, giữa danh sách,... Trong ví dụ này, mình sẽ chọn phần tử nằm giữa danh sách. Các bước của thuật toán trên như sau:

1. Với danh sách ban đầu, chỉ số đầu danh sách sIndex = 0 và chỉ số cuối dãy là eIndex=11 (do danh sách có 12 phần tử). Ta chọn phần tử chốt là pivot = a[(sIndex + endIndex) / 2] (= a[5] lúc này pivot = 8 nhé).
2. Gán hai chỉ số mới i = sIndex và j = eIndex và cho i chạy từ trái sang phải, j chạy theo chiều ngược lại. Nếu phát hiện được a[i] > pivot và a[j] < pivot thì đổi chỗ cho nhau và chạy tiếp.
3. Ta thấy với i = 2 (a[2] = 9 > pivot (=8) và a[10] = 7 < pivot (=8) nên ta sẽ đổi chỗ hai phần tử này cho nhau. Danh sách thu được lúc này là:
   a=[3, 6, 7, 2, 6, 8, 9, 1, 7, 21, 9, 12]
4. Tiếp tục cho i chạy sang trái và j chạy sang phải, lại phát hiện a[5] = 8 >= pivot (=8) và a[8] = 7 < pivot (=8) lại tiếp tục đổi chỗ hai phần tử này ta được danh sách mới như sau:
   a=[3, 6, 7, 2, 6, 7, 9, 1, 8, 21, 9, 12]
5. Tiếp tục như bước 4 ta thấy, a[6] = 9 > pivot (=8) và a[7] = 1 < pivot(=8) nên một lần nữa ta đổi chỗ hai phần tử này cho nhau và được danh sách như sau:
   a=[3, 6, 7, 2, 6, 7, 1, 9, 8, 21, 9, 12]
6. Bước tiếp theo này, ta sex tăng chỉ số của i lên và thấy chỉ số i = j nên rõ ràng tại ví trí này các phần tử bên trái là nhỏ hơn hoặc bằng pivot và các phần tử bên phải danh sách thì lớn hơn hoặc bằng pivot. Lúc này ta sẽ quyết định chi danh sách thành hai danh sách con và thực hiện thuật toán lại từ đầu với từng danh sách con. Các trường hợp được phân chia như sau:
1. Nếu i == j và a[i] <= pivot thì chia thành hai danh sách con gồm danh sách thứ nhất từ sIndex đến i và danh sách thứ hai từ i+1 đến eIndex.
2. Nếu i == j và a[i] > pivot thì danh sách thứ nhất từ sIndex đến i - 1 và từ i đến eIndex cho danh sách thứ hai.
3. Trường hợp còn lại là i != j (chắc chắn là j < i) thì sẽ chia thành hai danh sách là từ sIndex đện j cho danh sách thứ nhất và từ i đến eIndex cho danh sách hai.
7. Thực hiện lại thuật toán cho các danh sách đã được chia ở bước 6. Kết thúc thuật toán thì dãy ban đầu đã được sắp.

Dưới đây là mã nguồn Python:

Mã nguồn C (phiên bản con trỏ)

Ý tưởng của thuật toán sắp xếp nhanh (quick sort) rất đơn giản đúng không? Ở trong các đoạn code trên mình sử dụng các hàm đệ quy, thuật toán sắp xếp nhanh hoàn toàn có thể khử đệ quy được (coi như bài tập về nhà nhé).

Mã nguồn đầy đủ ở đây (python, c language).