Bài giảng Cấu trúc dữ liệu và giải thuật: Tìm kiếm và sắp xếp

1

TÌM KIẾM & SẮP XẾP

Bài giảng Cấu trúc dữ liệu và Giải thuật

Nội dung Nội d

Tì

(cid:137) Tìm kiếm kiế (cid:131) Tuần tự (cid:131) Nhị phân Nhị phân

(cid:137) Sắp xếp

(cid:131) (cid:131)

(cid:131) Bubble sort Bubble sort (cid:131) Selection sort Insert sort Insert sort (cid:131) Quick sort

Tìm kiếm

3

(cid:133) Tìm kiếm: duyệt một danh sách và lấy ra phần tử (cid:133) Tìm kiếm: duyệt một danh sách và lấy ra phần tử

thoả tiêu chuẩn cho trước.

(cid:133) Là thao tác phổ biến trên máy tính: (cid:134) Tìm mẫu tin trong cơ sở dữ liệu (cid:134) Tìm mẫu tin trong cơ sở dữ liệu (cid:134) Tìm kiếm thông tin trên Internet…

(cid:133) Khảo sát việc tìm kiếm trên mảng/danh sách.

Tìm kiếm Giải thuật Giải thuật

4

(cid:133) Input:put:

(cid:134) Mảng A gồm n phần tử (cid:134) Giá trị x cần tìm

(cid:133) Trả về:

(cid:134) Vị trí phần tử x trong A hoặc –1 nếu x không xuất hiện

(cid:133) Thao tác cơ bản:

(cid:134) So sánh

Tìm kiếm tuần tự Giải thuật Giải thuật

5

(cid:133) Giải thuật: (cid:133) Giải thuật:

(cid:134) Lần lượt so sánh x với các phần tử của mảng A cho đến khi

gặp được phần tử cần tìm, hoặc hết mảng. (cid:133) Ví dụ: A = {1, 25, 6, 5, 2, 37, 40}, x = 6

x = 6

1

25

6

5

2

37

40

x = 6

1

25

6

5

2

37

40

x = 6

1

25

6

5

2

37

40

Dừng

Tìm kiếm tuần tự Đánh giá Đánh giá

6

(cid:133) Đánh giá (thao tác so sánh): (cid:133) Đánh giá (thao tác so sánh):

Hiếm khi xảy ra. Tại sao?

(cid:134) Tốt nhất: O(1) (cid:134) Xấu nhất: O(n) (cid:134) Xấu nhất: O(n) (cid:134) Trung bình:

(cid:132) Giả sử dữ liệu phân bố đều, xác suất bắt gặp x tại mỗi vị trí

đều như nhau.

+ n)

