ð
ð
ạ
ạ
i H
i H
ọ
ọ
c Sư Ph
c Sư Ph
ạ
ạ
m Tp. H
m Tp. H
ồ
ồ
Ch
Ch
í
í
Minh
Minh
Chương 2: Tìm kiếm & Sắp xếp
C
C
Ấ
Ấ
U TR
U TR
Ú
Ú

• Email:
3
3
Tìm kiếm & Sắp xếp
Mục tiêu:
• Giới thiệu một số thuật toán tìm kiếm và sắp xếp nội.
• Phân tích, đánh giá độ phức tạp của các giải thuật tìm
kiếm, sắp xếp.
Nội dung:
• Nhu cầu tìm kiếm và sắp xếp dữ liệu trong một hệ
thống thông tin.
• Các giải thuật tìm kiếm nội.
• Các giải thuật sắp xếp nội.
4
4
Các giải thuật
tìm kiếm nội
• Tìm tuần tự
• Tìm nhị phân
Tìm kiếm
5
5
Các giải thuật tìm kiếm nội
Bài toán: Tìm vò trí xuất hiện của phần tử có
giá trò
x trên danh sách đặc a
•Tập dữ liệu được lưu trữ là dãy số a
1
, a
2

9
T
TT
Tì
ìì
ìm kie
m kiem kie
m kiế
áá
ám tua
m tuam tua
m tuầ
àà
àn t
n tn t
n tự
ựự
ự
int LinearSearch(int a[], int N, int x)
{
for (int i=0; (i<N)&&(a[i]!=x ); i++);
if (i<N)
return i; // a[i] là phần tử có khoá x
return -1; // tìm hết mảng nhưng không có x
}
10
10
Tìm kiếm tuần tự
• Cải tiến cài đặt: dùng phương pháp “đặt lính
canh

trên một danh sách bất kỳ.
– Một thuật toán có thể được cài đặt theo nhiều
cách khác nhau, kỹ thuật cài đặt ảnh hưởng đến
tốc độ thực hiện của thuật toán.
14
14
Tìm kiếm nhò phân
• Đối với những dãy đã sắp thứ tự (giả sử thứ tự
tăng), các phần tử trong dãy có quan hệ
a
i -1
≤
≤≤
≤ a
i
≤
≤≤
≤ a
i+1
Nếu x > a
i
thì x chỉ có thể xuất hiện trong
đoạn
[a
i+1
,a
N
] của dãy
Nếu x < a
i

mid -1
right = mid - 1;
Ngược lại //tìm x trong dãy con a
mid +1
.. a
right
left = mid + 1;
//Hết lặp
Bước 3: Dừng, không tìm thấy.
17
17
Tìm kiếm nhò phân
• Ví dụ: Cho dãy số a gồm 8 phần tử:
1 2 4 5 6 8 12 15
• Giá trò cần tìm là 8
18
18
Tìm kiếm nhò phân
• left = 1, right = 8, mid = 4
19
19
Tìm kiếm nhò phân
• left = 5, right = 8, mid = 6
20
20
Tìm kiếm nhò phân
int BinarySearch(int a[],int N,int x )
{
int left =0, right = N-1, midle;
while (left <= right)

nhò phân
(n) = O(log
2
n) < T
tuần tự
(n) = O(n).
23
23
Tìm kiếm nhò phân

Nhận xét:
– Khi muốn áp dụng giải thuật tìm nhò phân cần
phải xét đến thời gian sắp xếp dãy số để thỏa
điều kiện dãy số có thứ tự. Thời gian này không
nhỏ, và khi dãy số biến động cần phải tiến hành
sắp xếp lại => khuyết điểm chính cho giải thuật
tìm nhò phân.
– Cần cân nhắc nhu cầu thực tế để chọn một trong
hai giải thuật tìm kiếm trên sao cho có lợi nhất.
24
24
Đònh nghóa bài toán sắp xếp
• Sắp xếp là quá trình xử lý một danh sách các
phần tử (hoặc các mẫu tin) để đặt chúng theo
một
thứ tự thỏa mãn một tiêu chuẩn nào đó
dựa trên nội dung thông tin lưu giữ tại mỗi
phần tử.
• Lưu ý: Thứ tự được đề cập ở đây là một thứ
tự tổng quát.

≤ … ≤
≤≤
≤ a
n
26
26
Các phương pháp sắp xếp thông dụng
• Selection sort
• Insertion sort
• Interchange sort
• Bubble sort
• Shaker sort
• Binary Insertion
sort
• Shell sort
• Heap sort
• Quick sort
• Merge sort
• Radix sort
• …
Đ
Đ
ơn gia
ơn gia
û
û
n,
n,
Chi ph
Chi ph

ä
ä
t toa
t toa
ù
ù
n
n
kha
kha
ù
ù
c
c
27
27
Selection sort – Ý tưởng
• Nhận xét: Mảng có thứ tự thì
a
i
= min(a
i
, a
i+1
, …, a
n-1
)


Ý tưởng: mô phỏng một trong những cách sắp

min
2 3 4 5 6 7 81
Find MinPos(1, 8)
Swap(a
i
, a
min
)
30
30
Selection sort – Ví duï
2 8 5 12 6 4 151
i
min
2 3 4 5 6 7 81
Find MinPos(2, 8)
Swap(a
i
, a
min
)
31
31
Selection sort – Ví duï
2 8 5 12 6 4 151
i
min
2 3 4 5 6 7 81
Find MinPos(3, 8)
Swap(a

34
34
Selection sort – Ví duï
2 4 5 6 12 8 151
i
min
2 3 4 5 6 7 81
Find MinPos(6, 8)
Swap(a
i
, a
min
)
35
35
Selection sort – Ví dụ
2 4 5 6 8 12 151
i
min
2 3 4 5 6 7 81
Find MinPos(7, 8)
Swap(a
i
, a
min
)
12
15
36
36

i)(n
1n
1i
−
=−
∑
−
=
39
39
Insertion Sort – Ý tưởng
• Nhận xét: mọi dãy a
1
, a
2
,..., a
n
luôn có i-1 phần tử
đầu tiên a
1
, a
2
,... ,a
i-1
đã có thứ tự (2 ≤ i).


Ý tưởng chính: tìm cách chèn phần tử a
i
vào vò trí

– Thêm a
2
vào đoạn a
1
sẽ có đoạn a
1
a
2
được sắp
– Thêm a
3
vào đoạn a
1
a
2
để có đoạn a
1
a
2
a
3
được sắp
– Tiếp tục cho đến khi thêm xong a
N
vào đoạn a
1
a
2 ...
a
N-1

41
41
Insertion Sort – Ví duï
2 8 5 1 6 4 1512
2 3 4 5 6 7 81
42
42
2 8 5 1 6 4 1512
i
x
2 3 4 5 6 7 81
pos
2
Insertion Sort – Ví duï
Insert a
2
into (1, 2)
43
43
12 8 5 1 6 4 152
i
x
2 3 4 5 6 7 81
pos
Insertion Sort – Ví duï
Insert a
3
into (1, 3)
8
44

Insertion Sort – Ví duï
Insert a
6
into (1, 6)
6
47
47
2 5 6 8 12 4 151
i
x
2 3 4 5 6 7 81
pos
Insertion Sort – Ví duï
Insert a
7
into (1, 7)
4
48
48
2 4 5 6 8 12 151
i
x
2 3 4 5 6 7 81
pos
Insertion Sort – Ví duï
Insert a
8
into (1, 8)
15
49