Please purchase a
Please purchase a
personal license.
personal license.
SHELL SORT
SHELL SORT
Ôn t
Ôn t
ậ
ậ
p Insertion sort
p Insertion sort
Ý tưởng của thuật toán:
• Giả sử dãy {a
0
,a
1
,…a
n-1
} có k phần tử đầu tiên
{a
0
,a
1
,…a
k-1
} đã có thứ tự.
• Chèn phần tử a
k
vào dãy đã có thứ  có dãy mới
{a

3. Chèn 3 vào {5,6,8}  {3,5,6,8}
4. Chèn 10 vào {3,5,6,8}  {3,5,6,8,10}
Ôn t
Ôn t
ậ
ậ
p Insertion sort
p Insertion sort
Code:
void Insertion_sort (int a[], int n)
{ for (int i=1;i<n;i++)
{ int x=a[i];
for ( int k =i; (k>0)&&(a[k-1]>x);k )
a[k]=a[k-1];
a[k]=x;
}
}
Shell sort
Shell sort
Giới thiệu:
– Được phát minh bởi Donald L.Shell vào năm 1959
– Shell sort là thuật toán hiệu quả nhất trong nhóm
các thuật toán sắp xếp có độ phức tạp O(n
2
).
– Shell sort là sự cải tiến của Insertion sort dựa vào
hai nhận xét sau đây:
• Insertion sort s
ẽ
r

c x
ế
p trong t
ừ
ng kho
ả
ng
c
ụ
c b
ộ
).
• Insertion sort ho
ạ
t
độ
ng kém hi
ệ
u qu
ả
vì nó di chuy
ể
n
các giá tr
ị
ph
ầ
n t
ử
m

}
Shell sort
Shell sort
Ví dụ: n=8;
16 7 10 1 13 11 3 8
1. d=4

So sánh a[0] =16 > a[4] =13

Swap (a[0],a[4])
13 7 10 1 16 11 3 8
So sánh a[1] = 7 < a[5] =11

!Swap (a[1],a[5])
13 7 10 1 16 11 3 8
So sánh a[2] =10 > a[6] = 3

Swap (a[2],a[6])
13 7 3 1 16 11 10 8
So sánh a[3] =1 < a[7] = 8

!Swap (a[3],a[7])
13 7 3 1 16 11 10 8
Shell sort
Shell sort
13 7 3 1 16 11 10 8
2. d=2

So sánh a[0] =13 > a[2] =3
