Bài giảng Cấu trúc dữ liệu và giải thuật - Tìm kiếm & sắp xếp - Đậu Ngọc Hà Dương

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Tìm kiếm & sắp xếp - Đậu Ngọc Hà Dương

1. 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
2. Nộidi dung ‰ Tìm ki ếm ƒ Tuần tự ƒ Nhị phân ‰ Sắp xếp ƒ Bubble sort ƒ Selection sort ƒ Insert sort ƒ Quick sort
3. Tìm kiếm 3 Tìm ki ếm: duy ệttm một danh sách và l ấyyraph ra phầnnt tử thoả tiêu chuẩn cho trước. Là thao tác phổ biến trên máy tính: † Tìm m ẫu tin trong c ơ sở dữ liệu † Tìm kiếm thông tin trên Internet Khảo sát việc tìm kiếm trên mảng/danh sách.
4. Tìm kiếm Giảithui thuật 4 Input: † Mảng A gồm n phần tử † Giá trị x cần tìm Trả về: † Vị trí phần tử x trong A hoặc –1 nếu x không xuất hiện Thao tác cơ bản: † So sánh
5. Tìm kiếm tuần tự Giảithui thuật 5 Giảithui thuật: † 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. 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
6. Tìm kiếm tuần tự Đánh giá 6 Đánh giá (thao tác so sánh): † Tốt nhất: O(1) Hiếm khi xảy ra. Tại sao? † Xấunhu nhất: O(n) † Trung bình: „ 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. „ Mỗi vòng lặp thực hiện 2 thao tác so sánh. Tại sao? „ Số thao tác = 2*(1 + 2 + + n) = n + 1 „ Độ phức tạp: O(n)
7. Tìm kiếm tuần tự Phầntn tử lính canh 7 Mỗi vòng l ặpcp cần 2 thao tác so sánh: † Kiểm tra hết mảng † Kiểmtraphm tra phầnnt tử hiệnnt tạiicób có bằng x Phần tử lính canh: đặt giá trị x vào cuối mảng ⇒ không cầnkin kiểmtram tra điềuuki kiệnhn hếttm mảng. Ví dụ: A = {1, 25, 5, 2, 37}, x = 6 12552376 Trả về: n nếu không tìm thấy
8. Tìm kiếm nhị phân 8 Khi mảng g ồm các ph ầnnt tử đượccs sắppt, tậnnd dụng điều kiện này để giảm số thao tác. Ý tưởng: † Xét ph ầntn tử giữaA[m]a A[m] † Nếu A[m] = x, trả về m † Nếu A[m] > x , tìm trong các ph ầntn tử bên trái c ủaam m † Nếu A[m] < x, tìm trong các phần tử bên trái của m
9. Tìm kiếm nhị phân Ví d ụ minh hoạ 9 A = {236710{2, 3, 6, 7, 10, 16, 18}, x = 16 2 3 6 7 10 16 18 [0] [1] [2] [3] [4] [5] [6] [4] [5] [6] 2 3 6 7 10 16 18
10. Tìm kiếm nhị phân Chương trình 10 int BinarySearch(int a[], int n, int x) { int l = 0, r = n-1; while (l <= r) { int m = (l + r)/2; if (a[m]==x) return m; // tìm thấy else if (x < a[m]) r = m – 1; else l = m + 1; } return –1; // không t ìm t hấy }
11. Tìm kiếm nhị phân Bài tập 11 Thựchic hiệnvin việc tìm ki ếm đốivi với các bài t ậppsau: sau: † A = {1, 2, 6, 26, 28, 37, 40}, x = 40 † A = {1, 2, 6, 26, 28, 37, 40}, x = -7
12. Tìm kiếm nhị phân Đánh giá 12 Mỗili lầnln lặpchip, chiềuudàim dài mảng con ph ảiixét xét được giảm ½ so với mảng trước đó. Mảng ban đầu đượccchiat chia tối đa k lầnvn với k = ⎣log2n⎦. Tối đa k vòng lặp đượccth thựchic hiện trong đómó mỗi vòng lặp thực hiện 1-2 phép so sánh. Độ phứctc tạp: O(log2n) Mảng c ần đượccs sắppx xếpptr trước!!!
13. Sắp xếp 13 Sắpxp xếp: t ổ chức các ph ầntn tử trong m ột danh sách theo thứ tự. Là bài toán phổ biến trên máy tính. Nhiềugiu giảiithu thuậtts sắppx xếp đããra ra đời. Khảo sát và đááhnh giá iáhi hiệu quả một số giiảithi thuật sắp xếp thông dụng dựa trên mảng.
14. Sắp xếp Giảithui thuật 14 Input: † Mảng A gồm n phần tử. Output: † Một hoán vị của A sao cho: A0 ≤ A1 ≤ ≤ An-1 (sắp xếp tăng dần). Thao tác cơ bản: † So sánh † Hoán vị (đổi vị trí hai phần tử)
15. Sắp xếp Các giảiithu thuật 15 Các phương pháp sắp xếp thông dụng: † Bubble Sort † Selection Sort † Insertion Sort † Quick Sort † Merge Sort † Shell Sort † Heap Sort † Radix Sort
16. Bubble sort 16 Giải thuật: † Xuất phát từ cuối(đầu) dãy, đổichỗ các cặpphầntử kế cận để đưa phầntử nhỏ hơnvề vị trí đúng đầudãy hiện hành. † Sau đó không xét đếnnóở bướckế tiếp. † Lầnxử lý thứ isẽ có vị trí đầu dãy là i. † Lặplạichođến khi không còn cặpphầntử nào để xét. Ví dụ: sắp xếp dãy A: 15 2 8 7 3 6 9 17
17. Bubble sort Ví d ụ 17 i = 0 j = 4 15 2 8 7 3 6 9 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 i = 1 j = 5 2 15 3 8 7 6 9 17 i = 1 j = 4 2 15 3 8 6 7 9 17 i = 1 j = 2 2 15 3 6 8 7 9 17 i = 2 j = 5 2 3 15 6 8 7 9 17 i = 2 j = 3 2 3 15 6 7 8 9 17
18. Bubble sort Ví d ụ (tt) 18 i = 3 j = 4 2 3 6 15 7 8 9 17 i = 4 j = 5 2 3 6 7 15 8 9 17 i = 5 j = 6 2 3 6 7 8 15 9 17 i = 6 j = 7 2 3 6 7 8 9 15 17 2 3 6 7 8 9 15 17
19. Bubble sort Chương trình 19 void BubbleSort(int a[], int n){ for(int i=0; i i; j ){ if(a [j]<a [j-1])//nếusai vị títrí thì đổi chỗ HoanVi(a[j],a[j-1]); } } }
20. Bubble sort Bài tập 20 Mô tả tình tr ạng dãy A sau m ỗibi bướccch chạyvy vớiithu thuật toán Bubble sort. A = {295122015{2, 9, 5, 12, 20, 15, -8, 10}
21. Bubble sort Đánh giá 21 Các gi ảiithu thuậtts sắppx xếppth thường có độ phứcct tạppt tương tự nhau. Cầnmn một đánh giá chi ti ết: † Các trường hợp: xấu nhất, tốt nhất, trung bình † Các thao tác: „ So sánh „ 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
22. Bubble sort Chương trình 22 void BubbleSort(int a[], int n){ for(int i=0; i i; j ){ if(a [j]<a [j-1]) HoanVi(a[j],a[j-1]); } } } Số lần vòng j Số lần vòng i thực hiện? thực hiện?
23. Bubble sort Đánh giá 23 Số phép so sánh: không ph ụ thuộc vào tình trạng dãy số ban đầu. n−2 nn(1)− ∑(1)ni− −= i=0 2 Số lượng phép gán: tùy vào k ếttqu quả so sánh † Tốt nhất: 0 n−2 3(nn− 1) † Xấu nhất: ∑3(ni−− 1) = i=0 2
24. Shaker sort Cảitii tiến Bubble sort 24 Nhận xét: Bubble sort có các khuy ết điểm: † Không nhận diện được tình trạng dãy đã có thứ tự hay không có thứ tự từngpg phần. † 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. Giải thuật Shaker sort cải tiến các khuyết điểm này.
25. Shaker sort Cảitii tiến Bubble sort 25 Cảitii tiến: † Duyệt mảng theo 2 lượt từ 2 phía khác nhau: „ Lượt đi: đẩypy phần tử nhỏ về đầu mảng „ Lượt về: đẩy phần tử lớn về cuối mảng. † Ghi nhận lại những đoạn đã sắp.
26. Shaker sort Ví d ụ minh hoạ 26 l = 0 r =7 15 2 8 7 3 6 9 17 15 2 8 3 7 6 9 17 15 2 3 8 7 6 9 17 l = 1 r =7 2 15 3 8 7 6 9 17 kk1=1 2 3 15 8 7 6 9 17 2 3 8 15 7 6 9 17 2 3 8 7 15 6 9 17
27. Shaker sort Ví d ụ minh hoạ 27 2 3 8 7 6 15 9 17 l = 1 r =5 2 3 8 7 6 9 15 17 k=5 2 3 8 7 6 9 15 17 2 3 8 6 7 9 15 17 l = 3 r =5 2 3 6 8 7 9 15 17 k=3 2 3 6 7 8 9 15 17
28. Shaker sort 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 l) { 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 ; } l=k; //loại các phần tử đã có thứ tự ở đầu dãy
29. Shaker sort Chương trình (tt) 29 jjl;=l; //đẩyphy phầntn tử lớnvn về cuối while(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 }
30. Selection Sort 30 Mô ph ỏng cách s ắppx xếppt tự nhiên nh ất trong thựcct tế † Chọn phần tử nhỏ nhất và đưa về vị trí đúng là đầu dãy hiện hành. † Sau đó xem dãy hiện hành chỉ còn n-1 phần tử. † Lặp lại cho đến khi dãy hiện hành chỉ còn 1 phần tử.
31. Selection Sort Giảithui thuật 31 Các b ướccc củagia giảithui thuật: 1. i = 0. 2. Tìm a[[]min] nhỏ nhất tronggy 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
32. Selection Sort Ví d ụ 32 i = 0 15 2 8 7 3 6 9 17 i = 1 2 15 8 7 3 6 9 17 i = 2 2 3 8 7 15 6 9 17 i = 3 2 3 6 7 15 8 9 17 i = 4 2 3 6 7 15 8 9 17 i = 5 2 3 6 7 8 15 9 17 i = 6 2 3 6 7 8 9 15 17 i = 7 2 3 6 7 8 9 15 17
33. Selection Sort 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<n-1; i++) { min = i; for(int j = i+1; j<n; j++) { if(a[j] < a[min]) min = j; //ghi nhận lại vị trí } HoanVi(a[min], a[i]); } }
34. Selection Sort Đánh giá 34 void SelectionSort(int a[], int n){ int min; Cho biết số phép gán? 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; } HoanVi(a[min], a[i]); } Nhận xét số phép so } sánh trong vòng for
35. Selection Sort Đánh giá 35 Số phép so sánh: † Tại lượt i bao giờ cũng cần (n-i-1) số lần so sánh † Không ph ụ thuộc vào tình tr ạng dãy s ố ban đầu n−1 n(n −1) Số phép so sánh = ∑(n − i −1) = i=0 2 Số phép gán: n−1 † Tốtnht nhất: ∑ 44= n i=0 n−1 n(n + 7) † Xấu nhất: ∑(4 + n − i −1) = i=0 2
36. Insertion Sort 36 Cách xếp các quâ n bà i dù ng t hu ậtttoá toán Inse setortion Sort: † Tay trái là dãy các quân bài đã có thứ tự, khi cầm 1 quâbàiân bài mớilêi lên thì hìì tìm vị trí đúng của nóóàhèà và chèn vào. † 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.
37. Insertion Sort Giảithui thuật 37 Giảithui thuật: † Xem dãy a0, a1, , an-1 có i phần tử đầu tiên a0, a1, , ai-1 đã có thứ tự. † 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ự. † Cho dãy ban đầu a0, a1, , an-1, có thể xem như đoạn gồm 11h phần tử a0 đã được sắp. † 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 a n-1
38. Insertion Sort Ví d ụ 38 i = 1 15 2 8 7 3 6 9 17 i = 2 2 15 8 7 3 6 9 17 i = 3 2 8 15 7 3 6 9 17 i = 4 2 7 8 15 3 6 9 17 i = 5 2 3 7 8 15 6 9 17 i = 6 2 3 6 7 8 15 9 17 i = 7 2 3 6 7 8 9 15 17
39. Insertion Sort Giảithui thuật 39 Các b ướccc củagia giảithui thuật: 1. Xuất phát từ i = 1. 2. Tìm vị trí pos thích hợppg trong đoạn a[[]0] đến a[i-1] để chèn 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] . 4. a[pos] = a[i] 5T5. Tăng i. 5.1 Nếu i ≤ n: lặp lại bước 2 5.2 Ngược lại: dừng
40. Insertion Sort Chương trình 40 void InsertionSort(int a[], int n) { for(int i=1; i =0 && a[pos] > x) //tìm pos { a[pos+1]=a[pos]; //dờivề sau 1 vị trí pos ; } a[pos+1] = x; } }
41. Insertion Sort Bài tập 41 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. A = {295122015{2, 9, 5, 12, 20, 15, -8, 10}
42. Insertion Sort Nhậnxétn xét 42 Nhậnxét:n xét: † Đoạn a[0] đến a[i-1] luôn luôn được sắp: „ Việc tìm vị trí chèn có thể dùnggg giải thuật tìm kiếm nhị phân. „ 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 ầnnt tử sau x. † Sinh viên tự cài đặt.
43. Insertion Sort Đánh giá 43 void InsertionSort(int a[], int n) { for(int i=1; i =0 && a[pos] > x) ố ầ ặ { S l n l p pos a[pos+1]=a[pos]; pos ; } a[pos+1] = x; } }
44. Insertion Sort Đánh giá 44 So sánh: n −1 † Tốt nhất: ∑ 22(1)= n − i =1 n −1 † Xấu nhất: ∑ 2(1)inn= − i =1 Gán: n−1 † Tốtnht nhất: ∑33= (()n −1) i=1 n −1 nn(1)− † Xấu nhất: ∑ (3+=in ) 3( −+ 1) i =1 2
45. Quick sort 45 Các gi ảiithu thuật Bubble sort, Selection sort , Insertion sort: † Dễ hiểu, dễ cài đặt † Hiệu quả thấp: O(n2) Các gi ảiithu thuậtts sắppx xếppd dựaatrênsosánh: trên so sánh: độ phức tạp ≥ n × log2n. Qui ck sort (C. A . R . H oar e, 1 962 ) có thể đạt được độ phức tạp trên.
46. Quick Sort ÝtÝ tưởng 46 Dựa trên việc phân hoạch dãy ban đầu thành 2 phần: † Dãy con 1: a0, a1,,, , ai có giá trị nhỏ hơnx † Dãy con 2: aj, , an-1 có giá trị lớnhơnx. Dãy ban đầu được phân thành 3 phần: ak x k = 0 i k = i+1 j k = j+1, n-1 ‰ Phần2 đãcóthứ tự ‰ Phần 1, 3: cầnsắpthứ tự, tiến hành phân hoạch từng dãy con theo cáhách phâhân hoạch dãy ban đầu (chia để trị)
47. Quick Sort Giảithui thuật 47 Giải ttuhuật ppâhânhoạch ttàhành 2 dãy con: 1. Chọnphầntử a[k] trong dãy làm giá trị mốc, 0 ≤ k ≤ r-1 x=a[k], i = 0, j = r-1. Thường chọnphầntửở giữa dãy: k = (l+r)/2 2. Phát hiệnvàhiệuchỉnh cặpphầntử a[i], a[j] sai vị trí 2.1 Trong khi ([(a[i] x), giảmj. 2.3 Nếu i<=j thì hoán vị a[i], a[j], tăng i, giảm j 3. Nếu i<j: lặplạibước2 Ngượclại: dừng.
48. Quick Sort Ví d ụ 48 Phân hoạch dãy ban đầu: l = 0, r = 7, x = a[3] i=0, j = 5; i = 2, j = 4 15 2 8 7 3 6 9 17 i = 3j3, j = 3 6 2 3 7 8 15 9 17 Phân hoạch đoạn l = 0, r = 3, x = a[1] i=0, j = 1 6 2 3 7 8 15 9 17 i=1, j = 0 2 6 3 7 8 15 9 17 Phân hoạch đoạn l = 1, r = 3, x = a[2] i=1, j = 2 2 6 3 7 8 15 9 17 i=2, j = 1 2 3 6 7 8 15 9 17
49. Quick Sort Ví d ụ 49 Phân hoạch đoạnl = 2,,,[] r = 3, x = a[2] i=3, j = 1 2 3 6 7 8 15 9 17 Phân hoạch đoạn l = 3, r = 7, x = a[5] i=5, j = 6 2 3 6 7 8 15 9 17 i=6, j = 5 Phân hoạch đoạn l = 3, r = 5, x = a[4] i=5, j = 3 2 3 6 7 8 9 15 17 Phân hoạch đoạn l = 6, r = 7x7, x = a[6] 2 3 6 7 8 9 15 17
50. Quick Sort Chương trình 50 void QuickSort(int a[], int l, int r) { i = l; j = r; x = a[(l+r)/2]; do { while ([(a[i] x) j ; if (i <= j){ HoanVi(a[i], a[j]); i++; j ; } } while (i< j); if (l < j) QuickSort(a, l, j); if (i < r) QuickSort(a, i, r); }
51. Quick Sort Bài tập 51 Chạytaythuy tay thuật toán Quick Sort để sắppx xếppm mảng A trong 2 trường hợp tăng dần và giảm dần. A = {295122015{2, 9, 5, 12, 20, 15, -8, 10}
52. Quick Sort Đánh giá 52 Đánh giá gi ảiithu thuật: † Hiệu quả phụ thuộc vào việc chọn giá trị mốc „ Tốt nhất là phần tử median. „ Nếu phần tử mốc là cực đại hay cực tiểu thì việc phân hoạch không đồng đều. † Tốt nhất: O(n*l og2n) † Trung bình: O(n*log2n) † Xấu nhấtO(t: O(n2)
53. Quick Sort Danh sách liên kết 53 Với danh sách liên k ết: † Quick sort sắp xếp hiệu quả nhất trên danh sách liên kết. † Lưu ý: khi cài đặt trên danh sách liên kết, phần tử mốc duy nhất hợp lý là phần tử đầu xâu.
54. Quick Sort Danh sách liên kết 54 Giảithui thuậttQuick Quick sort cho DSLK: † Bước1: chọnx làmmốclàphầntửđầu DSLK. † Bước 2: Tách DSLK thành 2DSLKconL1(2 DSLK con L1 (các phần tử≤ x), L2 (các phầntử >x). † Bước 3: QuickSort(L1) † Bước 4: QuickSort(L2) † Bước5: Nối L1, X và L2 lại
55. Quick Sort Danh sách liên kết 55 4 9 3 4 2 19 12 Tách L thành L1, X và L2 3 4 2 4 9 19 12 L1 X L2 2 3 4 Tách L1 thành L11, X1 và L12 L11 X1 L12 Nối L11, X, L12 2 3 4
56. Quick Sort Danh sách liên kết 56 Tách L2 thành L21, X2 và L22 9 19 12 X2 L22 Tách L22 thành L221, X22 và L222 12 19 L221 X22 Nối L221 và X22 thành L22 12 19 Nối L21 , X2 và L22 thành L2 9 12 19 Nối L1, X và L2 thành L 2 3 4 4 9 12 19