›
›

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

ppt 187 trang hapham 2280
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 1 - 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:

  • pptbai_giang_cau_truc_du_lieu_va_giai_thuat_1_chuong_2_tim_kiem.ppt

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật 1 - 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 Toá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ó khoá 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 Toá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 Toá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 Toá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 Toá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 Toán Tìm Tuyến Tính ➢ Nhận xét: Số phép so sánh của thuật toá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 toá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 Toá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 Toá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 Toá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 Toá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 Toá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 Toá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 Toá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 Toá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 hoá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 Toá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 Toá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 Toá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 Toá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 Toá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 Toá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 Toán j 1 2 4 5 126 8 6 15 0 1 2 30 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 34
  35. Minh Họa Thuật Toán j 1 2 4 5 6 128 8 15 0 1 2 3 04 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 35
  36. Minh Họa Thuật Toán j 1 2 4 5 6 8 12 15 0 1 2 3 4 50 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 36
  37. Minh Họa Thuật Toá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 37
  38. Độ Phức Tạp Của Thuật Toá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 38
  39. Các Thuật Toá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 39
  40. 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 40
  41. Các Bước Của Thuật Toá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 41
  42. 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 42
  43. 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 43
  44. 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 44
  45. 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 45
  46. Cài Đặt Thuật Toá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 46
  47. Minh Họa Thuật Toá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 47
  48. Minh Họa Thuật Toá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 48
  49. Minh Họa Thuật Toá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 49
  50. Minh Họa Thuật Toá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 50
  51. Minh Họa Thuật Toá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 51
  52. Minh Họa Thuật Toá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 52
  53. Minh Họa Thuật Toá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 53
  54. Độ Phức Tạo Của Thuật Toán ➢ Ðánh giá giải thuật n−1 nn(− 1) soá laàn so saù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 54
  55. Các Thuật Toá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 55
  56. 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 56
  57. 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]<a[j-1] Doicho(a[j],a[j-1]); j = j-1; ➢ Bước 3 : 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. 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 ➢ Cho dãy số a: 2 12 8 5 1 6 4 15 i=0 j=6 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 58
  59. 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 59
  60. 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 60
  61. 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=361 j=6
  62. 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 62
  63. Cài Đặt Thuật Toá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 63
  64. Minh Họa Thuật Toá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 64
  65. Minh Họa Thuật Toá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 65
  66. Minh Họa Thuật Toá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 66
  67. Minh Họa Thuật Toá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 67
  68. Minh Họa Thuật Toá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 68
  69. Minh Họa Thuật Toá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 69
  70. Minh Họa Thuật Toá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 70
  71. Độ Phức Tạp Của Thuật Toá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 71
  72. Các Thuật Toá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 72
  73. 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 73
  74. Các Bước Của Thuật Toá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 hoá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]); k=j;} j++; r=k; //loại 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 74
  75. Cài Đặt Thuật Toá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 75
  76. Các Thuật Toá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 76
  77. 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 77
  78. 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 78
  79. 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 79
  80. 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 80
  81. 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 81
  82. Cài Đặt Thuật Toá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 82
  83. Minh Họa Thuật Toá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 83
  84. Minh Họa Thuật Toá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 84
  85. Minh Họa Thuật Toá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 85
  86. Minh Họa Thuật Toá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 86
  87. Minh Họa Thuật Toá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 87
  88. Minh Họa Thuật Toá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 88
  89. Minh Họa Thuật Toá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 89
  90. Minh Họa Thuật Toá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 90
  91. Minh Họa Thuật Toá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 91
  92. Độ 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 92
  93. Các Thuật Toá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 93
  94. 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 94
  95. Các Thuật Toá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 95
  96. 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 96
  97. 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 97
  98. 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 98
  99. 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 99
  100. 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 100
  101. 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 101
  102. 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 102
  103. 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 103
  104. 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 104
  105. 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 105
  106. 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 106
  107. 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 107
  108. 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 108
  109. 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 109
  110. 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 110
  111. 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 111
  112. 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 112
  113. 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 113
  114. 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 114
  115. 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 115
  116. Các Thuật Toá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 116
  117. Thuật Toá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 toá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 117
  118. Thuật Toán Sắp Xếp Heap Sort ➢ Cho dãy số : 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 12 a[0] 2 a[1] 8 a[2] 5 a[3] 1 a[4] 6 a[5] 4 a[6] 15 a[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 118
  119. Thuật toá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ánh liên quan đến phần tử mới loại bỏ, còn các nhánh khác thì bảo toà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 toá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 119
  120. Các Bước Thuật Toá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-1; Swap (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 120
  121. Minh Họa Thuật Toán ➢ Heap: Là một dãy các phần tử al, al+1 , , ar thoả các quan hệ với mọi i [l, r]:  ai a2i+1  ai a2i+2 // (ai , a2i+1), (ai , a2i+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 121
  122. Minh Họa Thuật Toá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 122
  123. Minh Họa Thuật Toá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 123
  124. Minh Họa Thuật Toá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 124 r=6
  125. Minh Họa Thuật Toá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 125
  126. Minh Họa Thuật Toá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 126
  127. Minh Họa Thuật Toá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 127
  128. Minh Họa Thuật Toá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 128
  129. Cài Đặt Thuật Toá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 129
  130. Cài Đặt Thuật Toá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 130
  131. Cài Đặt Thuật Toá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 131
  132. Cài Đặt Thuật Toá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 132
  133. Các Thuật Toá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 133
  134. 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 134
  135. 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 135
  136. 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 136
  137. 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 137
  138. 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 138
  139. 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 Swap(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 139
  140. 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 140
  141. Quick Sort – Ví Dụ 4 2 8 5 1 6 12 15 i = 0 j = 6 l=0 r=7 4 2 8 5 1 6 12 15 i = 1 i = 2 l=0 j = 3 j = 4 j = 5 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 – Ví Dụ ➢ Phân hoạch đoạn l = 0, r = 2: 4 2 1 5 8 6 12 15 l = 0 r =3 i = 0 j = 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 142
  143. Quick Sort – Ví Dụ ➢ Phân hoạch đoạn l =4, r = 7: 1 2 4 5 8 6 12 15 l = 4 r =7 i = 4 j = 6 j = 6 j = 7 1 2 4 5 i = 46 8 12 15 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 143
  144. Quick Sort – Ví Dụ ➢ Phân hoạch đoạn l =6, r = 7: 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 144
  145. Quick Sort void QuickSort(int a[], int left, int right) { int i, j, x; x = a[(left+right)/2]; i = left; j = right; do { while(a[i] x) j ; if(i <= j) { Swap(a[i],a[j]); i++ ; j ; } } while(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 145
  146. Quick Sort – Ví Dụ ➢ Phân hoạch đọan [0,7] i j 0 1 2 3 4 5 6 7 12 2 8 55 1 6 4 15 left X 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 146
  147. Quick Sort – Ví Dụ ➢ Phân hoạch đọan [0,7] X 5 i j 0 1 2 3 4 5 6 7 4 2 8 5 1 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 147
  148. Quick Sort – Ví Dụ ➢ Phân hoạch đọan [0,2] j i 0 1 2 3 4 5 6 7 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 148
  149. ➢ Phân hoạch đọan [0,2] i j 0 1 2 3 4 5 6 7 4 2 1 5 8 6 12 15 X 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 149
  150. Quick Sort – Ví Dụ ➢ Phân hoạch đọan [4,7] i j 0 1 2 3 4 5 6 7 1 2 4 5 8 6 12 15 X 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 150
  151. Quick Sort – Ví Dụ ➢ Phân hoạch đọan [5,7] j i 0 1 2 3 4 5 6 7 1 2 4 5 6 8 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 151
  152. Quick Sort – Ví Dụ ➢ Phân hoạch đọan [5,7] i j 0 1 2 3 4 5 6 7 1 2 4 5 6 8 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 152
  153. Quick Sort – Ví Dụ 0 1 2 3 4 5 6 7 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 153
  154. Độ 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 154
  155. Các Thuật Toá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 155
  156. 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 156
  157. Merge Sort – thuật toán Bước 1 : // Chuẩn bị k = 1; // k là chiều dài của dãy con trong bước hiện hành Bước 2 : Tách dãy a0, a1, ., an-1 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 = a0, ., ak, a2k, ., a3k, . c = ak+1, ., a2k+1, a3k+1, . Bước 3 : 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 4 : k = k*2; Nếu k < n 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 157
  158. Merge Sort – Ví Dụ ➢ k=1 ➢Phân phối luân phiên 0 1 2 3 4 5 6 7 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 158
  159. Merge Sort – Ví Dụ ➢k = 1 ➢Phân phối luân phiên 0 1 2 3 4 5 6 7 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 159
  160. Merge Sort – Ví Dụ ➢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 160
  161. 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 161
  162. Merge Sort – Ví Dụ ➢k = 2 ➢Phân phối 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 162
  163. 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 163
  164. 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 164
  165. Merge Sort – Ví Dụ ➢k = 4 ➢Phân phối 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 165
  166. 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 166
  167. 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 167
  168. Merge Sort – Ví Dụ ➢k = 8 0 1 2 3 4 5 6 7 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 168
  169. 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 169
  170. 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 170
  171. 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 171
  172. 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 172
  173. Merge Sort – Cài Đặt void Merge(int a[],int nb, int nc,int k) { int p, pb, pc, ib, ic, kb, kc; p=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[p++]=b[pb+ib]; ib++; if(ib==kb) { for(;ic<kc;ic++ a[p++]=c[pc+ic]; pb+=kb; pc+=kc; ib = ic=0; nb-=kb; nc-=kc; } } 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
  174. Merge Sort – Cài Đặt else { a[p++]=c[pc+ic]; ic++; if(ic==kc) { for(;ib<kb;ib++) a[p++]=b[pb+ib]; pb+=kb; pc+=kc; ib = ic=0; nb-=kb; nc-=kc; } } } } 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
  175. Merge Sort – Cài Đặt int min(int a,int b) { if(a>b) return b; else return 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 175
  176. Độ phức tạp của Merge Sort ➢ Số lần lặp của Bước 2, 3 là log2n do sau mỗi lần lặp giá trị k tăng gấp đôi. Chi phí thực hiện ở bước 2 và 3 tỉ lệ thuật với n. Do dó chi phí của dãy thuật MergeSort là 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 176
  177. Các Thuật Toá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
  178. Sắp Xếp Theo Phương Pháp Cơ Số Radix Sort ➢ Radix Sort là một thuật toán tiếp cận theo một hướng hoàn toàn khác. ➢ Nếu như trong các thuật toá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
  179. 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
  180. 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
  181. 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
  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 182
  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 183
  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 184
  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 185
  186. 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
  187. 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