thuật toán shell sort - cải tiến của 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;
}
}
}
.png)
.png)
.png)
.png)
