Tổng quan
Shell Sort là dạng tổng quát của Insertion Sort: đầu tiên sắp các phần tử ở xa nhau, rồi giảm dần khoảng cách. Việc di chuyển phần tử đi xa ngay từ sớm giúp nó vượt qua hành vi bậc hai của Insertion Sort thuần.
Shell Sort hoạt động thế nào?
- Chọn một dãy khoảng cách giảm dần (ví dụ n/2, n/4, …, 1).
- Với khoảng cách hiện tại, chạy insertion sort trên các phần tử cách nhau đúng khoảng cách đó.
- Giảm khoảng cách và lặp lại, khiến mảng ngày càng gần được sắp.
- Lượt cuối với khoảng cách 1 là insertion sort thông thường trên mảng gần như đã sắp — nên rất nhanh.
Khi nào nên dùng?
- Mảng cỡ vừa khi cần một thuật toán đơn giản, tại chỗ, không đệ quy.
- Môi trường nhúng hoặc hạn chế, tránh đệ quy của Quick/Merge Sort.
Phân tích độ phức tạp
Độ phức tạp của Shell Sort phụ thuộc vào dãy khoảng cách. Các dãy thông dụng cho khoảng O(n^1.25) đến O(n^1.5); trường hợp xấu nhất với khoảng cách đơn giản là O(n²). Nó tại chỗ và không ổn định, nhưng nhanh hơn nhiều so với Insertion Sort trên đầu vào lớn.
Câu hỏi thường gặp
Dãy khoảng cách có thực sự quan trọng không?
Rất quan trọng. Các dãy được chọn tốt (Hibbard, Sedgewick, Knuth) cải thiện rõ rệt cận xấu nhất so với dãy chia đôi ngây thơ.