CẤU TRÚC DỮ LIỆU
CẤU

TRÚC

DỮ

LIỆU

VÀ GIẢITHUẬT
VÀ

GIẢI

THUẬT
Lý thuyết
Chương 4: Sắp xếp
 Bài toán sắp xếp

Các phương pháp sắpxếpcơ bản

Các

phương

pháp

sắp

xếp

cơ

bản
 Phương pháp sắp xếp nhanh (Quick Sort)
ắ ế ể ố
 Phươn
g
pháp s
ắ
p x
ế
p ki
ể
u vun đ
ố
n
g
(Heap
Sort)
 Phương pháp sắp xếp kiểu trộn (Merge
Sort)
Vũ Anh Dũng - Khoa CNTT 2
4.1 Bài toán sắp xếp
 Sắp xếp là quá trình bố trí lại các phần tử
củamộttập đốitượng nào đó, theo mộtthứ
của

một

tập


đối

tượng

nào

đó,

theo

một

thứ

tự ấn định (tăng, giảm, thứ tự từ điển).

Bài toán đặtra:Sắpxếpmộtbảng gồmN

Bài

toán

đặt

ra

:

Sắp


xếp

một

bảng

gồm

N

bản ghi (record) R
1
…R
N
, theo một trường
nào đógọi là khóa(key)
nào

đó

gọi

là

khóa(key)
.
Vũ Anh Dũng - Khoa CNTT 3
4.2 Một số phương pháp sắp
xếp đơn giản

 Sắp xếp kiểu lựa chọn (Selection Sort)

Sắpxếpkiểuthêmdần (Insertion Sort)
Sắp

xếp

kiểu

thêm

dần

(Insertion

Sort)
 Sắp xếp kiểu đổi chỗ (Exchange Sort -
Bubble Sort)
Bubble

Sort)
Note :
• Dùng dãy khóa sau : 52, 34, 85, 16, 68, 58, 92, 46, 99, 88
• Giả sử xét bài toán sắp xếp theo thứ tự tăng dần
Vũ Anh Dũng - Khoa CNTT 4
4.2.1 Sắp xếp kiểu lựa chọn
 Nguyên tắc : Ở lượt thứ i (i=1,2,…,n) ta sẽ chọn trong
dãy khóa k
i
,k

i+1
,…,k
n
khóa nhỏ nhất và đổi chỗ với k
i
.
 Thuật giải :
