Ý tưởng:
Trong phương pháp sắp xếp kiểu chèn nếu ta luôn phải chèn một khóa vào vị trí
đầu dãy thì dẫn đến hạn chế của thuật toán này. Để khắc phục trong trường hợp này thì
người ta đưa ra một phương pháp sắp xếp là ShellSort.
Xét một dãy a[1]...a[n], cho một số nguyên h (1 £ h £ n), ta có thể chia
dãy đó thành h dãy con như sau:
Dãy con 1 : a[1], a[1+ h], a[1+2h]...
Dãy con 2 : a[2], a[2+h], a[2+2h]...
Dãy con 3 : a[3], a[3+h], a[3+2h]...
...
Dãy con h : a[h], a[2h], a[3h]...
Thuật toán :
Bước 1 : chọn k khoảng cách h[1], h[2],.., h[k], và i = 1.
Bước 2 : Chia dãy ban đầu thành các dãy con có bước nhảy là h[i]. Thực hiện 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
o Nếu i > k: Þ Dừng
o Ngược lại: Þ Bước 2.
Ví dụ: cho dãy : 6,5,3,2, 8, 7, 1, 4
Cài đặt ShellSort: sắp xếp dãy a[] tăng, với h[] là mảng chứa các độ dài (bước nhảy) đãchọn sẵn:
void ShellSort(int a[], int n, int h[], int k)
{
int step, i, j;
int x, len;
for(step = 0; step < k; step++) // duyệt qua từng bước nhảy
{
len = h[step]; // chiều dài của bước nhảy
for(i = len; i < n; i++) // duyệt các dãy con
{ // lưu phần tử cuối để tìm vị trí thích hợp trong dãy con
x = a[i]; // a[j] đứng trước a[i] trong cùng dãy con
j = i – len;
while ((x < a[j]) && (j>= 0))
// sắp xếp dãy con chứa x dùng pp chèn
{
a[j+len] = a[j]; // dời về sau theo dãy con
j = j – len; // qua phần tử trước trong dãy con
}
a[j+len] = x;// đưa x vào vị trí thích hợp trong dãy con
}
}
}
0 nhận xét:
Đăng nhận xét