Sắp xếp nhanh

Sắp xếp nhanh là một trong những thuật toán sắp xếp được dùng nhiều nhất. Nó chọn một chốt, chia danh sách thành các giá trị nhỏ hơn chốt và phần còn lại, rồi sắp xếp hai bên theo cùng cách. Nó nhanh trong thực tế và không cần danh sách phụ, nhưng nhanh đến đâu còn tùy vào chốt.

Các cột được phân hoạch quanh cột chốt: cột nhỏ hơn ở một bên, cột lớn hơn ở bên kia, chốt nằm giữa
Các cột được phân hoạch quanh cột chốt: cột nhỏ hơn ở một bên, cột lớn hơn ở bên kia, chốt nằm giữa

Ý tưởng

Chọn một giá trị làm chốt. Sắp xếp lại danh sách sao cho mọi giá trị nhỏ hơn chốt đứng trước nó và mọi giá trị khác đứng sau. Việc sắp xếp lại đó gọi là phân hoạch, và nó đặt chốt đúng vào vị trí của chốt trong danh sách đã sắp xếp. Hai bên giờ là hai bài toán độc lập: sắp xếp từng bên bằng sắp xếp nhanh. Một bên chỉ có một giá trị hoặc không có giá trị nào thì đã được sắp xếp.

Phân hoạch, từng bước

Ứng dụng dùng phân hoạch Lomuto. Chốt được chuyển về cuối phần. Một điểm đánh dấu bắt đầu từ đầu phần: mọi giá trị trước nó đều nhỏ hơn chốt. Mỗi giá trị khác được so sánh với chốt; nếu nhỏ hơn, nó được hoán đổi đến điểm đánh dấu và điểm đánh dấu tiến thêm một vị trí. Cuối cùng, chốt được hoán đổi đến điểm đánh dấu. Lấy 5, 1, 4, 2, 8 với giá trị cuối làm chốt: cả bốn giá trị đều nhỏ hơn 8, nên 8 ở lại cuối. Phần 5, 1, 4, 2 được phân hoạch quanh 2, cho ra 1, 2, 4, 5, và 4, 5 quanh 5. Tổng cộng 8 phép so sánh, 2 lần hoán đổi và 3 lần phân hoạch.

Chốt tốt và chốt tồi

Nếu mọi chốt đều rơi vào giữa, mỗi lần phân hoạch sẽ chia đôi bài toán, và cần khoảng n log₂ n phép so sánh. Trên danh sách ngẫu nhiên, chốt hiếm khi hoàn hảo nhưng thường đủ tốt: với 40 giá trị ngẫu nhiên, ứng dụng đếm được khoảng 190 phép so sánh. Trường hợp xấu nhất xảy ra khi chốt luôn là giá trị nhỏ nhất hoặc lớn nhất. Khi lấy giá trị cuối làm chốt, danh sách đã sắp xếp sẵn, hoặc đảo ngược, gây ra đúng điều đó: mỗi lần phân hoạch chỉ loại được chính chốt, và cần n(n − 1)/2 phép so sánh, tức 780 với 40 giá trị.

Chọn chốt

Chốt ngẫu nhiên khiến trường hợp xấu nhất cực kỳ khó xảy ra với mọi đầu vào, vì không thứ tự cụ thể nào đánh lừa được nó. Trung vị của ba, tức giá trị ở giữa của phần tử đầu, giữa và cuối, rẻ để tính và xử lý tốt cả danh sách đã sắp xếp lẫn đảo ngược. Thử cả hai trên danh sách đã sắp xếp trong ứng dụng, số phép so sánh giảm từ 780 xuống khoảng 150. Nhiều giá trị bằng nhau là một vấn đề khác: chúng đều rơi về một phía của chốt. Phân hoạch ba phần, giữ các giá trị bằng chốt ở phần giữa, khắc phục được điều đó.

Lịch sử và ứng dụng

Tony Hoare phát minh sắp xếp nhanh năm 1959 và công bố năm 1961. Cách phân hoạch của chính ông quét từ hai đầu và ít hoán đổi hơn; phiên bản Lomuto đơn giản hơn được trình bày ở đây trở nên phổ biến nhờ sách giáo khoa. Sắp xếp nhanh sắp xếp tại chỗ và vòng lặp trong rất ngắn, nên trong thực tế thường nhanh hơn sắp xếp trộn, dù không ổn định. Introsort, thuật toán sắp xếp đằng sau thư viện chuẩn C++, chạy sắp xếp nhanh và chuyển sang sắp xếp vun đống nếu các lần phân hoạch quá lệch, nên trường hợp xấu nhất vẫn là n log n.

Tony Hoare, người phát minh sắp xếp nhanh năm 1959 và công bố năm 1961.
Tony Hoare, người phát minh sắp xếp nhanh năm 1959 và công bố năm 1961.

Khám phá

Mở ứng dụng và nhấn Bước. Phần đang phân hoạch được tô bóng, chốt có màu riêng, và đường nét đứt đánh dấu cuối phần bên trái, tức các giá trị nhỏ hơn chốt. Mỗi chốt chuyển sang màu xanh lá khi đến vị trí cuối cùng. Chọn danh sách đã sắp xếp và lấy giá trị cuối làm chốt, rồi chuyển sang trung vị của ba, và so sánh các bộ đếm.

Câu hỏi thường gặp

Độ phức tạp thời gian của sắp xếp nhanh là bao nhiêu?

O(n log n) trung bình và khi chốt tốt, O(n²) trong trường hợp xấu nhất. Nó sắp xếp tại chỗ; đệ quy cần thêm O(log n) bộ nhớ nếu sắp xếp bên nhỏ hơn trước.

Phân hoạch Lomuto và Hoare khác nhau thế nào?

Lomuto dùng một điểm đánh dấu và quét từ trái sang phải, dễ theo dõi và là cách ứng dụng này trình bày. Hoare quét từ hai đầu về phía nhau và hoán đổi các cặp nằm sai bên, nên trung bình số lần hoán đổi ít hơn khoảng ba lần.

Vì sao sắp xếp nhanh chậm khi có nhiều giá trị bằng nhau?

Các giá trị bằng chốt đều đi về cùng một bên, nên danh sách có ít giá trị khác nhau bị chia lệch, và danh sách toàn giá trị bằng nhau tệ như trường hợp xấu nhất. Phân hoạch ba phần gom các giá trị bằng chốt vào giữa sẽ tránh được điều đó.

Sắp xếp nhanh có ổn định không?

Không. Các lần hoán đổi trong phân hoạch di chuyển giá trị qua khoảng cách xa, nên các giá trị bằng nhau có thể đổi thứ tự.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Thử sắp xếp nhanh