void selection_sort(k,n){
1. for (i=1;i<=n-1;i++)
2. { m = i;
3. for (j=i+1;j<=n;j++)
4. if (k[j]<k[m]) m=j;
5. if (m!=i) swap(k[i],k[m]);// tien hanh doi cho
6. }
7. return;
Vũ Anh Dũng - Khoa CNTT 5
4.2.1 Sắp xếp kiểu lựa chọn
i Ki B1 B2B3B4B5B6B7B8B9
1 52 16 1616161616161616
2 34 34 3434343434343434
3 85 85 8546464646464646
4 16 52 5252525252525252
5 68 68 6868685858585858
6 58 58 5858586868686868
7 92 92 9292929292858585
8 46 46 4685858585928888
9 99 99 9999999999999992
10 88 88 88 88 88 88 88 88 92 99
Vũ Anh Dũng - Khoa CNTT 6
4.2.1 Sắp xếp kiểu lựa chọn

 Độ phức tạp của thuật toán (không gian,
thời gian)
Bước i mất n-i phép so sánh, số phép toán so
sánh (n-1)*n/2.
Độ phức tạp tính toán : O(n
2
)
Vũ Anh Dũng - Khoa CNTT 7
4.2.2 Sắp xếp kiểu thêm dần
 Nguyên tắc :Dựa trên kinh nghiệm của người chơi
bài.
 Dãy có một khóa là dãy đã có thứ tự
 Giả sử dãy gồm i khóa đã có thứ tự, thêm khóa thứ
i+1 à t lầ l táhới á khó thứ ithứ i
i+1
v
à
o,
t
a
lầ
n
l
ượ
t
so s
á
n
h
v

ới
c
á
c
khó
a
thứ

i
,
thứ

i
-
1,… để tìm ra chỗ thích hợp để chèn vào.
Vũ Anh Dũng - Khoa CNTT 8
4.2.2 Sắp xếp kiểu thêm dần
 Thuật giải :
void insertion_sort(k,n){
for (i 2 i< n i++)
1.
for

(i
=
2
;
i<
=
n

;
i++)
2. { X= k[i];j=i-1;
3. while((x<k[j])&&(j>0)) do
4
{ k[j+1]
=
k[j];
4
.
{

k[j+1] k[j];
5. j=j-1;
6. }
7. k
[j
+1
]
=X
;
[j];
8. }
9. return;
10. }
Vũ Anh Dũng - Khoa CNTT 9
4.2.2 Sắp xếp kiểu thêm dần
i Ki B1 B2B3B4B5B6B7B8B9
152
34

34
16
16 16 16 16 16 16
23452 52
34 34 34 34 34 34 34
38585
85
52
52 52 52
46
46 46
416161685
68 58
58 52 52 52
56868686885
68 68 58 58 58
65858585858
85 85 68 68 68
7929292929292
92
85 85 85
8 46 46 464646464692 92
88
9 99 99 999999999999
99
92
10 88 88 88 88 88 88 88 88 88 99
Vũ Anh Dũng - Khoa CNTT 10
4.2.2 Sắp xếp kiểu thêm dần
 Độ phức tạp của thuật toán (không gian,

thời gian)
Bước i mất nhỏ nhất 1 phép so sánh, lớn nhất là I
phép so sánh, trung bình là i/2 phép so sánh.
i chạy từ 2->n, do đó mất (n-1)(n+2)/2 phép so
sánh.
Độ phứctạptínhtoán:O(n
2
)
Độ

phức

tạp

tính

toán

:

O(n
2
)
Vũ Anh Dũng - Khoa CNTT 11
4.2.3 Sắp xếp kiểu đổi chỗ
 Ý tưởng chính :
 Nếu có một chỉ số i : k
i
>k
i+1

, ta nói rằng tại vị trí i có
một nghịch thế.
 Nếu duyệt toàn bộ dãy khóa k mà không tồn tại một
nghịch thế nào thì dãy đãcóthứ tự
nghịch

thế

nào

thì

dãy

đã

có

thứ

tự
.
 Nhận xét :

Bảng khóa sẽ được duyệttừ đáy lên đỉnh nếugiữa

Bảng

khóa


sẽ

được

duyệt

từ

đáy

lên

đỉnh
,
nếu

giữa

đường gặp nghịch thế thì hoán đổi vị trí. Như vậy,
sau lượt i thì số lớn thứ i sẽ về đúng vị trí.
Vũ Anh Dũng - Khoa CNTT 12
4.2.3 Sắp xếp kiểu đổi chỗ
 Thuật giải
void bubble_sort(k,n){
1. for (i=1;i<=n-1;i++)
2. {
3
for (j
=
n;j>i;j


)
3
.
for

(j n;j>i;j
)
4. if(k[j]<k[j-1])
5. {tmp=k[j];k[j]=k[j-1];k[j-1]=tmp;}
6. }
7. return;
8
}
Vũ Anh Dũng - Khoa CNTT 13
8
.
}
4.2.3 Sắp xếp kiểu đổi chỗ
 Thuật giải cải tiến
void bubble_sort(k,n){
1. i=0;
d
2.
d
o
3. { i++;
4. nghichthe=false;
5. for
(j

=n
;j
>i
;j

)
(j ;j ;j
)
6. if(k[j]<k[j-1])
7. {tmp=k[j];k[j]=k[j-1];
8. k[j-1]=tmp;nghichthe=true;}
}
9.
}
10. while (nghichthe)
11. return;
12. }
Vũ Anh Dũng - Khoa CNTT 14
4.2.3 Sắp xếp kiểu đổi chỗ
 Độ phức tạp của thuật toán (không gian, thời
gian)
Độ phức tạp tính toán : O(n
2
)
Tu
y
nhiên
,
do thu
ậ

t toán có cải ti
ế
n nên t
ố
c đ
ộ

y, ậ ộ
sẽ nhanh hơn.
 Có thể cải tiến thêm bằng cách trong 1 lần
duyệt, giữ lại vị trí của nghịch thế cuối cùng.
Vũ Anh Dũng - Khoa CNTT 15
4.2.4 Sắp xếp nhanh
 Tác giả : C.A.R Hoare
 Ý tưởng chính :
 Sử dụng phương pháp chia để trị
 Với một dãy chọn một khóa ngẫu nhiên làm chốt
(pivot)
(pivot)
.
 Chia dãy trên làm 3 dãy con S
1
,S
2
,S
3
đặt theo đúng
thứ tự trên, sao cho dãy S
1
chứa các phần tử nhỏ hơn

hốtS
hứ áhầ tử bằ hốtS
hứ áhầ
c
hốt
,
S
2
c
hứ
a c
á
c p
hầ
n
tử

bằ
ng c
hốt
,
S
3
c
hứ
a c
á
c p
hầ
n

tử lớn hơn chốt.
 Áp dụng thuật toán sắp xếp nhanh với S
1
và S
3
.
Vũ Anh Dũng - Khoa CNTT 16
Note : Ví dụ
4.2.4 Sắp xếp nhanh
 Thuật giải
