vÝ tưởng
thuật toán
- Là giải thuật cải tiến từ Insertion sort. Ý tưởng chính của thuật toán là phân chia dãy ban đầu thành những dãy con mà mỗi phần tử của dãy cách nhau 1 vị trí là h. Insertion sort áp dụng sau đó trên mỗi dãy con sẽ làm cho các phần tử được đưa về vị trí đúng tương đối (trong dãy con) 1 cách nhanh chóng.
- Sau đó tiếp tục giảm khoảng cách h để tạo thành các dãy con mới (Tạo điều kiện để so sánh một phần tử với nhiều phần tử khác trước đó không ở cùng dãy con với nó) 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 sẽ được so sánh với nhau để xác định trật tự cuối cùng.
Thuật toán viết bằng C++ :
void main()
{
int i,n,j,gap,temp,a[10];
printf("Mang co bao nhieu phan tu:=");
scanf("%d",&n);
printf("Nhap %d phan tu mang \n\n",n);
for(i=0;i<n;i++)
{
printf("Nhap a[%d]:",i);
scanf("\n%d",&a[i]);
}
for(gap=n/2;gap>0;gap=gap/2)
{
for(i=0;i<n;i=i+gap)
{
temp=a[i];
for(j=i;j>0&&a[j-gap]>temp;j=j-gap)
{
a[j]=a[j-gap];
}
a[j]=temp;
}
}
printf("Sap Xep Hoan Thanh\n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();
}
vĐộ phức tạp của thuật toán
- Yếu tố quyết định chính của thuật toán chính là cách chọn khoảng cách h trong từng bước sắp xếp và số bước sắp xếp k. Nhưng phải thỏa 2 điều kiện sau: hi > hi + 1 và hk = 1.
- Các phần tử h không được là bội số của nhau nhằm tránh hiện tượng mỗi bước sắp thứ tự phải tổ hợp 2 nhóm mà bước trước chúng không hề có ảnh hưởng lẫn nhau. Điều mong muốn là ảnh hưởng giữa các nhóm khác nhau càng nhiều càng tốt.
- Việc đánh giá giải thuật Shell sort hiện nay rất phức tạp, thậm chí 1 số chưa được chứng minh. Nhưng có 1 điều chắc chắn là hiệu quả của thuật toán phụ thuộc vào dãy các độ dài được chọn. Trong trường hợp chọn dãy độ dài theo công thức hi = (hi – 1 - 1)/2 và hk = 1, k = log2 - 1 thì giải thuật có độ phức tạp tương đương n1,2 << n2 .