Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Một lượt phân hoạch
- ChọnLấy một phần tử làm mốc, gọi là pivot
- Đẩy tráiSố nhỏ hơn pivot dồn sang bên trái
- Đẩy phảiSố lớn hơn pivot dồn sang bên phải
- LặpLàm lại đúng như vậy với từng phía
Pivot quyết định nhanh hay chậm
Pivot chia mảng thành hai phía. Chia càng cân thì càng ít tầng đệ quy, và thuật toán càng nhanh. Chia lệch thì một phía gần như không nhỏ đi, nên số tầng tăng vọt.
Chia cân thì n log n, chia lệch mọi lần thì n²
Trường hợp làm quick sort sập
Mảng đã sắp xếp sẵn, cộng với cách chọn pivot là phần tử đầu tiên. Mỗi lần chia đều lệch hết cỡ, và quick sort rơi xuống n². Đó là lý do không thư viện nào chọn kiểu đó.
Thư viện không dùng quick sort thuần
C++, Go và Rust dùng introsort hoặc pdqsort. Chúng bắt đầu như quick sort, nhưng khi đệ quy quá sâu thì đổi sang heap sort. Nhờ vậy trường hợp xấu nhất không còn là n².
Sắp xếp ổn định thì Python và Java đi nhánh merge sort
Quick sort được gì, mất gì
Ưu điểm
Mảng ngẫu nhiên thì nhanh nhất trên thực tế
Sắp xếp tại chỗ, đệ quy chỉ tốn log n
Là mặc định cho sắp xếp không ổn định
Nhược điểm
Trường hợp xấu nhất vẫn là n²
Không ổn định, hai số bằng nhau có thể đảo
Cài ẩu thì đệ quy sâu, tràn ngăn xếp
Bài sau: heap sort
Chính là cái lưới mà introsort rơi vào khi quick sort đệ quy quá sâu.
