Tuy nhiên, sắp xếp bằng phương pháp chèn khá chậm ví nó chỉ hoán vị các phần tử kề nhau. Ví dụ, nếu phần tử nhỏ nhất nằm ở cuối mảng, cần thực hiện N lần để đến vị trí cuối cùng của nó. Shellsort là mở rộng đơn giản của sắp xếp bằng phương pháp chèn, phương pháp này đạt được tốc độ bằng cách hoán vị giữa các phần tử ở xa nhau.

Ý tưởng là sắp xếp lại tập tin đẻ cho nó có tính chất là việc lấy mọi phần tử thứ h (bắt đầu bất kỳ vị trí nào) cũng đều cho ra một tập tin đã sắp. Một tập tin như vậy được gọi là sắp theo độ dài bước h. Nói một cách khác, một tập tin được sắp theo độ dài bước h là h tập tin được sắp độc lập, đan xen với nhau. Bằng cách sắp xếp theo độ dài bước h ứng với vài giá trị h khá lớn, chúng ta có thể di chuyển các phần tử ở những khoảng cách xa trong mảng và vì vậy dễ dàng hơn để sắp xếp độ dài bước h cho các giá trị h nhỏ hơn. Dùng thủ tục này cho bất kỳ một dãy cac giá trị của h tận cùng là 1 sẽ cho ra một tập tin đã sắp xong: đây là Shellsort.

Hình ảnh dưới đây sẽ cho thấy thao tác của Shellsort trên tập tin ví dụ ứng dụng với các bước 13, 4, 1.

Trong lần lặp đầu tiên, A ở vị trí 1 được so sánh với L ở vị trí 14, sau đó S ở vị trí 2 được so sánh (và hoán vị) với E ở vị trí 15. Trong lần lặp thứ hai, A T E P ở vị trí 1, 5, 9 và 13 được sắp xếp lại để đặt A E P T vào các vị trí đó, và tương tự cho các vị trí 1, 6, 10 và 14,…Lần lặp cuối chỉ là sắp bằng chèn, nhưng không có phần tử nào phải dời chuyển rất xa.

Một cách để cài đặt Shellsort là: ứng với mỗi giá trị h, sử dụng chèn trực tiếp một cách độc lập trên từng tập tin trong số h tập tin con (Phần tử cầm canh sẽ không được dùng vì đó sẽ phải là h ứng với giá trị lớn nhất h được dùng). Nhưng dễ hơn nhiều là: nếu chúng ta thay thế mọi sự xuất hiện của “1” bằng “h” (“2” bằng “h+1”) trong sắp xếp bằng chèn, thì chương trình sắp xếp tập tin theo độ dài bước h sẽ như trang trước:

Chương trình này sử dụng dãy tăng…, 1093, 364, 40, 13, 4, 1. Các dãy tăng khác cũng có thể sử dụng trong thực tế. Dãy tăng trong chương trình này dễ sử dụng và dẫn đến sắp xếp hiệu quả. Nhiều dãy tăng khác dẫn đến việc sắp xếp hiệu quả hơn nữa (điều này phải nhờ các độc giả thử khả năng của mình khám phá ra một dãy tăng của h và tự mình sắp và kiểm nghiệm). Tuy nhiên để tìm được dãy có hiệu quả khoảng 20% so với chương trình trên là không dễ chút nào ngay cả khi N tương đối lớn. Mặt khác có vài dãy tăng rất tồi. Shellsort đôi khi được cài đặt bằng cách bắt đầu với h=N (thay vì phải dùng dãy tăng trên). Điều này đảm bảo là sẽ sản sinh ra một dãy con tồi ứng với một giá trị N nào đó. Mô tả trên về độ hiệu quả của Shellsort là không chính xác bởi vì không có ai có thể phân tích thuật toán. Điều này dẫn đến khó khăn không những khi đánh giá các dãy tăng khác nhau mà cả khi so sánh Shellsort với các phương pháp khác về mặt giải tích. Thậm chí dạng hàm của thời gian chạy cả thời gian chạy cho Shellsort cũng không biết được. (Hơn thế nữa, dạng hàm phụ thuộc vào dãy tăng). Đối với chương trình trên, phỏng chừng là N(logN)2 và N1.25. Thời gian chạy không bị ảnh hưởng bởi thứ tự ban đầu của tập tin, nhưng ngược lại sắp xếp bằng chèn trực tiếp lại tuyến tính với tập tin có sẵn nhưng tỉ lệ N2 với tập tin sắp ngược.

*** Shellsort không bao giờ thực hiện hơn N3/2 so sánh (đối với dãy tăng 1, 4, 13, 40, 121,…)

Như đã nêu ở trên, có vài dãy tăng không hiệu quả mà Shellsort cần một số bình phương lần so sánh, nhưng giới hạn N3/2 đã được chứng minh là đúng đối với một phạm vi rộng các dãy, gồm cả dãy đã dùng ở trên.

Hình dưới đây sẽ cho ta thấy hình ảnh của thao tác trong Shellsort

Hình ảnh của thao tác trong Shellshort cho thấy nội dung của mảng sau mỗi lần sắp (trừ lần cuối cùng hoàn thành việc sắp xếp). Trong hình vẽ này chúng ta có thể hình dung ra một dải sao su bị dồn cục lại ở các điêmr trải dài ở góc dưới trái và trên phải, bị kéo căng hơn để đẩy tất cả các điểm hướng về phía đường chéo. Mỗi đồ hình trong hình trên biểu diễn chỉ một lần sắp xếp theo độ dài h.

Shellsort là phương pháp được chọn cho nhiều ứng dụng sắp xếp bởi vì nó có thời gian chạy có thể chấp nhận được ngay cả đối với tập tin có kích thước lớn vừa phải (ít hơn 5.000 phần tử) và nó đòi hỏi chỉ một lượng mã chương rình rất nhỏ dễ hoạt động. Có thể có nhiều phương pháp hiệu quả hơn nhưng có lẽ chỉ nhanh hơn hai lần ngoại trừ N lớn, và tất nhiên là chúng phức tạp hơn đáng kể. Tóm lại, nếu bạn có một bài toán sắp xếp, thì hãy thử dùng chương trình trên, sau đó xác định xem khi nào việc bỏ công sức ra để thay nó bằng một phương pháp tinh vi hơn là đáng để làm.

School@net (Theo THNT)