(cid:132) Mỗi vòng lặp thực hiện 2 thao tác so sánh. Tại sao? (cid:132) Số thao tác = 2*(1 + 2 + … + n) = n + 1 (cid:132) Số thao tác n + 1 2*(1 + 2 + (cid:132) Độ phức tạp: O(n)

Tìm kiếm tuần tự Phần tử lính canh Phần tử lính canh

7

(cid:133) Mỗi vòng lặp cần 2 thao tác so sánh: (cid:133) Mỗi vòng lặp cần 2 thao tác so sánh:

(cid:134) Kiểm tra hết mảng (cid:134) Kiểm tra phần tử hiện tại có bằng x (cid:134) Kiểm tra phần tử hiện tại có bằng x

(cid:133) Phần tử lính canh: đặt giá trị x vào cuối mảng ⇒

không cần kiểm tra điều kiện hết mảng. không cần kiểm tra điều kiện hết mảng.

(cid:133) Ví dụ: A = {1, 25, 5, 2, 37}, x = 6

1 25 5

2 37 6

(cid:133) Trả về: n nếu không tìm thấy Trả ề: nế không tìm thấ

Tìm kiếm nhị phân

ị p

8

(cid:133) Khi mảng gồm các phần tử được sắp, tận dụng điều (cid:133) Khi mảng gồm các phần tử được sắp tận dụng điều

kiện này để giảm số thao tác.

(cid:133) Ý tưởng:

(cid:134) Xét phần tử giữa A[m] (cid:134) Xét phần tử giữa A[m] (cid:134) Nếu A[m] = x, trả về m (cid:134) Nếu A[m] > x, tìm trong các phần tử bên trái của m (cid:134) Nếu A[m] > x tìm trong các phần tử bên trái của m (cid:134) Nếu A[m] < x, tìm trong các phần tử bên trái của m

Tìm kiếm nhị phân Ví dụ minh hoạ Ví dụ minh hoạ

9

16 (cid:133) A = {2 3 6 7 10 16 18} x = 16 {2, 3, 6, 7, 10, 16, 18}, x (cid:133) A

2 2 3 3 6 6 7 10 16 18 7 10 16 18

[0] [1] [2] [3] [4] [5] [6]

[4] [5] [6]

2 2 3 3 6 6 7 10 16 18 7 10 16 18

Tìm kiếm nhị phân Chương trình Chương trình

10

int BinarySearch(int a[], int n, int x) {

int l = 0, r = n-1; while (l <= r) { ) {

(

// tìm thấy

int m = (l + r)/2; if (a[m]==x) return m; else if (x < a[m]) r = m else if (x < a[m])

1; r = m – 1;

else l = m + 1;

} return –1;

// không tìm thấy // khô

hấ

}

Tìm kiếm nhị phân Bài tập Bài tập

11

(cid:133) Thực hiện việc tìm kiếm đối với các bài tập sau: (cid:133) Thực hiện việc tìm kiếm đối với các bài tập sau:

(cid:134) A = {1, 2, 6, 26, 28, 37, 40}, x = 40

(cid:134) A = {1, 2, 6, 26, 28, 37, 40}, x = -7

Tìm kiếm nhị phân Đánh giá Đánh giá

12

(cid:133) Mỗi lần lặp, chiều dài mảng con phải xét được (cid:133) Mỗi lần lặp chiều dài mảng con phải xét được

giảm ½ so với mảng trước đó.

(cid:133) Mảng ban đầu được chia tối đa k lần với k (cid:133) Mảng ban đầu được chia tối đa k lần với k =

⎣log2n⎦.

(cid:133) Tối đa k vòng lặp được thực hiện trong đó mỗi (cid:133) Tối đa k vòng lặp được thực hiện trong đó mỗi

vòng lặp thực hiện 1-2 phép so sánh.

(cid:133) Độ phức tạp: O(log2n) (cid:133) Độ phức tạp: O(log2n)

(cid:133) Mảng cần được sắp xếp trước!!! (cid:133) Mảng cần được sắp xếp trước!!!

p Sắp xếp p

13

(cid:133) Sắp xếp: tổ chức các phần tử trong một danh sách (cid:133) Sắp xếp: tổ chức các phần tử trong một danh sách

theo thứ tự.

(cid:133) Là bài toán phổ biến trên máy tính. (cid:133) Nhiều giải thuật sắp xếp đã ra đời. (cid:133) Nhiều giải thuật sắp xếp đã ra đời

(cid:133) Khảo sát và đánh giá hiệu quả một số giải thuật sắp

ột ố iải th ật ắ

ả át à đá h iá hiệ Khả xếp thông dụng dựa trên mảng.

Sắp xếp Giải thuật Giải thuật

14

(cid:133) Input: (cid:133) Input:

(cid:134) Mảng A gồm n phần tử.

(cid:133) Output: (cid:133) Output:

(cid:134) Một hoán vị của A sao cho: A0 ≤ A1 ≤ … ≤ An-1 (sắp

xếp tăng dần). ) g

(cid:133) Thao tác cơ bản:

(cid:134) So sánh (cid:134) Hoán vị (đổi vị trí hai phần tử)

Sắp xếp Các giải thuật Các giải thuật

15

(cid:133) Các phương pháp sắp xếp thông dụng: (cid:133) Các phương pháp sắp xếp thông dụng:

(cid:134) Bubble Sort (cid:134) Selection Sort (cid:134) Selection Sort (cid:134) Insertion Sort (cid:134) Quick Sort (cid:134) Merge Sort (cid:134) Shell Sort (cid:134) Heap Sort (cid:134) Radix Sort

Bubble sort

16

(cid:133) Giải thuật: (cid:133) Giải thuật:

(cid:134) Xuất phát từ cuối (đầu) dãy, đổi chỗ các cặp phần tử kế

cận để đưa phần tử nhỏ hơn về vị trí đúng đầu dãy y hiện hành.

(cid:134) Sau đó không xét đến nó ở bước kế tiếp. (cid:134) Lần xử lý thứ i sẽ có vị trí đầu dãy là i. (cid:134) Lặp lại cho đến khi không còn cặp phần tử nào để xét.

(cid:133) Ví dụ: sắp xếp dãy A: 15 2 8 7 3 6 9 17

Bubble sort Ví dụVí dụ

17

i = 0 i 0 j = 4 j 4 15 15 2 2 8 8 7 7 3 3 6 6 9 9 17 17

i = 0 j = 3 15 2 8 3 7 6 9 17

i = 0 j = 1 15 2 3 8 7 6 9 17

1 i = 1 i 5 j = 5 j 15 15 3 3 8 8 7 7 6 6 9 9 17 17 2 2

15 3 8 6 7 9 17 2 i = 1 j = 4

15 3 6 8 7 9 17 2 i = 1 j = 2

15 6 8 7 9 17 2 3 i = 2 j j = 5

15 6 7 8 9 17 2 3 i = 2 j = 3

Bubble sort Ví dụ (tt) Ví dụ (tt)

18

j = 4 j 4 i = 3 i 3 15 7 8 9 17 2 3 6

j = 5 i = 4 15 8 9 17 2 3 6 7

j = 6 i = 5 15 9 17 2 3 6 7 8

7 j = 7 j 6 i = 6 i 15 15 17 17 2 2 3 3 6 6 7 7 8 8 9 9

2 3 6 7 8 9 15 17

Bubble sort Chương trình Chương trình

19

void BubbleSort(int a[], int n){

for(int i=0; i

for(int j = n-1; j>i; j--){

if(a[j]

HoanVi(a[j],a[j-1]);

}

Bubble sort Bài tập Bài tập

20

(cid:133) Mô tả tình trạng dãy A sau mỗi bước chạy với thuật (cid:133) Mô tả tình trạng dãy A sau mỗi bước chạy với thuật

toán Bubble sort. {2, 9, 5, 12, 20, 15, 8, 10} A = {2 9 5 12 20 15 -8 10} A

Bubble sort Đánh giá Đánh giá

21

(cid:133) Các giải thuật sắp xếp thường có độ phức tạp tương (cid:133) Các giải thuật sắp xếp thường có độ phức tạp tương

tự nhau.

(cid:133) Cần một đánh giá chi tiết: (cid:133) Cần một đánh giá chi tiết:

(cid:134) Các trường hợp: xấu nhất, tốt nhất, trung bình (cid:134) Các thao tác: (cid:134) Các thao tác: (cid:132) So sánh (cid:132) Gán (quan trọng hơn vì tốn nhiều chi phí hơn). Lưu ý: mỗi

thao tác gán vị tốn 3 phép gán

ố

Bubble sort Chương trình Chương trình

22

void BubbleSort(int a[], int n){

for(int i=0; i

for(int j = n-1; j>i; j--){

if(a[j]

HoanVi(a[j],a[j-1]);

}

ự Số lần vòng j ệ thực hiện?

Số lần vòng i thực hiện?

Bubble sort Đánh giá Đánh giá

23

(cid:133) Số phép so sánh: không phụ thuộc vào tình trạng (cid:133) Số phép so sánh: không phụ thuộc vào tình trạng

dãy số ban đầu.

−

( (

n i n i

1) 1) − − =

∑ ∑

n n ( − 2

(cid:133) Số lượng phép gán: tùy vào kết quả so sánh (cid:133) Số lượng phép gán: tùy vào kết quả so sánh

−

n i

1) − − =

(cid:134) Tốt nhất: 0 (cid:134) Xấu nhất:

∑ ∑

n n 3 ( 2 2

Shaker sort Cải tiến Bubble sort Cải tiến Bubble sort

24

(cid:133) Nhận xét: Bubble sort có các khuyết điểm: (cid:133) Nhận xét: Bubble sort có các khuyết điểm:

(cid:134) Không nhận diện được tình trạng dãy đã có thứ tự hay

không có thứ tự từng phần.

g p

(cid:134) Trong khi phần tử nhỏ được đưa về vị trí đúng rất

nhanh, thì các phần tử lớn lại được đưa về vị trí đúng rất chậm. ấ h Giải thuật Shaker sort cải tiến các khuyết điểm này.

Shaker sort Cải tiến Bubble sort Cải tiến Bubble sort

25

(cid:133) Cải tiến: (cid:133) Cải tiến:

(cid:134) Duyệt mảng theo 2 lượt từ 2 phía khác nhau:

ợ

y p

(cid:132) Lượt đi: đẩy phần tử nhỏ về đầu mảng g (cid:132) Lượt về: đẩy phần tử lớn về cuối mảng.

(cid:134) Ghi nhận lại những đoạn đã sắp.

Shaker sort Ví dụ minh hoạ Ví dụ minh hoạ

26

r =7 7 l = 0 l 0 15 15 2 2 8 8 7 7 3 3 6 6 9 9 17 17

15 2 8 3 7 6 9 17

15 2 3 8 7 6 9 17

r 7 r =7 k 1 k=1 15 15 3 3 8 8 7 7 6 6 9 9 17 17 1 l = 1 l 2 2

3 15 8 7 6 9 17 2

3 8 15 7 6 9 17 2

3 8 7 15 6 9 17 2

Shaker sort Ví dụ minh hoạ Ví dụ minh hoạ

27

3 3 8 8 7 7 6 6 15 15 9 9 17 17 2 2

k=5 3 8 7 6 9 15 17 2 r =5 l = 1

3 8 7 6 9 2 15 17

3 8 6 7 9 2 15 17

k=3 r =5 l = 3 8 7 9 2 3 6 15 17

2 3 6 7 8 9 15 17

Shaker sort Chương trình Chương trình

28

l=0; r=n-1; k=n-1; //khởi gán các giá trị

//k là vị trí xảy ra hoán vị sau cùng

while(l

{{

j=r; // đẩy phần tử nhỏ về đầu

while(j>l)

{ {

if(a[j]

{

HoanVi(a[j], a[j-1]);

k=j; //lưu lại vị trí xảy ra hoán vị

}

j--;j

}

l=k; //loại các phần tử đã có thứ tự ở đầu dãy

Shaker sort Chương trình (tt) Chương trình (tt)

29

j l; //đẩy phần tử lớn về cuối j=l; //đẩy phần tử lớn về cuối

while(j

{

if(a[j]>a[j+1])

{

HoanVi(a[j], a[j+1]);

k=j; //lưu lại vị trí xảy ra hoán vị

}

j++;

}}

r=k; //loại các phần tử đã có thứ tự ở cuối dãy

}

Selection Sort

30

(cid:133) Mô phỏng cách sắp xếp tự nhiên nhất trong thực tế (cid:133) Mô phỏng cách sắp xếp tự nhiên nhất trong thực tế

(cid:134) Chọn phần tử nhỏ nhất và đưa về vị trí đúng là đầu dãy

hiện hành.

(cid:134) Sau đó xem dãy hiện hành chỉ còn n-1 phần tử. (cid:134) Lặp lại cho đến khi dãy hiện hành chỉ còn 1 phần tử.

Selection Sort Giải thuật Giải thuật

31

(cid:133) Các bước của giải thuật: (cid:133) Các bước của giải thuật:

[

[ ]

[

1. i = 0. 2. Tìm a[min] nhỏ nhất trong dãy từ a[i] đến a[n-1] ] ] 3. Hoán vị a[min] và a[i] 4. Nếu i ≤ n thì tăng i và lặp lại bước 2 Ngược lại: Dừng thuật toán

Selection Sort Ví dụVí dụ

32

0 i = 0 i 15 15 2 2 8 8 7 7 3 3 6 6 9 9 17 17

i = 1 15 8 7 3 6 9 17 2

i = 2 8 7 15 6 9 17 2 3

i = 3 7 15 8 9 17 2 3 6

15 8 9 17 2 3 6 7 i = 4

15 9 17 i = 5 2 3 6 7 8

i = 6 15 17 2 3 6 7 8 9

i = 7 17 2 3 6 7 8 9 15

Selection Sort Chương trình Chương trình

33

void SelectionSort(int a[], int n){

int min; //chỉ số của phần tử nhỏ nhất

for(int i=0; i

{{

min = i;

for(int j = i+1; j

{{

if(a[j] < a[min])

min = j; //ghi nhận lại vị trí

}

HoanVi(a[min], a[i]);

}

Selection Sort Đánh giá Đánh giá

34

void SelectionSort(int a[], int n){

int min;

Cho biết số phép gán?

for(int i=0; i

{ {

min = i;

for(int j = i+1; j

{{

if(a[j] < a[min])

min = j;

}

HoanVi(a[min], a[i]);

}

Nhận xét số phép so ố sánh trong vòng for

Selection Sort Đánh giá Đánh giá

35

(cid:133) Số phép so sánh: (cid:133) Số phép so sánh:

(cid:134) Tại lượt i bao giờ cũng cần (n-i-1) số lần so sánh (cid:134) Không phụ thuộc vào tình trạng dãy số ban đầu (cid:134) Không phụ thuộc vào tình trạng dãy số ban đầu 1 −

(

)1 =−−

Số phép so sánh = ∑

( nn − 2

=0i i 0 =

1 −

(cid:133) Số phép gán: (cid:134) Tốt nhất: (cid:134) Tốt nhất:

∑ =∑ 4 4

0i=

1 −

) )1

=−−+

(cid:134) Xấu nhất:

in∑ ∑ ( 4(

nn ( + 2 2

Insertion Sort

36

ếp các quâ bà dù g t uật toá (cid:133) Cách xếp các quân bài dùng thuật toán Insertion

se t o

Các Sort:

(cid:134) Tay trái là dãy các quân bài đã có thứ tự, khi cầm 1

â bài ới lê

quân bài mới lên thì tìm vị trí đúng của nó và chèn vào.

ó à hè

hì ì

í đú

ủ

à ị (cid:134) Cách tìm: lần lượt so sánh quân bài mới với các quân

bài trong dãy ban đầu. bài trong dãy ban đầu.

Insertion Sort Giải thuật Giải thuật

37

(cid:133) Giải thuật: (cid:133) Giải thuật:

(cid:134) Xem dãy a0, a1, …, an-1 có i phần tử đầu tiên a0, a1, …,

ai-1 đã có thứ tự. i 1

(cid:134) Tìm cách chèn phần tử ai vào vị trí thích hợp để dãy a0,

a1, …, ai có thứ tự.

(cid:134) Cho dãy ban đầu a0, a1, …, an-1, có thể xem như đoạn

1 hầ tử

đã đ

ắ

gồm 1 phần tử a0 đã được sắp. ồ

(cid:134) Thêm vào a1 sẽ có a0, a1 được sắp, tiếp tục thêm a2, a3

cho đến khi thêm an-1 cho đến khi thêm a

Insertion Sort Ví dụVí dụ

38

2 2 8 8 7 7 3 3 6 6 9 9 17 17 15 15 i = 1 i 1

8 7 3 6 9 17 2 15 i = 2

7 3 6 9 17 15 2 8 i = 3

3 3 6 6 9 9 17 17 8 8 15 15 2 2 7 7 i = 4

6 9 17 7 8 15 2 3 i = 5

9 17 6 7 8 15 2 3 i = 6

17 6 7 8 9 15 2 3 i = 7

Insertion Sort Giải thuật Giải thuật

39

(cid:133) Các bước của giải thuật: (cid:133) Các bước của giải thuật:

1. Xuất phát từ i = 1. g 2. Tìm vị trí pos thích hợp trong đoạn a[0] đến a[i-1] để chèn

[ ]

ợp

ạ

[

]

ị

a[i].

3. Dời chỗ các phần tử từ a[pos] đến a[i-1] sang 1 vị trí để

chèn a[i]. [i] hè 4. a[pos] = a[i] 5. Tăng i. 5 Tăng i

5.1 Nếu i ≤ n: lặp lại bước 2 5.2 Ngược lại: dừng

Insertion Sort Chương trình Chương trình

40

void InsertionSort(int a[], int n)

{

for(int i=1; i

{{

int x = a[i], pos = i-1;

while(pos>=0 && a[pos] > x) //tìm pos

{{

a[pos+1]=a[pos]; //dời về sau 1 vị trí

pos--;

}

a[pos+1] = x;

}

Insertion Sort Bài tập Bài tập

41

(cid:133) Cho biết các giá trị i, pos tương ứng khi dùng thuật (cid:133) Cho biết các giá trị i pos tương ứng khi dùng thuật toán Insertion Sort để sắp xếp mảng A giảm dần. {2, 9, 5, 12, 20, 15, 8, 10} A = {2 9 5 12 20 15 -8 10} A

Insertion Sort Nhận xét Nhận xét

42

(cid:133) Nhận xét: (cid:133) Nhận xét:

(cid:134) Đoạn a[0] đến a[i-1] luôn luôn được sắp:

ị (cid:132) Việc tìm vị trí chèn có thể dùng giải thuật tìm kiếm nhị

g g

ậ

ị

ệ phân.

(cid:132) Nếu dùng giải thuật tìm kiếm nhị phân thì vẫn phải trả giá

cho thao tác dời các phần tử sau x. cho thao tác dời các phần tử sau x

(cid:134) Sinh viên tự cài đặt.

Insertion Sort Đánh giá Đánh giá

43

void InsertionSort(int a[], int n) {

Số lần lặp i

for(int i=1; i

Số lần lặp pos

a[pos+1]=a[pos]; pos--;

int x = a[i], pos = i-1; while(pos>=0 && a[pos] > x) {

} a[pos+1] = x;

}

}}

Insertion Sort Đánh giá Đánh giá

44

(cid:133) So sánh: (cid:133) So sánh:

−

2 (

−

(cid:134) Tốt nhất:

∑

= n

1 1

−

n n (

−

(cid:134) Xấu nhất:

∑

(cid:133) Gán:

1 −

) 1)

( 3 3( =

−

(cid:134) Tốt nhất: (cid:134) Tốt nhất:

∑ ∑

i= 1

−

)

−

(cid:134) Xấu nhất:

∑ ∑

n n ( − 2 2

i =

Quick sort

45

(cid:133) Các giải thuật Bubble sort, Selection sort, Insertion (cid:133) Các giải thuật Bubble sort Selection sort Insertion

sort: (cid:134) Dễ hiểu, dễ cài đặt ặ , (cid:134) Hiệu quả thấp: O(n2)

(cid:133) Các giải thuật sắp xếp dựa trên so sánh: độ phức (cid:133) Các giải thuật sắp xếp dựa trên so sánh: độ phức

ể đạ được (cid:133) Quick sort (C. A. R. Hoare, 1962) có thể đạt được

. o e, 96 ) có

tạp ≥ n × log2n. . Qu c so (C. độ phức tạp trên.

Quick Sort Ý tưởng Ý tưởng

46

(cid:133) Dựa trên việc phân hoạch dãy ban đầu thành 2 (cid:133) Dựa trên việc phân hoạch dãy ban đầu thành 2

ị

phần: , (cid:134) Dãy con 1: a0, a1, …, ai có giá trị nhỏ hơn x y (cid:134) Dãy con 2: aj, …, an-1 có giá trị lớn hơn x. Dãy ban đầu được phân thành 3 phần: ợ p