›
›

Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán tìm kiếm

ppt 167 trang phuongnguyen 110
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: Các thuật toán tìm kiếm", để 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_cac_thuat_toan_tim.ppt

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán tìm kiếm

  1. NỘI DUNG CÁC THUẬT TỐN TÌM KIẾM Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  2. Bài tốn tìm kiếm • Input: Cho mảng a cĩ n phần tử • X: Giá trị cần tìm • Output: Tìm phần tử cĩ giá trị = x cĩ hay khơng trong mảng => Hai thuật tốn tìm kiếm: ▪ Tìm kiếm tuần tự (áp dụng trên mọi mảng) ▪ Tìm kiếm nhị phân (áp dụng trên mảng đã cĩ thứ tự) Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  3. Thuật tốn tìm kiếm tuyến tính • Ý tưởng :Lần lượt so sánh X với từng phần tử trong A cho đến khi tìm thấy hay hết phần tử trong mảng. • Các bước tiến hành Bước 1: Khởi gán i=1 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à thuậtvà giảiliệu dữ trúc Cấu
  4. Thuật tốn tìm kiếm tuyến tính 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à thuậtvà giảiliệu dữ trúc Cấu
  5. 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à thuậtvà giảiliệu dữ trúc Cấu
  6. Ðá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à thuậtvà giảiliệu dữ trúc Cấu
  7. 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à thuậtvà giảiliệu dữ trúc Cấu }
  8. Thuật tốn tìm kiếm nhị phân • Ý tưởng: – So sánh khĩa cần tìm với phần tử giữa dãy hiện hành. – Nếu nĩ nhỏ hơn thì tìm bên trái dãy hiện hành. – Ngược lại tìm bên phải dãy hiện hành. – Lặp lại động tác này. • Dãy hiện hành là dãy ta tang tìm, chỉ số đầu tiên của phần tử đầu tiên trong dãy là left, và chỉ số của phần tử cuối cùng trong dãy hiện hành là right Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  9. Các bước thuật tốn tìm kiếm nhị phân • Bước 1: left=1; right=N;//tìm kiếm trên tất cả các phần tử • Bước 2: – mid=(left+right)/2;//chỉ số của phầ tử đứng giữa trong dãy hiện hành – So sánh a[mid] với x. Cĩ 3 khả năng cĩ: • a[mid]= x: tìm thấy. Dừng • a[mid]>x + Right= mid-1;//Tìm tiếp x trong dãy con a[Left] a[mid-1] • a[mid]<x + Left= mid+1;//Tìm tiếp x trong dãy con a[mid+1] a[right] • 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à thuậtvà giảiliệu dữ trúc Cấu
  10. Thuật tốn tìm nhị phân 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à thuậtvà giảiliệu dữ trúc Cấu
  11. Độ phức tạp thuật tốn tìm nhị phân 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à thuậtvà giảiliệu dữ trúc Cấu
  12. Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  13. NỘI DUNG CÁC THUẬT TỐN SẮP XẾP Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  14. Sắp xếp • Cho tập N phần tử cĩ m thuộc tính, được biểu diễn dưới dạng bản ghi. • Dựa vào 1 (hoặc vài) thuộc tính để sắp xếp các phần tử theo trật tự mới Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  15. Sắp xếp • Gồm 2 bài tốn con: – Dựa theo khố sắp xếp định vị lại thứ tự bản ghi – Chuyển các bản ghi về vị trí mới. • Hai thao tác cơ bản – So sánh – Gán Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  16. 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 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu 11. Radix Sort
  17. 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à thuậtvà giảiliệu dữ trúc Cấu
  18. Đổi chỗ trực tiếp – Interchange Sort • Khái niệm nghịch thế: – Xét một mảng các số a0, a1, . an. – Nếu cĩ i aj, thì ta gọi đĩ là một nghịch thế. • Mảng chưa sắp xếp sẽ cĩ nghịch thế • Mảng đã cĩ thứ tự sẽ khơng chứa nghịch thế Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  19. Đổi chỗ trực tiếp – Interchange Sort • Tìm tất cả nghịch thế, triệt tiêu chúng bằng cách hốn vị 2 phần tử tương ứng trong nghịch thế Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  20. Đổi chỗ trực tiếp – Interchange Sort • Bước 1 : i = 1;// bắt đầu từ đầu dãy • Bước 2 : j = i+1;//tìm các phần tử a[j] 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] Doicho(a[i],a[j]); j = j+1; • Bước 4 : 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à thuậtvà giảiliệu dữ trúc Cấu
  21. Đổi chỗ trực tiếp – Interchange Sort • Cho dãy số a: 12 2 8 5 1 6 4 15 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  22. Đổi chỗ trực tiếp – Interchange Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  23. Đổi chỗ trực tiếp – Interchange Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  24. Đổi chỗ trực tiếp – Interchange Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  25. Đổi chỗ trực tiếp – Interchange Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  26. Đổi chỗ trực tiếp – Interchange Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  27. Đổi chỗ trực tiếp – Interchange Sort • 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]) // nếu cĩ sự sai vị trí thì đổi chỗ Doicho(a[i],a[j]); } Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  28. Interchange Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  29. Interchange Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  30. Interchange Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  31. Interchange Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  32. Interchange 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à thuậtvà giảiliệu dữ trúc Cấu
  33. Cấu trúc dữ liệu và giải thuật
  34. 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 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu 11. Radix Sort
  35. Nổi bọt – Bubble Sort • Ý tưởng chính của giải thuật là 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 . Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  36. Nổi bọt – Bubble Sort • Bước 1 : i = 1; // lần xử lý đầu tiên • Bước 2 : j = N; //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à thuậtvà giảiliệu dữ trúc Cấu
  37. Nổi bọt – Bubble Sort • Cho dãy số a: 2 12 8 5 1 6 4 15 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  38. Nổi bọt – Bubble Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  39. Nổi bọt – Bubble Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  40. Nổi bọt – Bubble Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  41. Nổi bọt – Bubble Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  42. Nổi bọt – Bubble Sort • void BubleSort(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ỗ Doicho(a[j], a[j-1]); } Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  43. Bubble Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  44. Bubble Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  45. Bubble Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  46. Bubble Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  47. Bubble Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  48. Bubble Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  49. Bubble Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  50. Cấu trúc dữ liệu và giải thuật Độ phức tạp của thuật tốn sắp xếp Bubble sort Bubble xếp sắp tốn thuật của tạp Độ phức
  51. 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 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu 11. Radix Sort
  52. Shaker Sort • Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phiá 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à thuậtvà giảiliệu dữ trúc Cấu
  53. 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]) {Doicho(a[j], a[j-1]);k = j; } right = k; } } Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  54. 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 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu 11. Radix Sort
  55. Chèn trực tiếp – Insertion Sort • Giả sử cĩ một dãy a1 , a2 , ,an trong đĩ i phần tử đầu tiên a1 , a2 , ,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 a1 , a2 , ,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à thuậtvà giảiliệu dữ trúc Cấu
  56. Chèn trực tiếp – Insertion Sort • Bước 1: i = 2; // 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à thuậtvà giảiliệu dữ trúc Cấu
  57. Chèn trực tiếp – Insertion Sort • Cho dãy số : 12 2 8 5 1 6 4 15 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  58. Chèn trực tiếp – Insertion Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  59. Chèn trực tiếp – Insertion Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  60. Chèn trực tiếp – Insertion Sort 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à thuậtvà giảiliệu dữ trúc Cấu }
  61. Insertion Sort – Ví dụ 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  62. Insertion Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  63. Insertion Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  64. Insertion Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  65. Insertion Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  66. Insertion Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  67. Insertion Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  68. Insertion Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  69. Insertion Sort – Ví dụ 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à thuậtvà giảiliệu dữ trúc Cấu
  70. Độ phức tạp của Insertion Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  71. 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 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu 11. Radix Sort
  72. 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 } } thuậtvà giảiliệu dữ trúc Cấu
  73. 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 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu 11. Radix Sort
  74. 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à thuậtvà giảiliệu dữ trúc Cấu
  75. 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à thuậtvà giảiliệu dữ trúc Cấu
  76. 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à thuậtvà giảiliệu dữ trúc Cấu
  77. 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à thuậtvà giảiliệu dữ trúc Cấu
  78. 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à thuậtvà giảiliệu dữ trúc Cấu
  79. 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à thuậtvà giảiliệu dữ trúc Cấu
  80. 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à thuậtvà giảiliệu dữ trúc Cấu
  81. Shell Sort • h = 5 : xem dãy ban đầu như các dãy con Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  82. 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à thuậtvà giảiliệu dữ trúc Cấu
  83. 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à thuậtvà giảiliệu dữ trúc Cấu
  84. Cấu trúc dữ liệu và giải thuật Shell Sort Shell
  85. 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à thuậtvà giảiliệu dữ trúc Cấu
  86. 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à thuậtvà giảiliệu dữ trúc Cấu
  87. 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à thuậtvà giảiliệu dữ trúc Cấu
  88. 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à thuậtvà giảiliệu dữ trúc Cấu
  89. 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à thuậtvà giảiliệu dữ trúc Cấu
  90. Shell sort – Ví dụ h = (5, 3, 1); k = 3 len = 3 1 2 3 4 5 6 7 8 4 1 12 5 2 15 6 8 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  91. 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à thuậtvà giảiliệu dữ trúc Cấu
  92. 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à thuậtvà giảiliệu dữ trúc Cấu
  93. Shell 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à thuậtvà giảiliệu dữ trúc Cấu
  94. 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 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu 11. Radix Sort
  95. Chọn trực tiếp – Selection Sort • 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 là đầ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 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à thuậtvà giảiliệu dữ trúc Cấu
  96. Chọn trực tiếp – Selection Sort • Bước 1: i = 1; • 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à thuậtvà giảiliệu dữ trúc Cấu
  97. 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à thuậtvà giảiliệu dữ trúc Cấu
  98. Chọn trực tiếp – Selection Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  99. Chọn trực tiếp – Selection Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  100. Chọn trực tiếp – Selection Sort Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  101. Chọn trực tiếp – Selection Sort 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; // ghi nhận vị trí phần tử hiện nhỏ nhất Doicho(a[min],a[i]); } Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu }
  102. Selection sort – Ví dụ Find MinPos(0, 7) Doicho(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à thuậtvà giảiliệu dữ trúc Cấu
  103. Selection sort – Ví dụ Find MinPos(1, 7) Doicho(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à thuậtvà giảiliệu dữ trúc Cấu
  104. Selection sort – Ví dụ Find MinPos(2, 7) Doicho(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à thuậtvà giảiliệu dữ trúc Cấu
  105. Selection sort – Ví dụ Find MinPos(3, 7) Doicho(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à thuậtvà giảiliệu dữ trúc Cấu
  106. Selection sort – Ví dụ Find MinPos(4, 7) Doicho(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à thuậtvà giảiliệu dữ trúc Cấu
  107. Selection sort – Ví dụ Find MinPos(5,7) Doicho(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à thuậtvà giảiliệu dữ trúc Cấu
  108. Selection sort – Ví dụ Find MinPos(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à thuậtvà giảiliệu dữ trúc Cấu
  109. Chọn trực tiếp – Selection Sort • Ðá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à thuậtvà giảiliệu dữ trúc Cấu
  110. 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 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu 11. Radix Sort
  111. 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ị khơng lớn 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ị khơng bé 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à thuậtvà giảiliệu dữ trúc Cấu
  112. 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à thuậtvà giảiliệu dữ trúc Cấu
  113. 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à thuậtvà giảiliệu dữ trúc Cấu
  114. 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à thuậtvà giảiliệu dữ trúc Cấu
  115. Quick sort – Giải thuật • 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à thuậtvà giảiliệu dữ trúc Cấu
  116. Quick sort – Giải thuật • 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à thuậtvà giảiliệu dữ trúc Cấu
  117. Quick sort – Ví dụ • Cho dãy số a: 12 2 8 5 1 6 4 15 Phân hoạch đoạn l =1, r = 8: x = A[4] = 5 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  118. Quick sort – Ví dụ Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  119. Quick sort – Ví dụ • Phân hoạch đoạn l =1, r = 3: x = A[2] = 2 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  120. Quick sort – Ví dụ • Phân hoạch đoạn l = 5, r = 8: x = A[6] = 6 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  121. • Phân hoạch đoạn l = 7, r = 8: x = A[7] = 6 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  122. 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à thuậtvà giảiliệu dữ trúc Cấu }
  123. Quick sort – Ví dụ Phân hoạch dãy X 5 i j 0 1 2 3 4 5 6 7 12 2 8 5 1 6 4 15 left right STOP STOP Not less than XNot greater than X Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  124. 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 Not less than XNot greater than X Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  125. 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à thuậtvà giảiliệu dữ trúc Cấu
  126. 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 Not less than XNot greater than X Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  127. 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à thuậtvà giảiliệu dữ trúc Cấu
  128. Cấu trúc dữ liệu và giải thuật Độ phức tạp của Quick Độ phứctạpcủa sort
  129. 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 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu 11. Radix Sort
  130. 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à thuậtvà giảiliệu dữ trúc Cấu
  131. 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à thuậtvà giảiliệu dữ trúc Cấu
  132. Cấu trúc dữ liệu và giải thuật
  133. Cấu trúc dữ liệu và giải thuật
  134. Cấu trúc dữ liệu và giải thuật
  135. Cấu trúc dữ liệu và giải thuật
  136. Cấu trúc dữ liệu và giải thuật
  137. 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à thuậtvà giảiliệu dữ trúc Cấu
  138. 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à thuậtvà giảiliệu dữ trúc Cấu
  139. 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à thuậtvà giảiliệu dữ trúc Cấu
  140. 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à thuậtvà giảiliệu dữ trúc Cấu
  141. 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à thuậtvà giảiliệu dữ trúc Cấu
  142. 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à thuậtvà giảiliệu dữ trúc Cấu
  143. 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à thuậtvà giảiliệu dữ trúc Cấu
  144. 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à thuậtvà giảiliệu dữ trúc Cấu
  145. 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à thuậtvà giảiliệu dữ trúc Cấu
  146. 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à thuậtvà giảiliệu dữ trúc Cấu
  147. 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à thuậtvà giảiliệu dữ trúc Cấu
  148. 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à thuậtvà giảiliệu dữ trúc Cấu
  149. 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à thuậtvà giảiliệu dữ trúc Cấu
  150. 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à thuậtvà giảiliệu dữ trúc Cấu
  151. Merge sort – Ví dụ k = 8; 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 STOP Only one subarray Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  152. 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à thuậtvà giảiliệu dữ trúc Cấu
  153. 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 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 1 cặp dãy con từ b và c vào a Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu
  154. 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à thuậtvà giảiliệu dữ trúc Cấu
  155. 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à thuậtvà giảiliệu dữ trúc Cấu
  156. 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 Cấu trúc dữ liệu và thuậtvà giảiliệu dữ trúc Cấu 11. Radix Sort
  157. 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à thuậtvà giảiliệu dữ trúc Cấu
  158. 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à thuậtvà giảiliệu dữ trúc Cấu
  159. 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à thuậtvà giảiliệu dữ trúc Cấu
  160. 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à thuậtvà giảiliệu dữ trúc Cấu
  161. Cấu trúc dữ liệu và giải thuật Sắp xếp theo phương pháp cơ số Radix Sort
  162. Cấu trúc dữ liệu và giải thuật Sắp xếp theo phương pháp cơ số Radix Sort
  163. Cấu trúc dữ liệu và giải thuật Sắp xếp theo phương pháp cơ số Radix Sort
  164. Cấu trúc dữ liệu và giải thuật Sắp xếp theo phương pháp cơ số Radix Sort
  165. Cấu trúc dữ liệu và giải thuật Sắp xếp theo phương pháp cơ số Radix Sort
  166. 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à thuậtvà giảiliệu dữ trúc Cấu