Ý tưởng
Shell Sort là phương pháp cải tiến của Insertion Sort.
Phân chia dãy ban đầu thành những dãy con gồm các phần tử cách nhau h vị trí.
Dãy con thứ nhất: a1, ah+1, a2h+1…
Dãy con thứ hai: a2, ah+2, a2h+2…
……..
Dãy con thứ h: ah, a2h, a3h…
Sắp xếp các phần tử trong cùng dãy con sẽ làm cho các phần tử được đưa về vị trí đúng tương đối (so với toàn bộ các phần tử trong dãy ban đầu có thể chưa đúng). Giảm khoảng cách h để tạo các dãy con mới và lại tiếp tục sắp xếp.
Thuật toán dừng khi h = 1, lúc này bảo đảm tất cả các phần tử trong dãy ban đầu đã được so sánh với nhau để xác định trật tự đúng cuối cùng.
Giải thuật
Bước 1: Chọn k khoảng cách h[1], h[2],…, h[k]; i = 1;
Bước 2: Phân chia dãy ban đầu thành các dãy con cách nhau h[i] khoảng cách. Sắp xếp từng dãy con bằng Insertion Sort.
Bước 3: i = i + 1;
Nếu i ≤ k : Lặp lại bước 2
Nếu i > k: Dừng