Shell Sort còn gọi là phương thức Shell là loại sắp xếp so sánh tại chỗ. Nó có thể được xem là tổng quát của sắp xếp nổi bọt (bubble sort) hoặc sắp xếp chèn (insertion sort). Giải thuật này tránh các trường hợp phải tráo đổi vị trí của hai phần tử xa nhau trong giải thuật sắp xếp chọn (nếu như phần tử nhỏ hơn ở vị trí bên phải khá xa so với phần tử lớn hơn bên trái).
Khi bắt đầu, giải thuật này sử dụng giải thuật sắp xếp chọn trên các phần tử có khoảng cách xa nhau, sau đó sắp xếp các phần tử có khoảng cách hẹp hơn. Khoảng cách này còn được gọi là khoảng (interval).
Lấy ví dụ dễ hiểu, ta lấy một khoảng là 4. Tạo một danh sách con ảo gồm tất cả các giá trị nằm trong khoảng 4 vị trí. Ở đây các giá trị này là {35, 14}, {33, 19}, {42, 27} và {10, 44}.
Ta so sánh các giá trị trong mỗi danh sách con và hoán đổi chúng (nếu cần) trong mảng ban đầu. Sau bước này, mảng mới sẽ trông như thế này.
Sau đó, chúng tôi lấy khoảng 2 và khoảng cách này tạo ra hai danh sách con - {14, 27, 35, 42}, {19, 10, 33, 44}.
Chúng tôi so sánh và hoán đổi các giá trị trong mảng ban đầu, nếu được yêu cầu. Sau bước này, mảng sẽ trông như thế này.
UPD: Trên hình có lỗi đánh máy và mảng kết quả được cho là
[14, 10, 27, 19, 35, 33, 42, 44].
Cuối cùng, chúng tôi sắp xếp phần còn lại của mảng bằng cách sử dụng khoảng giá trị 1. Shell sử dụng sắp xếp chèn để sắp xếp mảng.
| Name | Best | Average | Worst | Memory | Stable | Comments |
|---|---|---|---|---|---|---|
| Shell sort | n log(n) | depends on gap sequence | n (log(n))2 | 1 | No |