1
Cấu trúc dữ liệu và giải thuật
(Data structure and Algorithms)
2
Tìm kiếm và sắp xếp
Ch
ươ
ng II.
3
I. CÁC GIẢI THUẬT TÌM KIẾM NỘI
1. Tìm kiếm tuyến tính
2. Tìm kiếm nhị phân
II. CÁC GIẢI THUẬT SẮP XẾP NỘI
1. Chọn trực tiếp (Selection sort)
2. Chèn trực tiếp (Insertion sort)
3. Đổi chỗ trực tiếp (Interchange sort)
4. Nổi bọt (Buble sort)
5. Sắp xếp cây (Heap sort)
6. Sắp xếp dựa trên phân hoạch (Quick sort)
7. Sắp xếp trộn trực tiếp (Merge sort )
4
I. CÁC GIẢI THUẬT TÌM KIẾM NỘI
1. Tìm kiếm tuyến tính
2. Tìm kiếm nhị phân
5
* Bài toán tìm ki
ế
m
• Cho dãy n phần tử, giả sử chúng được lưu trữ dưới dạng mảng a[1],
a[2], …., a[n], và các phần tử là số tự nhiên.
• Hãy tìm vị trí của phần tử có giá trị là x trong mảng

Cho dãy số a:
1546158212
Hãy tìm phần tử
x=8
8
1. Tìm ki
ế
m tuy
ế
n tính
b. Ví dụ:
1546158212
X=8
i=1 : a[1
]<>
8
9
1. Tìm ki
ế
m tuy
ế
n tính
b. Ví dụ:
1546158212
X=8
i=2 : a[2]<>8
10
1. Tìm ki
ế
m tuy

i:=1;
2) {Tìm khoá x trong dãy}
While (a[i] <>x)and (i<n) do i:=i+1;
3) {Tìm thấy hay không}
If i=n+1 then return(0)
Else return(i)
End;
12
d. Nhận xét
1. Tìm ki
ế
m tuy
ế
n tính
 Mỗi lần thực hiện lặp while phải tiến hành kiểm tra 2 điểm kiện i<n và a[i]<>x.
Nhưng thực ra chỉ cần kiểm tra điều kiện a[i]<>x bằng cách sử dụng kỹ thuật lính
canh.
Thuật toán cải tiến
 Kỹ thuật lính canh: Đặt thêm phần tử x vào cuối mảng, như vậy bảo đảm luôn
tìm được x trong mảng, sau đó dựa vào vị trí tìm để kết luận
15 846158212
P
h
ầ
n

t
ử
lí
n

i-1
<=a
i
<=a
i+1
- Dãy a
1
, a
2
, …, a
n
đã được sắp xếp tăng dần, để tìm phần tử x, có thể
tiến hành như sau:
•Nếu x>a
i
: Thì x có thể xuất hiện trong đoạn [a
i+1
, a
n
]
•Nếu x<a
i
: Thì x có thể xuất hiện trong đoạn [a
1
, a
i-1
]
- Giải thuật tìm kiếm nhị phân sẽ tìm cách giới hạn phạm vi tìm kiếm x sau
mỗi lần so sánh với 1 phần tử trong dãy. Ý tưởng của giải thuật là tại mỗi
bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy hiện

16
2. Tìm ki
ế
m Nh
ị
phân
Các bước tiến hành như sau:
b. Ví dụ:
Cho dãy số a:
1512865421
Hãy tìm phần tử
x=8
17
2. Tìm ki
ế
m Nh
ị
phân
b. Ví dụ:
1512865421
X=8
left=1; right=8; mid=4
•So sánh (x=8) > (a[mid]=5) 

 Tìm kiếm nửa bên phải
left:=4+1=5
right:=8
mid:=(left+right) div 2=6
18
2. Tìm ki

3) {Tính chỉ sổ giữa}
m:=(l+r) div 2;
4) {So sánh}
If x<k[m] then r:=m-1 else if x>k[m] then l:=m+1
Else return(m)
End;
5) {Tìm kiếm không thoả mãn}
Return(0)
End;
Dạng đệ quy của giải thuật
20
d. Đánh giá giải thuật
2. Tìm ki
ế
m Nh
ị
phân
Giả sử xác suất các phần tử trong mảng nhận giá
trị x là như nhau
Log
2
n/2
Trung bình
Không có x trong mảng
log
2
nXấu nhất
Phần tử đầu tiên có giá trị x1Tốt nhất
Giải thíchSố lần so sánhTrường hợp
Độ phức tạp thuật toán T(n)=O(log

ắ
p x
ế
p cây (Heap sort)
6. S
ắ
p x
ế
p d
ự
a trên phân ho
ạ
ch (Quick sort)
7. S
ắ
p x
ế
p tr
ộ
n tr
ự
c ti
ế
p (Merge sort )
II. CÁC GI
Ả
I THU
Ậ
T S
Ắ


Nh vậy sau j lợt, j khoá nhỏ hơn đã lần lợt ở các vị trí
thứ nhất, thứ hai,

., thứ j theo đúng thứ tự sắp xếp.
1. Chn trc tip
a. T

t

ng gi

i thu

t
25
a. T
ư
t
ưở
ng gi
ả
i thu
ậ
t
Các bước tiến hành như sau:
B
ướ
c 1: i:=1; //
bắt đầu từ phần tử đầu tiên của dãy

ặ
p l
ạ
i b
ướ
c 2

Ng
ượ
c l
ạ
i: D
ừ
ng //
n-1 phần tử đã nằm đúng vị trí
1. Chọn trực tiếp