Tổng quan
Cocktail Shaker Sort là biến thể hai chiều của Bubble Sort. Nó đẩy phần tử lớn nhất về cuối trong lượt trái-sang-phải, rồi đẩy phần tử nhỏ nhất về đầu trong lượt phải-sang-trái, luân phiên đến khi sắp xong.
Cocktail Shaker Sort hoạt động thế nào?
- Duyệt trái-sang-phải, hoán đổi các cặp liền kề sai thứ tự để phần tử lớn nhất về cuối.
- Duyệt phải-sang-trái, làm tương tự để phần tử nhỏ nhất về đầu.
- Thu hẹp đoạn đang xét từ cả hai đầu sau mỗi lượt.
- Dừng ngay khi một lượt không có hoán đổi nào.
Khi nào nên dùng?
- Chủ yếu để giảng dạy — minh họa cách lượt hai chiều xử lý 'rùa' của Bubble Sort (giá trị nhỏ nằm gần cuối).
- Mảng nhỏ hoặc gần như đã sắp, như các sort bậc hai đơn giản khác.
Phân tích độ phức tạp
Giống Bubble Sort, nó O(n²) ở trung bình và xấu nhất, và O(n) với đầu vào đã sắp. Việc quét hai chiều giảm số lượt trong thực tế nhưng không đổi lớp tiệm cận. Nó tại chỗ và ổn định.
Câu hỏi thường gặp
Cocktail Sort hơn Bubble Sort ở điểm gì?
Nhờ quét cả hai chiều, nó nhanh chóng đưa các giá trị nhỏ mắc kẹt gần cuối ('rùa') về trước, nên thường cần ít lượt hơn — dù cả hai vẫn O(n²).