Đ
Đ
ạ
ạ
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
Ú
Ú
4
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
, ,a
N
int a[N];
•Khoá cần tìm là x
int x;
5
5
Tìm kiếm tuần tự
• Bước 1: i = Vò trí đầu;
• Bước 2: Nếu a[i] = x : Tìm thấy. Dừng, vò trí
xuất hiện: i
• Bước 3 : i = Vò trí kế(i);// xét tiếp phần tử kế
trong mảng
• Bước 4: Nếu i >Vò trí cuối: //Hết mảng
Không tìm thấy. Dừng.
Ngược lại: Lặp lại Bước 2.
6
6
Tìm kiếm tuần tự
• Ví dụ: Cho dãy số a
1228516415
• Giá trò cần tìm: 8
return -1; // tìm hết mảng nhưng không có x
}
9
9
Tìm kiếm tuần tự
• Cải tiến cài đặt: dùng phương pháp “đặt lính
canh”
– Đặt thêm một phần tử có giá trò x vào cuối mảng
– Bảo đảm luôn tìm thấy x trong mảng
– Sau đó dựa vào vò trí tìm thấy để kết luận.
10
10
Tìm kiếm tuần tự
int LinearSearch(int a[], int N, int x)
{
// mảng gồm N phần tử từ a[0] a[N-1]
a[N] = x; // thêm lính canh vào cuối dãy
for (int i=0; (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
}
11
11
Tìm kiếm tuần tự
• Đánh giá giải thuật:
• Vậy giải thuật tìm tuần tự có độ phức tạp
tính toán cấp n: T(n) = O(n)
12
12
,a
N
] của dãy
Nếu x < a
i
thì x chỉ có thể xuất hiện trong
đoạn [a
1
,a
i-1
] của dãy
14
14
Tìm kiếm nhò phân
• Ý 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 tìm kiếm hiện hành, dựa vào kết quả
so sánh này để quyết đònh giới hạn dãy tìm
kiếm ở bước kế tiếp là nửa trên hay nửa dưới
của dãy tìm kiếm hiện hành
15
15
Tìm kiếm nhò phân
Bước 1: left = VTĐ; right = VTC;
Bước 2: Trong khi left ≤
≤≤
≤ right lặp: //đoạn tìm kiếm chưa rỗng
Bước 2.1: mid = (left+right)/2; // lấy mốc so sánh
Bước 2.2: Nếu a[mid] = x: //Tìm thấy.
Dừng, vò trí xuất hiện: mid
{
int left =0, right = N-1, midle;
while (left <= right)
{
midle = (left + right)/2;
if (x == a[midle])
return midle;//Tìm thấy x tại mid
if (x<a[midle])right = midle -1;
else left = midle +1;
}
return -1; // trong dãy không có x
}
20
20
Tìm kiếm nhò phân
• Đánh giá giải thuật:
• Giải thuật tìm nhò phân có độ phức tạp
tính toán cấp logn:
T(n) = O(log
2
n)
21
21
Tìm kiếm nhò phân
Nhận xét:
– Giải thuật tìm nhò phân dựa vào quan hệ giá trò
của các phần tử mảng để đònh hướng trong quá
trình tìm kiếm, do vậy chỉ áp dụng được cho
những dãy đã có thứ tự.
phần tử.
• Lưu ý
: Thứ tự được đề cập ở đây là một thứ
tự tổng quát.
• Ví dụ: Hãy đònh nghóa một thứ tự để dãy số
sau là dãy tăng theo thứ tự này.
1 3 5 7 2220106
24
24
Khái niệm nghòch thế
• Khái niệm nghòch thế:
– Xét một mảng các số a
0
, a
1
, … a
n
.
– Nếu cói<j vàa
i
> a
j
, thì ta gọi đó là một nghòch
thế.
• Mảng chưa sắp xếp sẽ có nghòch thế.
• Mảng đã có thứ tự sẽ không chứa nghòch thế.
a
0
≤
≤≤
n,
n,
Chi ph
Chi ph
í
í
cao
cao
Ph
Ph
ứ
ứ
c ta
c ta
ï
ï
p hơn
p hơn
Hie
Hie
ä
ä
u qua
u qua
û
û
cao
cao
Lơ
Lơ
)
Ý tưởng: mô phỏng một trong những cách sắp
xếp tự nhiên nhất trong thực tế:
– Chọn phần tử nhỏ nhất trong N phần tử ban đầu,
đưa phần tử này về vò trí đúng là đầu dãy hiện
hành
– Xem dãy hiện hành chỉ còn N-1 phần tử của dãy
ban đầu, bắt đầu từ vò trí thứ 2; lặp lại quá trình
trên cho dãy hiện hành đến khi dãy hiện hành
chỉ còn 1 phần tử.
27
27
Selection sort – Thuật toán
//input: dãy (a, N)
//output: dãy (a, N) đã được sắp xếp
• Bước 1 : i = Vò trí đầu;
• Bước 2 : Tìm phần tử a[min] nhỏ nhất trong dãy
hiện hành từ a[i] đến a[N]
• Bước 3 : Nếu min
≠
≠≠
≠ i: Hoán vò a[min] và a[i]
• Bước 4 : Nếu i chưa là Vò trí cuối
» i = Vò trí kế(i);
» Lặp lại Bước 2
Ngược lại: Dừng. //N phần tử đã nằm
đúng vò trí.
28
min
23456781
Find MinPos(3, 8)
Swap(a
i
, a
min
)
31
31
Selection sort – Ví duï
2 4 5 12 6 8 151
i
min
23456781
Find MinPos(4, 8)
Swap(a
i
, a
min
)
32
32
Selection sort – Ví duï
2 4 5 12 6 8 151
i
min
23456781
Find MinPos(5, 8)
Swap(a
12
15
35
35
Selection sort
void SelectionSort(int a[],int N )
{
int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; i<N-1 ; i++)
{
min = i;
for(int j = i+1; j < N ; j++)
if (a[j] < a[min])
min = j; // ghi nhận vò trí phần tử nhỏ nhất
if (min != i)
Swap(a[min], a[i]);
}
}
36
36
• Số lần hoán vò (một hoán vò bằng 3 phép
gán) phụ thuộc vào tình trạng ban đầu
của dãy số
Selection sort – Đánh giá giải thuật
37
37
Selection sort – Đánh giá giải thuật
• Ởû lượt thứ i, cần (N-i) lần so sánh để xác
đònh phần tử nhỏ nhất hiện hành.
• Số lượng phép so sánh không phụ thuộc vào
Ý tưởng chính: tìm cách chèn phần tử a
i
vào vò trí
thích hợp của đoạn đã được sắp để có dãy mới a
1
,
a
2
, ,a
i
trở nên có thứ tự.
– Vò trí này chính là pos thỏa a
pos-1
≤ a
i
<a
pos
(1≤
≤≤
≤pos≤
≤≤
≤i).
Chi tiết hơn:
– Dãy ban đầu a
1
, a
2
, , a
n
a
2
a
N-1
sẽ
có dãy a
1
a
2
a
N
được sắp.
39
39
Insertion Sort – Thuật toán
//input: dãy (a, N)
//output: dãy (a, N) đã được sắp xếp
• Bước 1
: i = 2; // giả sử có đoạn a[1] đã được sắp
• Bước 2
: x = a[i]; Tìm vò trí pos thích hợp trong đoạn
a[1]
đến a[i] để chèn x vào
• Bước 3
: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang
phải 1 vò trí để dành chổ cho x
• Bước 4
: a[pos] = x; // có đoạn a[1] a[i] đã được sắp
• Bước 5
: i = i+1;
3
into (1, 3)
8
43
43
8 12 5 1 6 4 152
i
x
23456781
pos
Insertion Sort – Ví duï
Insert a
4
into (1, 4)
5
44
44
5 8 12 1 6 4 152
i
x
23456781
pos
Insertion Sort – Ví duï
Insert a
5
into (1, 5)
1
45
45
2 5 8 12 6 4 151
8
into (1, 8)
15
48
48
2 4 5 6 8 12 151
pos
23456781
Insertion Sort – Ví duï
49
49
Insertion Sort – Cài đặt
void InsertionSort(int a[], int N )
{
int pos, i;
int x;
//lưu trữ a[i] tránh bò ghi đè khi dời chỗ các phần tử.
for(int i=1 ; i<N ; i++) //đoạn a[0] đã sắp
{
x = a[i];
for(pos=i;(pos>0)&&(a[pos-1]>x);pos )
a[pos] = a[pos-1];
a[pos] = x;// chèn x vào dãy
}
}
50
50
Insertion Sort – Nhận xét
• Khi tìm vò trí thích hợp để chèn a[i] vào đoạn
a[0] đến a[i-1], do đoạn đã được sắp
a[l] = x; // chèn x vào dãy
}
}
52
52
Insertion Sort – Đánh giá giải thuật
• Các phép so sánh xảy ra trong mỗi vòng lặp tìm vò trí
thích hợp pos. Mỗi lần xác đònh vò trí pos đang xét
không thích hợp
dời chỗ phần tử a[pos-1] đến vò trí
pos.
• Giải thuật thực hiện tất cả N-1 vòng lặp tìm pos, do số
lượng phép so sánh và dời chỗ này phụ thuộc vào tình
trạng của dãy số ban đầu, nên chỉ có thể ước lược trong
từng trường hợp như sau:
Phương pháp đổi chỗ trực tiếp
Interchange Sort
54
54
Interchange Sort – Ý tưởng
• Nhận xét: Để sắp xếp một dãy số, ta có
thể xét các nghòch thế có trong dãy và
làm triệt tiêu dần chúng đi.
Ý tưởng chính:
– Xuất phát từ đầu dãy, tìm tất cả nghòch thế
chứa phần tử này, triệt tiêu chúng bằng
cách đổi chỗ phần tử này với phần tử tương
i
j
2
58
58
Interchange Sort – Ví duï
2 12 8 5 6 4 151
23456781
i
j
4
59
59
Interchange Sort – Ví duï
2 4 12 8 6 5 151
23456781
i
j
5
60
60
Interchange Sort – Ví duï
2 4 5 6 8 12 151
23456781
61
61
Interchange Sort - Cài đặt
void InterchangeSort(int a[], int N)
{
int i, j;
Bubble sort – Thuật toán
//input: dãy (a, N)
//output: dãy (a, N) đã được sắp xếp
• Bước 1 : i = Vò trí đầu;
• Bước 2 : j = Vò trí cuối;//Duyệt từ cuối dãy ngược
về vò trí i
– Trong khi (j > i) thực hiện:
• Nếu a[j]<a[j-1]: a[j]↔
↔↔
↔a[j-1];//xét cặp phần tử kế cận
• j = Vò trí trước(j);
• Bước 3 : i = Vò trí kế(i); // lần xử lý kế tiếp
– Nếu i = Vò trí cuối: Dừng. // Hết dãy.
– Ngược lại : Lặp lại Bước 2.
66
66
Bubble Sort – Ví dụ
2 8 5 1 6 4 1512
23456781
i
j
1
67
67
Bubble Sort – Ví dụ
12 2 8 5 4 6 151
23456781
i
j
2
j
8
72
72
Bubble Sort – Ví duï
2 4 5 6 8 12 151
23456781
i
j
15
12
73
73
Bubble sort - Cài đặt
void BubbleSort(int a[], int N)
{
int i, j;
for (i = 0 ; i < N-1 ; i++)
for (j = N-1; j>i ; j )
if(a[j]< a[j-1])
Swap(a[j], a[j-1]);
}
74
74
Bubble sort - Đánh giá giải thuật
• Số lượng các phép so sánh xảy ra không phụ
thuộc vào tình trạng của dãy số ban đầu
• Số lượng phép hoán vò thực hiện tùy thuộc
vào kết quả so sánh
75
• Bước 2 :
– Bước 2a : j = r ; // đẩy phần tử nhỏ về đầu mảng
• Trong khi (j > l) :
– Nếu a[j]<a[j-1]: a[j] ↔
↔↔
↔ a[j-1];
» k = j; //lưu lại nơi xảy ra hoán vò
– j = j-1;
• l = k; //loại bớt các phần tử đã có thứ tự ở đầu dãy
78
78
Giải thuật ShakerSort
• Bước 2 :
– Bước 2b : j = l ; // đẩy phần tử lớn về cuối mảng
• Trong khi (j < r) :
– Nếu a[j]>a[j+1]: a[j] ↔
↔↔
↔ a[j+1];
» k = j;//lưu lại nơi xảy ra hoán vò
– j = j+1;
• r = k; //loại bớt các phần tử đã có thứ tự ở cuối dãy
• Bước 3 : Nếu l < r: Lặp lại Bước 2.
79
79
Sắp xếp cây - Heap sort
• Khi tìm phần tử nhỏ nhất ở bước i, phương
pháp sắp xếp chọn trực tiếp không tận dụng
được các thông tin đã có được do các phép so
sánh ở bước i-1.
• Giải thuật Heap Sort khắc phục nhược điểm
trống giá trò -∞
∞∞
∞ để tiện việc cập nhật lại cây :
83
83
Sắp xếp cây - Heap sort
• Toàn bộ nhánh trái của cây cũ được bảo
toàn
⇒
⇒⇒
⇒ Bước kế tiếp để chọn được phần tử lớn
nhất hiện hành là 6, chỉ cần làm thêm
một phép so sánh 1 với 6.
84
84
Sắp xếp cây - Heap sort
• Tiến hành nhiều lần việc loại bỏ phần tử gốc của
cây cho đến khi tất cả các phần tử của cây đều là -
∞
∞∞
∞, khi đó xếp các phần tử theo thứ tự loại bỏ trên
cây sẽ có dãy đã sắp xếp.
• Để cài đặt thuật toán hiệu quả, cần phải tổ chức
một cấu trúc lưu trữ dữ liệu cókhảnăng thểhiện
được quan hệ của các phần tử trong cây với n ô nhớ
thay vì 2n-1 như trong ví dụ.
• Khái niệm heap và phương pháp sắp xếp Heapsort
do J.Williams đề xuất đã giải quyết được các khó
khăn trên.
85
, a
2i
), (a
i
,a
2i+1
) được gọi là các cặp
phần tử liên đới.
– Heap được đònh nghóa như trên được dùng
trong trường hợp sắp xếp tăng dần, khi sắp
xếp giảm dần phải đổi chiều các quan hệ.
86
86
Ví dụ dãy là heap:
12 8 5 1 4 6 215
23456781
87
87
Sắp xếp cây – Heap sort
a
2
a
3
a
4
a
5
a
6
a
là một heap
thì phần tử a
1
(đầu heap) luôn là phần tử
lớn nhất trong heap.
– Tính chất 3: Mọi dãy con a
left
, a
left+1
, ,
a
right
thỏa: 2left > right đều là heap.
89
89
Ví dụ các tính chất của heap:
12 8 5 1 6 4 215
23456781
12 8 5 1 6 4
1 6 4 2
90
90
Sắp xếp cây - Heap sort
• Sắp xếp dãy tăng dần qua 2 giai đoạn:
– Giai đoạn 1: Dựa vào tính chất 3 của heap
để hiệu chỉnh dãy ban đầu thành heap
– Giai đoạn 2: Dựa vào các tính chất 1 và 2
của heap để sắp xếp heap có được sau giai
đoạn 1 thành dãy tăng dần
91
//input: dãy (a, N)
//output: dãy (a, N) là một heap
• Bước 1: left = N/2; //Thêm các phần tử
a
left
, , a
1
vào heap
• Bước 2: Trong khi left > 0
//Lưu ý: đoạn a
left+1
, …, a
N
đã là heap
• Bước 21: Hiệu chỉnh đoạn a
left
, …, a
N
thành heap
• Bước 22: left = left - 1;
//Hết lặp
93
93
Heap sort – Giai ñoaïn 1
2 8 5 1 6 4 1512
23456781
94
94
15
Heap sort – Giai ñoaïn 1
98
98
Heap sort – Giai đoạn 2
• Vấn đề: Sắp xếp heap a
1
, …, a
N
thành dãy tăng
dần
//Đặt: right = N
dãy a
1
, …, a
right
là heap.
• Ý tưởng:
– Theo tính chất 2: a
1
sẽ là phần tử lớn nhất, vì vậy vò
trí đúng của a
1
phải là right - cuối dãy.
Đổi chổ (a
1
, a
right
)
);
//Loại bỏ phần tử lớn nhất ra khỏi heap
• Bước 2.2: right := right -1;
• Bước 2.3: Hiệu chỉnh đoạn a
1
, a
2
, …, a
right
thành heap
//Hết lặp
100
100
Heap sort – Giai đoạn 2
12 8 5 1 6 4 215
23456781
right
Swap(a
1
, a
right
)
Copyright: Tài liệu đại học ©