thuật toán shell sort - cải tiến của chèn trực tiếp

thuật toán shell sort - cải tiến của chèn trực tiếp

shell sort là Cải tiến của phương pháp chèn trực tiếp
Ý tưởng:
Phân hoạch dãy thành các dãy con
Sắp xếp các dãy con theo phương pháp chèn trực tiếp
Dùng phương pháp chèn trực tiếp sắp xếp lại cả dãy.
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 ban đầu : a1, a2, ..., an được xem như sự xen kẽ của các dãy con sau :
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 ...
Tiến hành 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
Giảm khoảng cách h để tạo thành các dãy con mới
Dừng khi h=1
Giả sử quyết định sắp xếp k bước, các khoảng cách  chọn phải thỏa điều kiện :
hi  > hi+1  và hk = 1
 hi  = (hi-1  - 1)/3 và hk = 1, k = log3n-1
Ví dụ :127, 40, 13, 4, 1
 hi  = (hi-1 - 1)/2 và hk = 1, k = log2n-1
Ví dụ : 15, 7, 3, 1
h có dạng 3i+1: 364, 121, 40, 13, 4, 1
Dãy fibonaci: 34, 21, 13, 8, 5, 3, 2, 1
h là dãy các số nguyên tố giảm dần đến 1: 13, 11, 7, 5, 3, 1.
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 phương pháp   chèn trực tiếp;
Bước 3 : i = i+1;            Nếu  i > k : Dừng            Ngược lại : Lặp lại Bước 2.    
Cho dãy số a:
12   2 8 5 1 6 4 15

Giả sử chọn các khoảng cách là 5, 3, 1

void ShellSort(int a[],int n, int h[], int k)
{ int step,i,j, x,len;
for (step = 0 ; step <k; step++)
{ len = h[step];
for (i = len; i<n; i++)
{
x = a[i]; 
j = i-len; // a[j] đứng kề trước a[i] trong cùng dãy con 
while ((x<a[j])&&(j>=0)// sắp xếp dãy con chứa  x 
{ // bằng phương pháp chèn trực tiếp 
a[j+len]  = a[j];
j = j - len;
}
a[j+len] = x;
}
}
}