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

Radix sort
 Thuật toán:
– Xem các phần tử trong mảng gồm các lớp có độ
ưu tiên khác nhau. VD: các số tự nhiên gồm các
lớp: đơn vị, chục, trăm, ngàn,
– Duyệt các phần tử từ trên xuống dưới.
– Bước 1: sắp xếp dãy các phần tử ở lớp có độ ưu
tiên thấp nhất (VD: các chữ số hàng đơn vị). Số
nào có hàng đơn vị thấp hơn thì ta đưa lên trên.
– Sau bước 11 dãy sắp xếp mới. Tương tự với các
lớp kế tiếp (chữ số thuộc hàng chục, hàng trăm,…)
cuối cùng sẽ có dãy đã sắp xếp.
Radix sort
Radix sort
Ví dụ: Cho dãy [310, 213, 023, 130, 013, 301,
222, 032, 201, 111, 323, 002, 330, 102, 231, 120]
Bucket Number Contents
0 310, 130, 330, 120
1 301, 201, 111, 231
2 222, 032, 002, 102
3 213, 023, 013, 323
 310, 130, 330, 120, 301, 201, 111, 231, 222, 032,
002, 102, 213, 023, 013, 323
Radix sort
Radix sort
Bucket Number Contents
0 301, 201, 002, 102
1 310, 111, 213, 013
2 120, 222, 023, 323
3 130, 330, 231, 032

1 7 2 5 0 7 0 1 7 0 0 9 9 1 7 0 0 9 9 9
0 9 9 9 3 2 5 2 4 5 1 8 3 2 5 2 1 4 2 4
9 1 7 0 1 4 2 4 1 4 2 4 1 4 2 4 1 7 2 5
3 2 5 2 1 7 2 5 1 7 2 5 4 5 1 8 3 2 5 2
4 5 1 8 4 5 1 8 3 2 5 2 0 7 0 1 4 5 1 8
7 0 0 9 0 9 9 9 9 1 7 0 1 7 2 5 7 0 0 9
1 4 2 4 7 0 0 9 0 9 9 9 0 9 9 9 9 1 7 0
Radix sort
Radix sort
 Đánh giá thuật toán:
- Với một dãy n số, mỗi số có tối đa m chữ số, thuật
toán thực hiện m lần các thao tác phân Bucket và
ghép Bucket.
- Trong thao tác phân Bucket, mỗi phần tử chỉ được
xét đúng một lần, khi ghép cũng vậy.
- Như vậy, chi phí cho việc thực hiện thuật toán hiển
nhiên là O(2m*n) = O(n).