›
›

Cấu trúc dữ liệu và giải thuật - Chương 2: Tìm kiếm và sắp xếp nội

pdf 186 trang phuongnguyen 3600
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cấu trúc dữ liệu và giải thuật - Chương 2: Tìm kiếm và sắp xếp nội", để 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_2_tim_kiem_va_sap_xep.pdf

Nội dung text: Cấu trúc dữ liệu và giải thuật - Chương 2: Tìm kiếm và sắp xếp nội

  1. CHƢƠNG 2 TÌM KIẾM VÀ SẮP XẾP NỘI CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 1
  2. Nội Dung  Các giải thuật tìm kiếm nội 1. Tìm kiếm tuyến tính 2. Tìm kiếm nhị phân  Các giải thuật sắp xếp nội 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 2
  3. Nội Dung (Tt) 4. Chèn trực tiếp – Insertion Sort 5. Chèn nhị phân – Binary Insertion Sort 6. Shaker Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 3
  4. Bài Tốn Tìm Kiếm  Cho danh sách cĩ n phần tử a0, a1, a2 , an-1.  Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách các phần tử nĩi trên trong bộ nhớ chính.  Tìm phần tử cĩ khố bằng X trong mảng . Giải thuật tìm kiếm tuyến tính (tìm tuần tự) . Giải thuật tìm kiếm nhị phân  Lưu ý: Trong quá trình trình bày thuật giải ta dùng ngơn ngữ lập trình C. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 4
  5. Tìm Kiếm Tuyến Tính  Ý tƣởng : So sánh X lần lượt với phần tử thứ 1, thứ 2, của mảng a cho đến khi gặp được khĩa cần tìm, hoặc tìm hết mảng mà khơng thấy.  Các bƣớc tiến hành • Bước 1: Khởi gán i=0; • Bước 2: So sánh a[i] với giá trị x cần tìm, cĩ 2 khả năng + a[i] == x tìm thấy x. Dừng; + a[i] != x sang bước 3; • Bước 3: i=i+1 // Xét tiếp phần tử kế tiếp trong mảng Nếu i==N: Hết mảng. Dừng; Ngược lại: Lặp lại bước 2; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 5
  6. Thuật Tốn Tìm Kiếm Tuyến Tính  Hàm trả về 1 nếu tìm thấy, ngược lại trả về 0: int LinearSearch(int a[],int n, int x) { int i=0; while((i<n)&&(a[i]!=x)) i++; if(i==n) return 0; //Tìm khơng thấy x else return 1; //Tìm thấy } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 6
  7. Minh Họa Thuật Tốn Tìm Kiếm Tuyến Tính X=6 Tìm thấy 6 tại vị trí 4 i 2 8 5 1 6 4 6 0 1 2 3 4 5 6 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 7
  8. Minh Họa Thuật Tốn Tìm Kiếm Tuyến Tính (tt) X=10 i=7, khơng tìm thấy i 2 8 5 1 6 4 6 0 1 2 3 4 5 6 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 8
  9. Ðánh Giá Thuật Tốn Tìm Tuyến Tính Trường hợp Css Tốt nhất 1 Xấu nhất N Trung bình (N+1) / 2  Độ phức tạp O(N) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 9
  10. Cải Tiến Thuật Tốn Tìm Tuyến Tính  Nhận xét: Số phép so sánh của thuật tốn trong trường hợp xấu nhất là 2*n.  Để giảm thiểu số phép so sánh trong vịng lặp cho thuật tốn, ta thêm phần tử “lính canh” vào cuối dãy. int LinearSearch(int a[],int n, int x) { int i=0; a[n]=x; // a[n] là phần tử “lính canh” while(a[i]!=x) i++; if(i==n) return 0; // Tìm khơng thấy x else return 1; // Tìm thấy } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 10
  11. Thuật Tốn Tìm Kiếm Nhị Phân  Được áp dụng trên mảng đã cĩ thứ tự.  Ý tƣởng: . . Giả xử ta xét mảng cĩ thứ tự tăng, khi ấy ta cĩ ai-1 ai thì X chỉ cĩ thể xuất hiện trong đoạn [ai+1, an-1] . Nếu X<ai thì X chỉ cĩ thể xuất hiện trong đoạn [a0, ai-1] . Ý tưởng của giải thuật là tại mỗi bước ta so sánh X với phần tử đứng giữa trong dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này mà ta quyết định giới hạn dãy tìm kiếm ở nữa dưới hay nữa trên của dãy tìm kiếm hiện hành. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 11
  12. Các Bƣớc Thuật Tốn Tìm Kiếm Nhị Phân  Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử nằm trong aleft, aright, các bước của giải thuật như sau:  Bước 1: left=0; right=N-1;  Bước 2: . mid=(left+right)/2; //chỉ số phần tử giữa dãy hiện hành . So sánh a[mid] với x. Cĩ 3 khả năng • a[mid]= x: tìm thấy. Dừng • a[mid]>x : Right= mid-1; • a[mid]<x : Left= mid+1;  Bước 3: Nếu Left <=Right ; // cịn phần tử trong dãy hiện hành + Lặp lại bước 2 Ngược lại : Dừng CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 12
  13. Cài Đặt Thuật Tốn Tìm Nhị Phân  Hàm trả về giá trị 1 nếu tìm thấy, ngược lại hàm trả về giá trị 0 int BinarySearch(int a[],int n,int x) { int left, right, mid; left=0; right=n-1; do{ mid=(left+right)/2; if(a[mid]==x) return 1; else if(a[mid]<x) left=mid+1; else right=mid-1; }while(left<=right); return 0; } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 13
  14. Ðánh Giá Thuật Tốn Tìm Tuyến Tính Trường hợp Css Tốt nhất 1 Xấu nhất log2N Trung bình log2N / 2  Độ phức tạp O(log2N) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 14
  15. Minh Họa Thuật Tốn Tìm Nhị Phân Tìm thấy 2 tại vị trí 1 X=2 L M R 1 2 4 6 7 9 10 0 1 2 3 4 5 6 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 15
  16. Minh Họa Thuật Tốn Tìm Nhị Phân (tt) X=-1 L M R 1 2 4 6 7 9 10 0 1 2 3 4 5 6 L=0 R=-1 => khơng tìm thấy X=-1 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 16
  17. Bài Tốn Sắp Xếp  Cho danh sách cĩ n phần tử a0, a1, a2 , an-1.  Sắp xếp là quá trình xử lý các phần tử trong danh sách để đặt chúng theo một thứ tự thỏa mãn một số tiêu chuẩn nào đĩ dựa trên thơng tin lưu tại mỗi phần tử, như: . Sắp xếp danh sách lớp học tăng theo điểm trung bình. . Sắp xếp danh sách sinh viên tăng theo tên. .  Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách trên trong bộ nhớ chính. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 17
  18. Bài Tốn Sắp Xếp (tt)  a: là dãy các phần tử dữ liệu  Để sắp xếp dãy a theo thứ tự (giả sử theo thứ tự tăng), ta tiến hành triệt tiêu tất cả các nghịch thế trong a. . Nghịch thế: • Cho dãy cĩ n phần tử a0, a1, ,an-1 • Nếu i aj 34 3 4 8 a[0], a[1] là cặp nghịch thế  Đánh giá độ phức tạp của giải thuật, ta tính Css: Số lượng phép so sánh cần thực hiện CHV: Số lượng phép hốn vị cần thực hiện CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 18
  19. Các Thuật Tốn Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 19
  20. Các Thuật Tốn Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 20
  21. Đổi Chỗ Trực Tiếp – Interchange Sort  Ý tƣởng: Xuất phát từ đầu dãy, tìm tất các các nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ 2 phần tử trong cặp nghịch thế. Lặp lại xử lý trên với phần tử kế trong dãy. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 21
  22. Các Bƣớc Tiến Hành  Bước 1: i = 0; // bắt đầu từ đầu dãy  Bước 2: j = i+1; //tìm các nghịch thế với a[i]  Bước 3: Trong khi j < N thực hiện Nếu a[j]<a[i] //xét cặp a[i], a[j] Swap(a[i],a[j]); j = j+1;  Bước 4: i = i+1; Nếu i < N-1: Lặp lại Bước 2. Ngược lại: Dừng. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 22
  23. Đổi Chỗ Trực Tiếp – Interchange Sort  Cho dãy số a: 12 2 8 5 1 6 4 15 i=0 j=1 i=0 j=4 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 23
  24. Đổi Chỗ Trực Tiếp – Interchange Sort i=1 j=2 i=1 j=3 i=1 j=4 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 24
  25. Đổi Chỗ Trực Tiếp – Interchange Sort i=2 j=3 i=2 j=4 i=2 j=6 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 25
  26. Đổi Chỗ Trực Tiếp – Interchange Sort i=3 j=4 i=3 j=5 i=3 j=6 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 26
  27. Đổi Chỗ Trực Tiếp – Interchange Sort i=4 j=5 i=4 j=6 i=5 j=6 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 27
  28. Đổi Chỗ Trực Tiếp – Interchange Sort i=6 j=7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 28
  29. Cài Đặt Đổi Chỗ Trực Tiếp void InterchangeSort(int a[], int N ) { int i, j; for (i = 0 ; i<N-1 ; i++) for (j =i+1; j < N ; j++) if(a[j ]< a[i]) // Thỏa 1 cặp nghịch thế Swap(a[i], a[j]); } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 29
  30. Minh Họa Thuật Tốn j 121 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 30
  31. Minh Họa Thuật Tốn j 1 122 8 5 2 6 4 15 00 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 31
  32. Minh Họa Thuật Tốn j 1 2 124 8 5 6 4 15 0 10 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 32
  33. Minh Họa Thuật Tốn j 1 2 4 125 8 6 5 15 0 1 20 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 33
  34. Minh Họa Thuật Tốn 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 34
  35. Độ Phức Tạp Của Thuật Tốn CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 35
  36. Các Thuật Tốn Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 36
  37. Chọn Trực Tiếp – Selection Sort  Ý tƣởng: . Chọn phần tử nhỏ nhất trong N phần tử trong dãy hiện hành ban đầu. . Đưa phần tử này về vị trí đầ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 hiện hành 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ử CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 37
  38. Các Bƣớc Của Thuật Tốn Chọn Trực Tiếp  Bước 1: i = 0;  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 : Đổi chỗ a[min] và a[i]  Bước 4 : Nếu i < N-1 thì i = i+1; Lặp lại Bước 2; Ngược lại: Dừng. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 38
  39. Chọn Trực Tiếp – Selection Sort  Cho dãy số a: 12 2 8 5 1 6 4 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 39
  40. Chọn Trực Tiếp – Selection Sort i=0 i=1 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 40
  41. Chọn Trực Tiếp – Selection Sort i=2 i=3 i=4 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 41
  42. Chọn Trực Tiếp – Selection Sort i=5 i=6 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 42
  43. Cài Đặt Thuật Tốn Chọn Trực Tiếp void SelectionSort(int a[],int n ) { int min,i,j; // chỉ số phần tử nhỏ nhất trong dãy hiện hành for (i=0; i<n-1 ; i++) //chỉ số đầu tiên của dãy hiện hành { min = i; for(j = i+1; j <N ; j++) if (a[j ] < a[min]) min = j; // lưu vtrí phần tử hiện nhỏ nhất Swap(a[min],a[i]); } } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 43
  44. Minh Họa Thuật Tốn Chọn Trực Tiếp Vị trí nhỏ nhất(0,7) Swap(a[0], a[4]) min 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 44
  45. Minh Họa Thuật Tốn Chọn Trực Tiếp Vị trí nhỏ nhất(1,7) Swap(a[1], a[1]) min 1 2 8 5 12 6 4 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 45
  46. Minh Họa Thuật Tốn Chọn Trực Tiếp Vị trí nhỏ nhất(2,7) Swap(a[2], a[6]) min 1 2 8 5 12 6 4 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 46
  47. Minh Họa Thuật Tốn Chọn Trực Tiếp Vị trí nhỏ nhất(3, 7) Swap(a[3], a[3]) min 1 2 4 5 12 6 8 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 47
  48. Minh Họa Thuật Tốn Chọn Trực Tiếp Vị trí nhỏ nhất(4, 7) Swap(a[4], a[5]) min 1 2 4 5 12 6 8 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 48
  49. Minh Họa Thuật Tốn Chọn Trực Tiếp Vị trí nhỏ nhất(5,7) Swap(a[5], a[6]) min 1 2 4 5 6 12 8 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 49
  50. Minh Họa Thuật Tốn Chọn Trực Tiếp Vị trí nhỏ nhất(6, 7) min 1 2 4 5 6 8 12 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 50
  51. Độ Phức Tạo Của Thuật Tốn  Ðánh giá giải thuật n 1 nn( 1) số lần so sánh  (ni ) i 1 2 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 51
  52. Các Thuật Tốn Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 52
  53. Nổi Bọt – Bubble Sort  Ý tƣởng: . Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đĩ về vị trí đúng đầu dãy hiện hành, sau đĩ sẽ khơng xét đến nĩ ở bước tiếp theo, do vậy ở 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. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 53
  54. Nổi Bọt – Bubble Sort  Bước 1 : i = 0; // lần xử lý đầu tiên  Bước 2 : j = N-1;//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] =N-1: Hết dãy. Dừng Ngược lại : Lặp lại Bước 2. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 54
  55. Nổi Bọt – Bubble Sort  Cho dãy số a: 2 12 8 5 1 6 4 15 i=0 j=6 i=0 i=4 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 55
  56. Nổi Bọt – Bubble Sort i=0 j=3 i=0 j=2 i=0 j=1 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 56
  57. Nổi Bọt – Bubble Sort i=1 j=5 i=1 j=4 i=1 j=3 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 57
  58. Nổi Bọt – Bubble Sort i=2 j=5 i=2 j=4 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU i=358 j=6
  59. Nổi Bọt – Bubble Sort i=3 j=5 i=4 j=6 i=5 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 59
  60. Cài Đặt Thuật Tốn 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])// nếu sai vị trí thì đổi chỗ Swap(a[j], a[j-1]); } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 60
  61. Minh Họa Thuật Tốn j 121 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 61
  62. Minh Họa Thuật Tốn j 1 122 2 8 5 4 6 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 62
  63. Minh Họa Thuật Tốn j 1 2 124 4 8 5 6 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 63
  64. Minh Họa Thuật Tốn j 1 2 4 125 8 5 6 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 64
  65. Minh Họa Thuật Tốn j 1 2 4 5 126 8 6 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 65
  66. Minh Họa Thuật Tốn j 1 2 4 5 6 128 8 15 0 1 2 3 4 5 6 7 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 66
  67. Minh Họa Thuật Tốn j 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 67
  68. Độ Phức Tạp Của Thuật Tốn Nổi Bọt CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 68
  69. Các Thuật Tốn Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 69
  70. Shaker Sort  Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phía khác nhau: . Lượt đi: đẩy 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 xếp nhằm tiết kiệm các phép so sánh thừa. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 70
  71. Các Bƣớc Của Thuật Tốn  Bước 1: l=0; r=n-1;//đoạn l->r là đoạn cần được sắp xếp k=n;//ghi nhận vị trí k xảy ra hốn vị sau cùng để làm cơ sơ thu hẹp đoạn l->r  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] thì Doicho(a[j],a[j+1]) j++ r=k;//loại 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 Ngược lại: dừng CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 71
  72. Cài Đặt Thuật Tốn Shaker Sort void ShakeSort(int a[],int n) { int i, j; int left, right, k; left = 0; right = n-1; k = n-1; while (left left; j ) if (a[j] a[j+1]) {Swap(a[j], a[j-1]);k = j; } right = k; } } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 72
  73. Các Thuật Tốn Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 73
  74. Chèn Trực Tiếp – Insertion Sort  Giả sử cĩ một dãy a0 , a1 , ,an-1 trong đĩ 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 của đoạn đã được sắp để cĩ dãy mới a0 , a1, ,ai trở nên cĩ thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak-1 và ak thỏa ak-1 < ai < ak (1≤k≤i). CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 74
  75. Chèn Trực Tiếp – Insertion Sort  Bước 1: i = 1;//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-1] để chèn a[i] 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 a[i]  Bước 4: a[pos] = x; //cĩ đoạn a[1] a[i] đã được sắp  Bước 5: i = i+1; Nếu i < n : Lặp lại Bước 2 Ngược lại : Dừng CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 75
  76. Chèn Trực Tiếp – Insertion Sort  Cho dãy số : 12 2 8 5 1 6 4 15 i=1 i=2 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 76
  77. Chèn Trực Tiếp – Insertion Sort i=3 i=4 i=5 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 77
  78. Chèn Trực Tiếp – Insertion Sort i=6 i=7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 78
  79. Cài Đặt Thuật Tốn Chèn Trực Tiếp void InsertionSort(int d, int n ) { int pos, i; int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử. for(i=1 ; i = 0)&&(a[pos] > x)) {//kết hợp dời chỗ các phần tử sẽ đứng sau x trong dãy mới a[pos+1] = a[pos]; pos ; } a[pos+1] = x]; // chèn x vào dãy } } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 79
  80. Minh Họa Thuật Tốn Insertion Sort 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 80
  81. Minh Họa Thuật Tốn Insertion Sort Insert a[1] into (0,0) pos 122 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 i x CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 81
  82. Minh Họa Thuật Tốn Insertion Sort Insert a[2] into (0, 1) pos 2 128 8 5 1 6 4 15 0 1 2 3 4 5 6 7 i x CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 82
  83. Minh Họa Thuật Tốn Insertion Sort Insert a[3] into (0, 2) pos 2 85 12 5 1 6 4 15 0 1 2 3 4 5 6 7 i x CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 83
  84. Minh Họa Thuật Tốn Insertion Sort Insert a[4] into (0, 3) pos 12 5 8 12 1 6 4 15 0 1 2 3 4 5 6 7 i x CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 84
  85. Minh Họa Thuật Tốn Insertion Sort Insert a[5] into (0, 4) pos 1 2 5 86 12 6 4 15 0 1 2 3 4 5 6 7 i x CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 85
  86. Minh Họa Thuật Tốn Insertion Sort Insert a[6] into (0, 5) pos 1 2 45 6 8 12 4 15 0 1 2 3 4 5 6 7 i x CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 86
  87. Minh Họa Thuật Tốn Insertion Sort Insert a[8] into (0, 6) pos 1 2 4 5 6 8 12 1515 0 1 2 3 4 5 6 7 i x CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 87
  88. Minh Họa Thuật Tốn Insertion Sort pos 1 2 4 5 6 8 12 15 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 88
  89. Độ Phức Tạp Của Insertion Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 89
  90. Các Thuật Tốn Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 90
  91. Chèn Nhị Phân – Binary Insertion Sort void BInsertionSort(int a[],int n ) { int l,r,m,i; int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử. for(int i=1 ; i =l ; j ) a[j+1] = a[j];// dời các phần tử sẽ đứng sau x a[l] = x; // chèn x vào dãy } } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 91
  92. Các Thuật Tốn Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 92
  93. Shell Sort  Cải tiến của phương pháp chèn trực tiếp  Ý tưởng: . Phân hoạch dãy thành các dãy con . Sắp xếp các dãy con theo phương pháp chèn trực tiếp . Dùng phương pháp chèn trực tiếp sắp xếp lại cả dãy. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 93
  94. Shell Sort  Phân chia dãy ban đầu thành những dãy con gồm các phần tử ở cách nhau h vị trí  Dãy ban đầu : a1, a2, , an được xem như sự xen kẽ của các dãy con sau : . Dãy con thứ nhất : a1 ah+1 a2h+1 . Dãy con thứ hai : a2 ah+2 a2h+2 . . Dãy con thứ h : ah a2h a3h CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 94
  95. Shell Sort  Tiến hành sắp xếp các phần tử trong cùng dãy con sẽ làm cho các phần tử được đưa về vị trí đúng tương đối  Giảm khoảng cách h để tạo thành các dãy con mới  Dừng khi h=1 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 95
  96. Shell Sort  Giả sử quyết định sắp xếp k bước, các khoảng cách chọn phải thỏa điều kiện : hi > hi+1 và hk = 1  hi = (hi-1 - 1)/3 và hk = 1, k = log3n-1 Ví dụ :127, 40, 13, 4, 1  hi = (hi-1 - 1)/2 và hk = 1, k = log2n-1 Ví dụ : 15, 7, 3, 1 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 96
  97. Shell Sort  h cĩ dạng 3i+1: 364, 121, 40, 13, 4, 1  Dãy fibonaci: 34, 21, 13, 8, 5, 3, 2, 1  h là dãy các số nguyên tố giảm dần đến 1: 13, 11, 7, 5, 3, 1. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 97
  98. Shell Sort  Bước 1: Chọn k khoảng cách h[1], h[2], , h[k]; i = 1;  Bước 2: Phân chia dãy ban đầu thành các dãy con cách nhau h[i] khoảng cách. Sắp xếp từng dãy con bằng phương pháp chèn trực tiếp;  Bước 3 : i = i+1; Nếu i > k : Dừng Ngược lại : Lặp lại Bước 2. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 98
  99. Shell Sort  Cho dãy số a: 12 2 8 5 1 6 4 15  Giả sử chọn các khoảng cách là 5, 3, 1 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 99
  100. Shell Sort  h = 5 : xem dãy ban đầu như các dãy con CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 100
  101. Shell Sort  h = 3 : (sau khi đã sắp xếp các dãy con ở bước trước) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 101
  102. Shell Sort  h = 1 : (sau khi đã sắp xếp các dãy con ở bước trước CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 102
  103. Shell Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 103
  104. Shell Sort void ShellSort(int a[],int n, int h[], int k) { int step,i,j, x,len; for (step = 0 ; step =0)// sắp xếp dãy con chứa x { // bằng phương pháp chèn trực tiếp a[j+len] = a[j]; j = j - len; } a[j+len] = x; } } } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 104
  105. Shell Sort – Ví Dụ h = (5, 3, 1); k = 3 len = 5 joint curr 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 105
  106. Shell Sort – Ví Dụ h = (5, 3, 1); k = 3 len = 5; 6 2 8 5 1 12 4 15 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 106
  107. Shell Sort – Ví Dụ h = (5, 3, 1); k = 3 len = 3 joint curr 6 2 15 5 1 12 4 8 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 107
  108. Shell Sort – Ví Dụ h = (5, 3, 1); k = 3 len = 3 joint joint curr 5 1 12 6 2 15 4 8 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 108
  109. Shell Sort – Ví Dụ h = (5, 3, 1); k = 3 len = 3 4 1 12 5 2 15 6 8 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 109
  110. Shell Sort – Ví Dụ h = (5, 3, 1); k = 3 len = 1 joint jointcurr joint 4 1 12 5 2 15 6 8 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 110
  111. Shell Sort – Ví Dụ h = (5, 3, 1); k = 3 len = 1 joint joint joint joint jointcurr joint joint 1 4 5 12 2 15 6 8 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 111
  112. Shell Sort – Ví Dụ 1 2 4 5 6 8 12 15 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 112
  113. Các Thuật Tốn Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 113
  114. Thuật Tốn Sắp Xếp Heap Sort  Heap Sort tận dụng được các phép so sánh ở bước i-1, mà thuật tốn sắp xếp chọn trực tiếp khơng tận dụng được  Để làm được điều này Heap sort thao tác dựa trên cây. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 114
  115. Thuật Tốn Sắp Xếp Heap Sort Xét dãy số: 5 2 6 4 8 1 8 6 8 5 6 8 -∞ 5 2 6 4 8 1 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 115
  116. Thuật tốn sắp xếp Heap Sort  Ở cây trên, phần tử ở mức i chính là phần tử lớn trong cặp phần tử ở mức i +1, do đĩ phần tử ở nút gốc là phần tử lớn nhất.  Nếu loại bỏ gốc ra khỏi cây, thì việc cập nhật cây chỉ xãy ra trên những nhấn liên quan đến phần tử mới loại bỏ, cịn các nhánh khác thì bảo tồn.  Bước kế tiếp cĩ thể sử dụng lại kết quả so sánh của bước hiện tại.  Vì thế độ phức tạp của thuật tốn O(nlog2n) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 116
  117. Các Bƣớc Thuật Tốn  Giai đoạn 1 : Hiệu chỉnh dãy số ban đầu thành heap  Giai đoạn 2: Sắp xếp dãy số dựa trên heap:  Bước 1:Đưa phần tử lớn nhất về vị trí đúng ở cuối dãy: r = n; Hốnvị (a1 , ar );  Bước 2: Loại bỏ phần tử lớn nhất ra khỏi heap: r = r-1; Hiệu chỉnh phần cịn lại của dãy từ a1 , a2 ar thành một heap.  Bước 3: Nếu r>1 (heap cịn phần tử ): Lặp lại Bước 2 Ngược lại : Dừng CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 117
  118. Minh Họa Thuật Tốn  Heap: Là một dãy các phần tử al , a2 , , ar thoả các quan hệ với mọi i [l, r]:  A i A 2i  A i A 2i+1 // (Ai , A 2i+1), (Ai , A 2i+2 ) là các cặp phần tử liên đới  Cho dãy số : 12 2 8 5 1 6 4 15 Giai đoạn 1: Hiệu chỉnh dãy ban đầu thành Heap 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 Pt liên l=3 đới CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 118
  119. Minh Họa Thuật Tốn 12 2 8 15 1 6 4 5 0 1 2 3 4 5 6 7 l=2 Pt liên đới 12 2 8 15 1 6 4 5 0 1 2 3 4 5 6 7 l=1 Pt liên đới CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 119
  120. Minh Họa Thuật Tốn 12 15 8 2 1 6 4 5 0 1 2 3 4 5 6 7 Lan truyền việc điều chỉnh l=1 12 15 8 5 1 6 4 2 0 1 2 3 4 5 6 7 l=0 Pt liên đới CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 120
  121. Minh Họa Thuật Tốn 15 12 8 5 1 6 4 2 0 1 2 3 4 5 6 7 Giai đoạn 2: Sắp xếp dãy số dựa trên Heap 15 12 8 5 1 6 4 2 0 1 2 3 4 5 6 7 2 12 8 5 1 6 4 15 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 121 r=6
  122. Minh Họa Thuật Tốn Hiệu chỉnh Heap 2 12 8 5 1 6 4 15 0 1 2 3 4 5 6 7 l=2 Pt liên đới 2 12 8 5 1 6 4 15 0 1 2 3 4 5 6 7 l=2 Pt liên đới CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 122
  123. Minh Họa Thuật Tốn 2 12 8 5 1 6 4 15 0 1 2 3 4 5 6 7 l=0 Pt liên đới 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 l=2 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 123
  124. Minh Họa Thuật Tốn Lan truyền việc điều chỉnh 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 l=2 12 5 8 2 1 6 4 15 0 1 2 3 4 5 6 7 l=2 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 124
  125. Minh Họa Thuật Tốn 12 5 8 2 1 6 4 15 0 1 2 3 4 5 6 7 4 5 8 2 1 6 12 15 0 1 2 3 4 5 6 7 Thực hiện với r= 5,4,3,2 ta được 1 2 4 5 6 8 12 15 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 125
  126. Cài Đặt Thuật Tốn  Hiệu chỉnh al, al+1, ,ar thành Heap void shift(int a[],int l,int r) { int x,i,j; i=l; j=2*i+1; x=a[i]; while(j<=r) { if(j<r) if(a[j]<a[j+1]) //tim phan tu lon nhat a[j] va a[j+1] CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 126
  127. Cài Đặt Thuật Tốn j++; //luu chi so cua phan tu nho nhat trong hai phan tu if(a[j]<=x) return; else { a[i]=a[j]; a[j]=x; i=j; j=2*i+1; x=a[i]; } } } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 127
  128. Cài Đặt Thuật Tốn  Hiệu chỉnh a0, an-1Thành Heap void CreateHeap(int a[],int n) { int l; l=n/2-1; while(l>=0) { shift(a,l,n-1); l=l-1; } } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 128
  129. Cài Đặt Thuật Tốn  Hàm HeapSort void HeapSort(int a[],int n) { int r; CreateHeap(a,n); r=n-1; while(r>0) { Swap(a[0],a[r]);//a[0] la nút gốc r ; if(r>0) shift(a,0,r); } } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 129
  130. Các Thuật Tốn Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 130
  131. Quick Sort  Ý tưởng: . Giải thuật QuickSort sắp xếp dãy a1, a2 , aN dựa trên việc phân hoạch dãy ban đầu thành 3 phần : • Phần 1: Gồm các phần tử cĩ giá trị bé hơn x • Phần 2: Gồm các phần tử cĩ giá trị bằng x • Phần 3: Gồm các phần tử 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. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 131
  132. Quick Sort - Ý Tƣởng . Sau khi thực hiện phân hoạch, dãy ban đầu được phân thành 3 đoạn: • 1. ak ≤ x , với k = 1 j • 2. ak = x , với k = j+1 i-1 • 3. ak x , với k = i N CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 132
  133. Quick Sort – Ý Tƣởng  Đoạn thứ 2 đã cĩ thứ tự.  Nếu các đoạn 1 và 3 chỉ cĩ 1 phần tử : đã cĩ thứ tự khi đĩ dãy con ban đầu đã được sắp. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 133
  134. Quick Sort – Ý Tƣởng  Đoạn thứ 2 đã cĩ thứ tự.  Nếu các đoạn 1 và 3 cĩ nhiều hơn 1 phần tử thì dãy ban đầu chỉ cĩ thứ tự khi các đoạn 1, 3 được sắp.  Để sắp xếp các đoạn 1 và 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu vừa trình bày CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 134
  135. Giải Thuật Quick Sort  Bước 1: Nếu left ≥ right //dãy cĩ ít hơn 2 phần tử Kết thúc; //dãy đã được sắp xếp  Bước 2: Phân hoạch dãy aleft aright thành các đoạn: aleft aj, aj+1 ai-1, ai aright Đoạn 1 x Đoạn 2: aj+1 ai-1 = x Đoạn 3: ai aright x  Bước 3: Sắp xếp đoạn 1: aleft aj  Bước 4: Sắp xếp đoạn 3: ai aright CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 135
  136. Giải Thuật Quick Sort  Bước 1 : 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;  Bước 2 : Phát hiện và hiệu chỉnh cặp phần tử a[i], a[j] nằm sai chỗ : . Bước 2a : Trong khi (a[i] x) j ; . Bước 2c : Nếu i< j Đoicho(a[i],a[j]);  Bước 3 : Nếu i < j: Lặp lại Bước 2. Ngược lại: Dừng CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 136
  137. Quick Sort – Ví Dụ  Cho dãy số a: 12 2 8 5 1 6 4 15 Phân hoạch đoạn l =0, r = 7: x = a[3] = 5 12 2 8 5 1 6 4 15 l=0 r=7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 137
  138. Quick Sort – Ví Dụ l=0 r=7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 138
  139. Quick Sort – Ví Dụ  Phân hoạch đoạn l =0, r = 2: x = a[2] = 2 l=0 r=2 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 139
  140. Quick Sort – Ví Dụ  Phân hoạch đoạn l = 4, r = 7: x = a[5] = 6 l=4 r=7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 140
  141.  Phân hoạch đoạn l = 6, r = 7: x = a[6] = 6 l=6 r=7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 141
  142. Quick Sort void QuickSort(int a[], int left, int right) { int i, j, x; x = a[(left+right)/2]; i = left; j = right; while(i x) j ; if(i <= j) { Doicho(a[i],a[j]); i++ ; j ; } } if(left<j) QuickSort(a, left, j); if(i<right) QuickSort(a, i, right); } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 142
  143. Quick Sort – Ví Dụ Phân hoạch dãy i j 0 1 2 3 4 5 6 7 12 2 8 5 1 6 4 15 left X right STOP STOP Not less than XNot greater than X CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 143
  144. Quick Sort – Ví Dụ Phân hoạch dãy X 5 i j 1 2 3 4 5 6 7 8 4 2 8 5 1 6 12 15 left right STOP STOP Khơng nhỏ hơn XKhơng lớn hơn X CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 144
  145. Quick Sort – Ví Dụ j i 1 2 3 4 5 6 7 8 4 2 1 5 8 6 12 15 left right CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 145
  146. Quick Sort – Ví Dụ Phân hoạch dãy X 6 i j 1 2 3 4 5 6 7 8 1 2 4 5 8 6 12 15 left right Sắp xếp đoạn 3 STOP STOP Khơng nhỏ hơn XKhơng lớn hơn X CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 146
  147. Quick Sort – Ví Dụ j i 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 left right Sắp xếp đoạn 3 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 147
  148. Độ Phức Tạp Của Quick Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 148
  149. Các Thuật Tốn Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 4. Shaker Sort 5. Chèn trực tiếp – Insertion Sort 6. Chèn nhị phân – Binary Insertion Sort 7. Shell Sort 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 149
  150. Merge Sort – Ý Tƣởng  Giải thuật Merge sort sắp xếp dãy a1, a2, , an dựa trên nhận xét sau:  Mỗi dãy a1, a2, , an bất kỳ 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. Hướng tiếp cận: tìm cách làm giảm số dãy con khơng giảm của dãy ban đầu. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 150
  151. Sắp Xếp Trộn - Merge Sort  Mảng A chia làm 02 phần bằng nhau.  Sắp xếp 02 phần  Trộn 02 nửa lại CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 151
  152. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 152
  153. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 153
  154. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 154
  155. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 155
  156. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 156
  157. Merge Sort – Ví Dụ Original Sequence Sorted Sequence 18 26 32 6 43 15 9 1 1 6 9 15 18 26 32 43 18 26 32 6 43 15 9 1 6 18 26 32 1 9 15 4343 1818 2626 32 6 4343 1515 9 1 18 26 6 32 15 43 1 9 1818 26 32 6 43 15 9 1 18 26 32 66 43 15 9 1 18 26 32 6 43 15 9 1 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 158
  158. Merge Sort void MergeSort (Day &d, p, r) { if p < r { q = (p+r)/2 MergeSort (A, p, q) MergeSort (A, q+1, r) Merge (A, p, q, r); } } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 159
  159. Merge Sort  Các dãy con tăng dần sẽ được tách ra 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 hai dãy phụ thành một dãy con của dãy ban đầu dãy mới cĩ số lượng dãy con giảm đi so với dãy ban đầu. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 160
  160. Merge Sort  Bước 1 : k = 1; // dãy con cĩ 1 phần tử là dãy khơng giảm  Bước 2 : Lặp trong khi (k < N) // dãy cịn hơn 1 dãy con  Bước 21: Phân phối đều luân phiên dãy a1, a2, , an thành 2 dãy b, c theo từng nhĩm k phần tử liên tiếp nhau. //b = a1, , ak, a2k+1, , a3k, //c = ak+1, , a2k, a3k+1, , a4k,  Bước 22: 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.  Bước 23: k = k*2; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 161
  161. Merge Sort – Ví Dụ k = 1; Phân phối đều luân phiên 1 2 3 4 5 6 7 8 12 2 8 5 1 6 4 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 162
  162. Merge Sort – Ví Dụ k = 1; Phân phối đều luân phiên 1 2 3 4 5 6 7 8 12 2 8 5 1 6 4 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 163
  163. Merge Sort – Ví Dụ k = 1; Trộn từng cặp đường chạy 0 1 2 3 4 5 6 7 12 8 1 4 2 5 6 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 164
  164. Merge Sort – Ví Dụ k = 1; Trộn từng cặp đường chạy 0 1 2 3 4 5 6 7 12 8 1 4 2 5 6 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 165
  165. Merge Sort – Ví Dụ k = 2; Phân phối đều luân phiên 2 12 5 8 1 6 4 15 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 166
  166. Merge Sort – Ví Dụ k = 2; Trộn từng cặp đường chạy 0 1 2 3 4 5 6 7 2 12 1 6 5 8 4 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 167
  167. Merge Sort – Ví Dụ k = 2; Trộn từng cặp đường chạy 0 1 2 3 4 5 6 7 2 12 1 6 5 8 4 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 168
  168. Merge Sort – Ví Dụ k = 4; Phân phối đều luân phiên 2 5 8 12 1 4 6 15 0 1 2 3 4 5 6 7 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 169
  169. Merge Sort – Ví Dụ k = 4; Trộn từng cặp đường chạy 0 1 2 3 4 5 6 7 2 5 8 12 1 4 6 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 170
  170. Merge Sort – Ví Dụ k = 4; Trộn từng cặp đường chạy 0 1 2 3 4 5 6 7 2 5 8 12 1 4 6 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 171
  171. Merge Sort – Ví Dụ k = 8; 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 STOP Chỉ một mảng con CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 172
  172. Merge Sort – Ví Dụ 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 173
  173. Merge Sort – Cài Đặt  Dữ liệu hỗ trợ: 2 mảng b, c: int b[MAX], c[MAX], nb, nc;  Các hàm cần cài đặt:  void MergeSort(int a[], int N); : Sắp xếp mảng (a, N) tăng dần  void Distribute(int a[], int N, int &nb, int &nc, int k); Phân phối đều luân phiên các dãy con độ dài k từ mảng a vào hai mảng con b và c  void Merge(int a[], int nb, int nc, int k); : Trộn mảng b và mảng c vào mảng a  void MergeSubarr(int a[], int nb, int nc, int &pa, int &pb, int &pc, int k); : Trộn một cặp dãy con từ b và c vào a CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 174
  174. Merge Sort – Cài Đặt int b[MAX], c[MAX], nb, nc; void MergeSort(int a[], int N) { int k; for (k = 1; k < N; k *= 2) { Distribute(a, N, nb, nc, k); Merge(a, nb, nc, k); } } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 175
  175. Merge Sort – Cài Đặt void Distribute(int a[], int N, int &nb, int &nc, int k) { int i, pa, pb, pc; pa = pb = pc = 0; while (pa < N) { for (i=0; (pa<N) && (i<k); i++, pa++, pb++) b[pb] = a[pa]; for (i=0; (pa<N) && (i<k); i++, pa++, pc++) c[pc] = a[pa]; } nb = pb; nc = pc; } CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 176
  176. Các Thuật Tốn Sắp Xếp 1. Đổi chỗ trực tiếp – Interchange Sort 2. Nổi bọt – Bubble Sort 3. Shaker Sort 4. Chèn trực tiếp – Insertion Sort 5. Chèn nhị phân – Binary Insertion Sort 6. Shell Sort 7. Chọn trực tiếp – Selection Sort 8. Quick Sort 9. Merge Sort 10. Heap Sort 11. Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 177
  177. Sắp Xếp Theo Phƣơng Pháp Cơ Số Radix Sort  Radix Sort là một thuật tốn tiếp cận theo một hướng hồn tồn khác.  Nếu như trong các thuật tốn khác, cơ sở để sắp xếp luơn là việc so sánh giá trị của 2 phần tử thì Radix Sort lại dựa trên nguyên tắc phân loại thư của bưu điện. Vì lý do đĩ Radix Sort cịn cĩ tên là Postman’s sort.  Radix Sort khơng hề quan tâm đến việc so sánh giá trị của phần tử mà bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự cho các phần tử. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 178
  178. Sắp Xếp Theo Phƣơng Pháp Cơ Số Radix Sort  Mơ phỏng lại qui trình trên, để sắp xếp dãy a1, a2, , an, giải thuật Radix Sort thực hiện như sau:  Trước tiên, ta cĩ thể giả sử mỗi phần tử ai trong dãy a1, a2, , an là một số nguyên cĩ tối đa m chữ số.  Ta phân loại các phần tử lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm, tương tự việc phân loại thư theo tỉnh thành, quận huyện, phường xã, . CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 179
  179. Sắp Xếp Theo Phƣơng Pháp Cơ Số Radix Sort  Bước 1 :// k cho biết chữ số dùng để phân loại hiện hành  k = 0; // k = 0: hàng đơn vị; k = 1: hàng chục;  Bước 2 : //Tạo các lơ chứa các loại phần tử khác nhau  Khởi tạo 10 lơ B0, B1, , B9 rỗng; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 180
  180. Sắp Xếp Theo Phƣơng Pháp Cơ Số Radix Sort  Bước 3 :  For i = 1 n do . Đặt ai vào lơ Bt với t: chữ số thứ k của ai;  Bước 4 :  Nối B0, B1, , B9 lại (theo đúng trình tự) thành a.  Bước 5 :  k = k+1;Nếu k < m thì trở lại bước 2. Ngược lại: Dừng CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 181
  181. Sắp Xếp Theo Phƣơng Pháp Cơ Số Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 182
  182. Sắp Xếp Theo Phƣơng Pháp Cơ Số Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 183
  183. Sắp Xếp Theo Phƣơng Pháp Cơ Số Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 184
  184. Sắp Xếp Theo Phƣơng Pháp Cơ Số Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 185
  185. Sắp Xếp Theo Phƣơng Pháp Cơ Số Radix Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 186
  186. Bài Tập  Nhập một dãy số nguyên n phần tử.  Sắp xếp lại dãy sao cho: . số nguyên dương đầu ở đầu dãy và theo thứ tự giảm. . số nguyên âm tăng ở cuối dãy và theo thứ tự tăng. . số 0 ở giữa.  Lưu ý: Khơng dùng đổi chỗ trực tiếp. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 187