interval = interval*3 +1;                   

  printf("Vong lap thu %d#:",i); 
  display();
  for(outer = interval; outer < elements; outer++) {
     valueToInsert = intArray[outer];
     inner = outer;
     while(inner > interval -1 && intArray[inner - interval] 
= valueToInsert) {
        intArray[inner] = intArray[inner - interval];
        inner -=interval;
        printf(" Di chuyen phan tu :%d\n",intArray[inner]);
     }
     intArray[inner] = valueToInsert;
     printf(" Chen phan tu :%d, tai vi tri :%d\n",valueToInsert,inner);
  }
  interval = (interval -1) /3;           
  i++;

Kết quả

Biên dịch và chạy chương trình C trên sẽ cho kết quả:

Quảng cáo

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.

1. Bubble sort. (Nổi bọt, nổi bong bóng)

2. Quick sort. (Sắp xếp nhanh)
3. Simple selection sort. (Sắp xếp chọn)
4. Thuật toán sắp xếp chèn
5. Heap sort. (Sắp xếp vun đống)
6. Simple insertion sort.(Sắp xếp chèn)
7. Shell sort.

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

{

printf("Nhap a[%d]:",i);

scanf("\n%d",&a[i]);

}

for(gap=n/2;gap>0;gap=gap/2)

{

for(i=0;i

{

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

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 .