›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Các thuật toán sắp xếp

pdf 61 trang Đức Chiến 04/01/2024 590
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Các thuật toán sắp xếp", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcau_truc_du_lieu_va_giai_thuat_chuong_3_cac_thuat_toan_sap_x.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Các thuật toán sắp xếp

  1. CHƯƠNG 3 CÁC THUẬT TỐN SẮP XẾP GV Th.S. Thiều Quang Trung Trường Cao đẳng Kinh tế Đối ngoại
  2. Nội dung 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 - Bubble Sort 5 • Sắp xếp dựa trên phân hoạch - Quick Sort 6 • Trộn trực tiếp - Merge Sort GV. Thiều Quang Trung 2
  3. Các khái niệm • Sắp xếp là gì ? – 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 đĩ. • Khái niệm nghịch thế: – Xét một mảng các số a0, a1, ,aN – Giả sử xét mảng cĩ thứ tự tăng dần, nếu cĩ i aj, thì ta gọi đĩ là nghịch thế. GV. Thiều Quang Trung 3
  4. Các khái niệm • Để sắp xếp một mảng => tìm cách giảm số các nghịch thế trong mảng này bằng cách hốn vị các cặp phần tử. • Cho trước một dãy số a1, a2, aN được lưu trữ trong cấu trúc dữ liệu mảng. Ví dụ: int a[N]; => Chọn lựa một số phương pháp để sắp xếp. GV. Thiều Quang Trung 4
  5. Chọn trực tiếp - Selection Sort • Ý tưởng: thực hiện N-1 lần việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đứng ở đầu dãy • Nhận xét: nếu mảng cĩ thứ tự thì phần tử ai luơn là min (ai,ai+1, ,an-1) => Ý tưởng của thuật tốn chọn trực tiếp: – 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 đầu dãy hiện hành; – Sau đĩ khơng quan tâm phần tử này nữa, 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 cho đến khi dãy hiện hành chỉ cịn một phần tử. GV. Thiều Quang Trung 5
  6. Chọn trực tiếp (tt) • Giải thuật : B1: i = 0; B2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n] B3: if (min ≠ i) : hốn vị a[min] và a[i] B4: if (i≤ (n-1): B4.1: i++ B4.2: Lặp lại B2 Ngược lại : dừng // vì n-1 phần tử đã nằm đúng vị trí GV. Thiều Quang Trung 6
  7. 1. Chọn trực tiếp (tt) GV. Thiều Quang Trung 77
  8. 1. Chọn trực tiếp (tt) GV. Thiều Quang Trung 88
  9. Cài đặt giải thuật Chọn trực tiếp 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]); } } GV. Thiều Quang Trung 9
  10. Đánh giá giải thuật Chọn trực tiếp • Ở lượt thứ I, cần (n-i) lần so sánh để tìm 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ình trạng của dãy ban đầu. n−1 n(n−1) • Trong mọi trường hợp số lần so sánh là (n − i) = i=1 2 • Số lần hốn vị (một hố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ố. Trường hợp Số lần so sánh Số phép gán n(n −1) Tốt nhất 2 0 3n(n −1) Xấu nhất 2 GV. Thiều Quang Trung 10
  11. Chèn trực tiếp - Insertion Sort Ý tưởng: • Giả sử dãy {a0,a1, an-1} cĩ k phần tử đầu tiên {a0,a1, ak-1} đã cĩ thứ tự. • Chèn phần tử ak vào k phần tử đầu tiên đã cĩ thứ tự bằng cách tìm vị trí đúng của phần tử k theo giải thuật tìm tuần tự (Sequential Search) → cĩ dãy mới {a0,a1, ,ak-1,ak} cĩ thứ tự. • Vị trí cần chèn ak chính là giữa 2 phần tử ai-1 và ai sao cho ai-1 ≤ ak+1 ≤ ai GV. Thiều Quang Trung 11
  12. Chèn trực tiếp - Insertion Sort (tt) Thuật tốn: B1: k = 1 //Giả sử đoạn a[0] đã sắp xếp B2: x = ak Tìm vị trí pos thích hợp trong đoạn a0 đến ak-1 để chèn ak vào B3: Dời chỗ các phần tử từ apos đến ak-1 sang phải 1 vị trí để dành chỗ cho ak B4: apos = x; // đoạn a0 ak đã được sắp B5: k = k+1 Nếu i<= n: lặp lại B2 Ngược lại : dừng GV. Thiều Quang Trung 12
  13. Ví dụ mơ phỏng chèn trực tiếp • Cho dãy số a : N = 8 ; 12 2 8 5 1 6 4 15 GV. Thiều Quang Trung 1313
  14. Ví dụ mơ phỏng chèn trực tiếp (tt) GV. Thiều Quang Trung 1414
  15. Cài đặt giải thuật Chèn trực tiếp void InsertionSort (int a [ ], int n) { int k=0, i; while (a[k]≤a[k+1] && k 0) { a[i+1] = a[i]; i ; } a[i+1]=x; k++; } return; } GV. Thiều Quang Trung 15
  16. Đánh giá giải thuật Chèn trực tiếp • Trường hợp tốt nhất: khi mảng a ban đầu đã cĩ thứ tự tăng – Số phép gán: Gmin = 2*(n-1) – Số phép so sánh: Smin = 1+2+ + (n-1) = n*(n-1)/2 • Trường hợp xấu nhất: khi mảng a ban đầu luơn cĩ phần tử nhỏ nhất trong n-k phần tử cịn lại – Số phép gán: Gmax = 2*(n-1) + n*(n-1)/2 – Số phép so sánh: Smax = n-1 • Độ phức tạp của thuật tốn: O(n2) GV. Thiều Quang Trung 16
  17. Chèn nhị phân – Binary Insertion Sort Ý tưởng: • Phương pháp chèn nhị phân tương tự phương pháp chèn trực tiếp. • Tuy nhiên, khi thực hiện tìm kiếm vị trí i cho phần tử ai để chèn vào đoạn {a0,a1, ,ai-1} cĩ thể dùng phương pháp tìm kiếm nhị phân (Binary Search) thay cho tìm kiếm tuần tự (Sequential Search) GV. Thiều Quang Trung 17
  18. Cài đặt Binary Insertion Sort void BinaryInsertionSort(int a[], int n ) { int l,r,m,i; int x;//lưu trữ giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử. for(int i=0 ; i l ; j ) a[j] = a[j-1]; // dời chỗ các phần tử sẽ đứng sau x a[l] = x; // chèn x vào dãy } } GV. Thiều Quang Trung 18
  19. Đánh giá Binary Insertion Sort • Phương pháp chèn nhị phân chỉ cải tiến cách tìm kiếm vị trí thích hợp của phần tử a[i], làm giảm số lần so sánh nhưng lại khơng làm thay đổi số lần di chuyển. • Vì vậy việc cải tiến này khơng đáng kể lắm → Độ phức tạp của thuật tốn vẫn là O(n2) GV. Thiều Quang Trung 19
  20. Đổi chỗ trực tiếp - Interchange Sort • Ý tưởng : Ý tưởng chính của giải thuật là xuất phá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 ứng trong cặp nghịch thế. Lặp lại xử lý trên với các phần tử tiếp theo trong dãy. GV. Thiều Quang Trung 2020
  21. 3. Đổi chỗ trực tiếp (tt) • Giải thuật : B1 : i = 1 ; // Bắt đầu từ đầu dãy. B2 : j = i + 1 ; // Tìm các phần tử a[j] i B3 : Trong khi j n thực hiện Nếu a[j] < a[i] : Hốn vị a[i] và a[j] ; j = j +1; B4 :i = i+1; Nếu i < n : lặp lại Bước 2. Ngược lại : Dừng. GV. Thiều Quang Trung 2121
  22. Ví dụ mơ phỏng Đổi chỗ trực tiếp • Cho dãy số a : N = 8 ; 12 2 8 5 1 6 4 15 GV. Thiều Quang Trung 2222
  23. Ví dụ mơ phỏng Đổi chỗ trực tiếp (tt) GV. Thiều Quang Trung 2323
  24. Ví dụ mơ phỏng Đổi chỗ trực tiếp (tt) GV. Thiều Quang Trung 2424
  25. Ví dụ mơ phỏng Đổi chỗ trực tiếp (tt) GV. Thiều Quang Trung 2525
  26. Ví dụ mơ phỏng Đổi chỗ trực tiếp (tt) GV. Thiều Quang Trung 2626
  27. Ví dụ mơ phỏng Đổi chỗ trực tiếp (tt) GV. Thiều Quang Trung 2727
  28. Cài đặt thuật tốn Đổi chỗ trực tiếp void InterchangeSort ( int a[] , int N ) for (int i = 0 ; i < N - 1 ; i ++ ) for (int j = i +1 ; j < N ; j ++) if (a[j] < a[i]) // Nếu cĩ sự sai vị trí thì đổi chỗ swap (a[i],a[j]);  GV. Thiều Quang Trung 2828
  29. Đánh giá giải thuật Đổi chỗ trực tiếp Số lượng các phép so sánh khơng phụ thuộc vào tình trạng của dãy số ban đầu, nhưng số lượng các phép hốn vị phụ thuộc vào kết quả so sánh Trường hợp Số lần so sánh Số lần hốn vị Tốt nhất n(n −1) 0 2 n(n −1) Xấu nhất 2 GV. Thiều Quang Trung 2929
  30. Giải thuật Nổi bọt (Bubble Sort) Ý tưởng : • 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ỏ (lớn) hơn trong cặp phần tử đĩ về vị trí đứng đầu (cuối) dãy hiện hành, sau đĩ sẽ khơng xét đến nĩ ở bước tiếp theo, • Ở lần xử lý thứ i sẽ cĩ vị trí đầu dãy là i. • Lặp lại xử lý trên cho đến khi khơng cịn cặp phần tử nào để xét. GV. Thiều Quang Trung 3030
  31. Giải thuật Nổi bọt (Bubble Sort) Giải thuật : B1: i = 0 ; // Lần xử lý đầu tiên B2: j = N-1 ; // Duyệt từ cuối dãy ngược về vị trí i Trong khi (j > i) thực hiện if a[j] < a[j-1] : swap (a[j], a[j-1]); j = j - 1; B3: i = i + 1; // Lần xử lý kế tiếp Nếu i = n: Hết dãy. Dừng Ngược lại : Lặp lại Bước 2. GV. Thiều Quang Trung 3131
  32. Cài đặt giải thuật Nổi bọt void BubbleSort(int a[], int n) { int i, j; for (i = 0 ; i i ; j ) if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } GV. Thiều Quang Trung 32
  33. Ví dụ mơ phỏng giải thuật Nổi bọt • Cho dãy số a : N = 8 ; 12 2 8 5 1 6 4 15 GV. Thiều Quang Trung 3333
  34. 4. Nổi bọt (tt) GV. Thiều Quang Trung 3434
  35. 4. Nổi bọt (tt) GV. Thiều Quang Trung 3535
  36. 4. Nổi bọt (tt) GV. Thiều Quang Trung 3636
  37. 4. Nổi bọt (tt) GV. Thiều Quang Trung 3737
  38. 4. Nổi bọt (tt) GV. Thiều Quang Trung 3838
  39. Đánh giá thuật tốn Nổi bọ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 hốn vị thực hiện tùy thuộc vào kết quả so sánh Trường hợp Số lần so sánh Số lần hốn vị n(n −1) Tốt nhất 0 2 Xấu nhất GV. Thiều Quang Trung 3939
  40. Sắp xếp dựa trên phân hoạch - Quick Sort • Ý tưởng : Để sắp xếp dãy a1, a2, , an giải thuật QuickSort dựa trên việc phân hoạch dãy ban đầu thành hai phần : Dãy con 1 : gồm các phần tử a1 ai cĩ giá trị nhỏ hơn x. Dãy con 2 : gồm các phần tử ai an cĩ giá trị lớn hơn x. Với x là giá trị của một phần tử tùy ý trong dãy ban đầu. x x x GV. Thiều Quang Trung 4040
  41. Sắp xếp dựa trên phân hoạch (tt) Giải thuật sắp xếp : Cho dãy aL, aL + 1, , aR : B1 : Phân hoạch dãy aL aR thành các dãy con : – Dãy con 1 : aL aj x – Dãy con 2 : aj + 1 ai -1 = x – Dãy con 3 : ai aR x B2 : Nếu (L < j) Phân hoạch dãy aL aj Nếu (i < R) Phân hoạch dãy ai aR GV. Thiều Quang Trung 4141
  42. Sắp xếp dựa trên phân hoạch (tt) Giải thuật phân hoạch: (Phân hoạch dãy aL, aL + 1, , aR thành 2 dãy con) B1 : Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, L k R : x = a[k]; i = L; j = R ; B2 : Phát hiện và hiệu chỉnh cặp phần tử a[i], a[j] nằm sai chỗ B2.1 : Trong khi (a[i] x) j ; B2.3 : Nếu (i < j) Hốn vị a[i] và a[j]; B3 : Nếu i < j : lặp lại bước 2. Ngược lại : Dừng phân hoạch. GV. Thiều Quang Trung 4242
  43. Cài đặt giải thuật sắp Quicksort void QuickSort(int a[], int l, int r) { int i, j, x; x = a[(l+r)/2]; // chọn phần tử giữa làm giá trị mốc i = l; j = r; while(i x) j ; if(i <= j) { Swap(a[i], a[j]); i++ ; j ; } } if (l<j) QuickSort(a, l, j); if (i<r) QuickSort(a, i, r); } GV. Thiều Quang Trung 43
  44. Đánh giá giải thuật Quicksort • Hiệu quả phụ thuộc vào việc chọn giá trị mốc: • Trường hợp tốt nhất: mỗi lần phân hoạch đều chọn phần tử median làm mốc → dãy được chia thành 2 phần bằng nhau → log2(n) lần phân hoạch thì sắp xếp xong. • Nếu mỗi lần phân hoạch chọn phần tử cĩ giá trị cực đại (hay cực tiểu) là mốc → dãy sẽ bị phân chia thành 2 phần khơng đều: một phần chỉ cĩ 1 phần tử, phần cịn lại gồm (n-1) phần tử → n lần phân hoạch mới sắp xếp xong. Trường hợp Độ phức tạp Tốt nhất n*log(n) Trung bình n*log(n) Xấu nhất n2 GV. Thiều Quang Trung 44
  45. 5. Sắp xếp dựa trên phân hoạch (tt) • Ví dụ : Cho dãy số a : N = 8 ; 12 2 8 5 1 6 4 15 GV. Thiều Quang Trung 4545
  46. 5. Sắp xếp dựa trên phân hoạch (tt) Phân hoạch đoạn l = 1, r = 8 : x = a[4] = 5 12 2 8 5 1 6 4 15 l = 1 r = 8 4 2 1 5 8 6 12 15 Phân hoạch đoạn l = 1, r = 3 : x = a[2] = 2 4 2 1 5 8 6 12 15 l = 1 r = 3 1 2 4 5 8 6 12 15 GV. Thiều Quang Trung 4646
  47. 5. Sắp xếp dựa trên phân hoạch (tt) Phân hoạch đoạn l = 5, r = 8 : x = a[6] = 6 1 2 4 5 8 6 12 15 l = 5 r = 8 1 2 4 5 6 8 12 15 Phân hoạch đoạn l = 7, r = 8 : x = a[7] = 12 1 2 4 5 6 8 12 15 l = 7 r = 8 1 2 4 5 6 8 12 15 Dừng GV. Thiều Quang Trung 4747
  48. Giải thuật Trộn trực tiếp - Merge Sort • Ý tưởng : Để sắp xếp dãy a1, a2, , an, giải thuật trộn trực tiếp dựa trên nhận xét sau : – Mỗi dãy a1, a2, , an bất kỳ đều cĩ thể coi như là một tập hợp các dãy con liên tiếp mà mỗi dãy con đều đã cĩ thứ tự. Ví dụ dãy 12, 2, 8, 5, 1, 6, 4, 15 cĩ thể coi như gồm 5 dãy con khơng giảm (12); (2, 8); (5); (1, 6); (4, 15). – Dãy đã cĩ thứ tự coi như cĩ 1 dãy con. GV. Thiều Quang Trung 4848
  49. Giải thuật Trộn trực tiếp - Merge Sort (tt) ▪ Cách tiếp cận để sắp xếp dãy là tìm cách làm giảm số dãy con khơng giảm của nĩ => Phân hoạch dãy ban đầu thành các dãy con. ▪ Sau khi phân hoạch xong, dãy ban đầu sẽ được tách ra thành 2 dãy phụ theo nguyên tắc phân phối đều luân phiên. ▪ Trộn từng cặp dãy con của 2 dãy phụ thành một dãy con của dãy ban đầu, ta sẽ nhận lại dãy ban đầu nhưng với số lượng dãy con ít nhất giảm đi một nửa. ▪ Lặp lại quá trình trên sau một số bước, ta sẽ nhận được một dãy gồm 1 dãy con khơng giảm. Nghĩa là dãy ban đầu đã được sắp xếp. GV. Thiều Quang Trung 4949
  50. Giải thuật Trộn trực tiếp - Merge Sort (tt) ▪ Giải thuật trộn là phương pháp đơn giản nhất. Việc phân hoạch thành các dãy con đơn giản là tách dãy gồm n phần tử thành n dãy con. Cứ mỗi lần tách rồi trộn, chiều dài của các dãy con sẽ được nhân đơi. GV. Thiều Quang Trung 5050
  51. Giải thuật Trộn trực tiếp - Merge Sort (tt) Giải thuật : B1 : k = 1; // k là chiều dài của dãy con trong bước hiện hành B2 : Tách dãy a1, a2, , an thành 2 dãy b, c theo nguyên tắc luân phiên từng nhĩm k phần tử : b = a1, , ak, a2k +1, a3k, c = ak + 1, , a2k, a3k +1, a4k, B3 : Trộn từng cặp dãy con gồm k phần tử của 2 dãy b, c vào a. B4 : k = k * 2; Nếu k < n thì trở lại bước 2. Ngược lại : Dừng. GV. Thiều Quang Trung 5151
  52. Ví dụ mơ phỏng giải thuật Merge Sort • Cho dãy số a : N = 8 ; 12 2 8 5 1 6 4 15 GV. Thiều Quang Trung 5252
  53. Ví dụ mơ phỏng giải thuật Merge Sort (tt) GV. Thiều Quang Trung 5353
  54. Cài đặt giải thuật Merge Sort void MergeSort (int a[], int N) int pa, pb, pc;// các chỉ số trên các mảng a,b,c int i, k = 1; // độ dài của dãy con khi phân hoạch int b [N], c[N]; // hai mảng phụ do // tách a thành b và c pa = pb = pc = 0; while (pa < N) for (i = 0 ; (pa < N) && (i < k) ; i++) b [pb++] = a [pa++]; for (i = 0 ; (pa < N) && (i < k) ; i ++) c [pc++] = a [pa++]  Merge (a, b, c, pb, pc, k); // trộn b, c lại thành a k * = 2;  while (k < N);  GV. Thiều Quang Trung 5454
  55. Cài đặt giải thuật Merge Sort (tt) void Merge ( int a [], int b [], int c [], int nb, int nc, int k) int pa, pb, pc, ib, ic, kb, kc; pa = pb = pc = 0 ; ib = ic = 0 ; while ((nb > 0) && (nc > 0)) kb = min (k, nb) ; kc = min (k, nc) ; if (b [pb + ib] <= c [pc + ic]) a [pa++] = b [pb + ib]; ib ++; if (ib = = kb) for (; ic < kc ; ic ++ ) a [pa ++] = c [pc + ic] ; pb += kb ; pc += kc ; ib = ic = 0 ; nb −= kb ; nc −= kc;  GV. Thiều Quang Trung 5555
  56. Cài đặt giải thuật Merge Sort (tt)  else a [pa ++] = c [pc + ic] ; ic ++; if (ic = = kc) for (; ib < kb ; ib ++) a [pa ++] = b [pb + ib] ; pb += kb ; pc += kc ; ib = ic = 0; nb −= kb ; nc −= kc ;     GV. Thiều Quang Trung 5656
  57. Đánh giá giải thuật Merge Sort • Số lần lặp của bước 2 và bước 3 là log2n do sau mỗi lần lặp giá trị của k tăng lên gấp đơi. • Chi phí thực hiện của giải thuật trộn là nlog2n. • Do khơng sử dụng thơng tin nào về đặc tính của dãy cần sắp xếp, nên trong mọi trường hợp của thuật tốn chi phí là khơng đổi. Đây chính là một trong những nhược điểm lớn của thuật tốn. GV. Thiều Quang Trung 5757
  58. So sánh các phương pháp sắp xếp STT Phương pháp Độ phức tạp 1 Chèn trực tiếp – InsertionSort O(n2) 2 Chèn nhị phân – Binary InsertionSort O(n2) 3 Chọn trực tiếp - SelectionSort O(n2) 4 Nổi bọt – BubbleSort O(n2) 5 QuickSort O(nlogn) 6 MergeSort O(nlogn) GV. Thiều Quang Trung 58
  59. Bài tập thực hành • Bài 1: Cho dãy số dùng mảng lưu trữ. Viết chương trình sắp xếp bằng phương pháp chọn trực tiếp (Selection Sort). In ra dãy số trước khi sắp và sau khi sắp. • Bài 2: Cho dãy số dùng mảng lưu trữ. Viết chương trình sắp xếp bằng phương pháp chèn trực tiếp (Insertion Sort). In ra dãy số trước khi sắp và sau khi sắp. • Bài 3: Cho dãy số dùng mảng lưu trữ. Viết chương trình sắp xếp bằng phương pháp đổi chổ trực tiếp (Interchange Sort). In ra dãy số trước khi sắp và sau khi sắp. GV. Thiều Quang Trung 5959
  60. Bài tập thực hành (tt) • Bài 4: Cho dãy số dùng mảng lưu trữ. Viết chương trình sắp xếp bằng phương pháp nổi bọt (Bubble Sort). In ra dãy số trước khi sắp và sau khi sắp. • Bài 5: Cho dãy số dùng mảng lưu trữ. Viết chương trình sắp xếp bằng phương pháp theo nguyên tắc trộn (Merge Sort). In ra dãy số trước khi sắp và sau khi sắp. • Bài 6: Cho dãy số dùng mảng lưu trữ. Viết chương trình sắp xếp bằng phương pháp hiệu quả cao (Quick Sort). In ra dãy số trước khi sắp và sau khi sắp. GV. Thiều Quang Trung 6060
  61. GV. Thiều Quang Trung