void quick_sort(k,fi,la){
1. ok=true;
if(fi<l ){
2.
if(fi<l
a
){
3. i=fi; j=la+1;pivot=k[fi];
4. while (ok){
5. i++;
hil ((k[i]< i t)&&(i<l ))i++
6. w
hil
e
((k[i]<
p
i
vo
t)&&(i<l
a

))i++
;
7. j ;
8. while((k[j]>pivot)&&(j>fi))j ;
9. if (i<j) swap(k[i],k[j]); else ok=false;
}
10.
}
11. swap(k[fi],k[j]);
12. quick_sort(k,fi,j-1);
13. quick_sort(k,j+1,la);
} ret rn
Vũ Anh Dũng - Khoa CNTT 17
14.
}

ret
u
rn
;
15. }
4.2.4 Sắp xếp nhanh
 Nhận xét và đánh giá
 Ví d
ụ
ụ
 Vấn đề chọn chốt
 Vấn đề kết hợp với các phương pháp khác : Khi
ố ầ ắ ế
p

hân đoạn có s
ố
ph
ầ
n tử nhỏ thì s
ắ
p x
ế
p nhanh
không có lợi, khi đó có thể kết hợp với sắp xếp
nổibọt (Kunth
-
1979 có nêu : 9 là giá trị giới
nổi

bọt
.
(Kunth
-
1979

có

nêu

:

9

là


giá

trị

giới

hạn của quick sort).
 Đ
ộ

p
hức t
ạp
tính toán : O
(
nlo
g
2
n
)
Vũ Anh Dũng - Khoa CNTT 18
ộ p ạp(g
2
)
4.2.5 Sắp xếp vun đống
 Cây nhị phân hoàn chỉnh và cách lưu trữ kế
tiếp.
tiếp.
 Định nghĩa : Đống là một cây nhị phân hoàn

chỉnh mà mỗi nút đượcgánmột giá trị sao
chỉnh

mà

mỗi

nút

được

gán

một

giá

trị

sao

cho khóa ở nút cha bao giờ cũng lớn hơn
khóa ở nút con củanó
khóa

ở

nút

con


của

nó
.
Vũ Anh Dũng - Khoa CNTT 19
4.2.5 Sắp xếp vun đống
 Thuật toán :

Giai đoạntạo đống : Cây nhị phân ban đầu

Giai

đoạn

tạo

đống

:

Cây

nhị

phân

ban

đầu


được tạo thành một đống. (k
i/2
>k
i
với
1<=i/2<i<=n).
 Giai đoạn 2 : Giai đoạn sắp xếp
 Đưa khóa trội về vị trí thực của nó bằng cách đổi
chỗ cho khóa hiện đang ở vị trí đó.
 Vun lại thành đống với cây gồm các khóa còn lại
sau khi đãloại khóa trội ra ngoài
Vũ Anh Dũng - Khoa CNTT 20
sau

khi

đã

loại

khóa

trội

ra

ngoài
.
4.2.5 Sắp xếp vun đống

 Cài đặt :
 Chú ý : Với cây n nút thì chỉ số nút từ [n/2] trở xuống mới có thể là cha của nút khác.
void vundong(i,n){
1. ke
y
= k[i];
j
=i*2;
yj
2. //chon con ung voi khoa max trong 2 con cua i
3. while (j<=n){
4. if (j<n)&&(k[j]<k[j+1]) j++;
5. //so sanh khoa cha voi khoa con lon nhat
6. if (key>k[j]){
7. k[j/2]=key; return;
8. }
9. k[
j
/2] = k[
j
];
j
=2*
j
;
jjjj
10. }
11. k[j/2]=key;
12. }
Vũ Anh Dũng - Khoa CNTT 21

4.2.5 Sắp xếp vun đống
void heap_sort(k,n){
1. //Giai doan 1
2
for (i=n/2;i>0;i

)
2
.
for

(i=n/2;i>0;i
)
3. vundong(i,n);
4. //sapxep
i
i0i
5. for (
i
=n-1;
i
>
0
;
i
){
6. X=k[1];k[1]=k[i+1];k[i+1]=X;
7. vundong(1,i);
8. }
9. }

10
Độ phứctạp tính toán : O(nlog
n)
Vũ Anh Dũng - Khoa CNTT 22
10
.
Độ

phức

tạp

tính

toán

:

O(nlog
2
n)
4.2.6 Sắp xếp hòa nhập
 Sắp xếp dựa trên việc hợp nhất hai mảng đã sắp
xếp thành mảng mới.
 Nguyên tắc : So sánh 2 khóa nhỏ nhất (lớn nhất)
của 2 mảng. Đưa phần tử nhỏ hơn (lớn hơn) về
ầ
mảng mới, loại bỏ ph
ầ
n tử đó khỏi mảng cũ. Lặp

cho đến khi hai mảng con hết phần tử.
ắ ắ ế kiể hh đ
 Đưa ra nguyên t
ắ
c s
ắ
p x
ế
p
kiể
u
h
òa n
h
ập 2
đ
ường
trực tiếp.
Vũ Anh Dũng - Khoa CNTT 23