›

Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 13: Các thuật toán sắp xếp - Hoàng Thị Điệp

pdf 87 trang huongle 8090
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 - Bài 13: Các thuật toán sắp xếp - Hoàng Thị Điệp", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

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

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_bai_13_cac_thuat_to.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 13: Các thuật toán sắp xếp - Hoàng Thị Điệp

  1. Tài liệu tham khảo: Bài giảng SMA 5503 Introduction to Algorithms. 2001-5 Erik D. Demaine and Charles E. Leiserson. Bài 13: Các thuật toán sắp xếp Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014
  2. Nội dung chính 1. Bài toán sắp xếp 2. Sắp xếp xen vào 3. Sắp xếp trộn 4. Sắp xếp nhanh 5. Sắp xếp sử dụng cây thứ tự bộ phận 6. Sắp xếp đếm 7. Sắp xếp cơ số 2 diepht@vnu
  3. Bài toán sắp xếp  Lí do:  Một trong những bài toán được nghiên cứu lâu đời nhất trong CNTT  Chứa nhiều kĩ thuật về thuật toán  Input: dãy số  Output: 1 hoán vị của input thỏa mãn a1’<= a2’<= <= an’  Ý nghĩa?  Bài toán tìm kiếm  Bài toán phát hiện phần tử lặp 3 diepht@vnu
  4. Ví dụ bài toán tìm kiếm  x = 5  A = (3, 1, 4, 15, 9, 26, 53, 58, 97, 93, 23, 8, 46, 26, 4, 33, 8, 3, 2)  B = (1, 2, 3, 3, 4, 4, 8, 8, 9, 15, 23, 26, 26, 33, 46, 53, 58, 93, 97) x có trong A? x có trong B? 4 INT2203/w13 diepht@vnu
  5. Ví dụ bài toán phát hiện phần tử lặp  A = (3, 1, 4, 15, 9, 26, 53, 58, 97, 93, 23, 8, 46, 26, 4, 33, 8, 3, 2)  B = (1, 2, 3, 3, 4, 4, 8, 8, 9, 15, 23, 26, 26, 33, 46, 53, 58, 93, 97) Các giá trị xuất hiện hơn 1 lần trong A? Các giá trị xuất hiện hơn 1 lần trong B? 5 INT2203/w13 diepht@vnu
  6. Tổng quan TTSX lựa chọn O(n2) TTSX nổi bọt TTSX xen vào TTSX trộn Sắp xếp trong Sắp xếp O(n logn) TTSX nhanh Sắp xếp ngoài TTSX sử dụng heap O(n) TTSX theo cơ số 6 INT2203/w13 diepht@vnu
  7. Tổng quan Selection sort O(n2) Bubble sort Insertion sort Merge sort In-memory sort Sorting O(n logn) Quicksort External sort Heapsort O(n) Radix sort 7 INT2203/w13 diepht@vnu
  8. Với mỗi thuật toán sắp xếp  Lịch sử ra đời  Cài đặt bằng ngôn ngữ  Ý tưởng C++   Giả mã có trong STL không?  Tính ổn định (stability)  Ví dụ  Liên hệ với các thuật  Phân tích độ phức tạp toán sắp xếp khác thời gian  Vận dụng thế nào? 8 INT2203/w13 diepht@vnu
  9. Insertion Sort 9 diepht@vnu
  10. Thuật toán sắp xếp xen vào INSERTION-SORT (A, n) ⊳ A[1 . . n] for j ← 2 to n do key ← A[ j] i ← j – 1 “pseudocode” while i > 0 and A[i] > key do A[i+1] ← A[i] i ← i – 1 A[i+1] = key 10 diepht@vnu
  11. Thuật toán sắp xếp xen vào INSERTION-SORT (A, n) ⊳ A[1 . . n] for j ← 2 to n do key ← A[ j] i ← j – 1 “pseudocode” while i > 0 and A[i] > key do A[i+1] ← A[i] i ← i – 1 A[i+1] = key 1 i j n A: key sorted 11 diepht@vnu
  12. Minh họa SX xen vào 8 2 4 9 3 6 12 diepht@vnu
  13. Minh họa SX xen vào 8 2 4 9 3 6 13 diepht@vnu
  14. Minh họa SX xen vào 8 2 4 9 3 6 2 8 4 9 3 6 14 diepht@vnu
  15. Minh họa SX xen vào 8 2 4 9 3 6 2 8 4 9 3 6 15 diepht@vnu
  16. Minh họa SX xen vào 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 16 diepht@vnu
  17. Minh họa SX xen vào 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 17 diepht@vnu
  18. Minh họa SX xen vào 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 18 diepht@vnu
  19. Minh họa SX xen vào 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 19 diepht@vnu
  20. Minh họa SX xen vào 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 2 3 4 8 9 6 20 diepht@vnu
  21. Minh họa SX xen vào 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 2 3 4 8 9 6 21 diepht@vnu
  22. Minh họa SX xen vào 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 2 3 4 8 9 6 2 3 4 6 8 9 done 22 diepht@vnu
  23. Phân tích độ phức tạp  Thời gian chạy phụ thuộc bản thân input  Nếu đã sắp  đúng thứ tự?  ngược thứ tự?  Kích thước dữ liệu vào  Thời gian chạy xấu nhất? 23 diepht@vnu
  24. Merge Sort 24 diepht@vnu
  25. Thuật toán sắp xếp trộn MERGE-SORT A[1 . . n] 1. If n = 1, done. 2. Recursively sort A[ 1 . . ⎡n/2⎤ ] and A[ ⎡n/2⎤+1 . . n ] . 3. “Merge” the 2 sorted lists. Key subroutine: MERGE John von Neumann 25 diepht@vnu
  26. Trộn 2 mảng tăng 20 12 13 11 7 9 2 1 26 diepht@vnu
  27. Trộn 2 mảng tăng 20 12 13 11 7 9 2 1 1 27 diepht@vnu
  28. Trộn 2 mảng tăng 20 12 20 12 13 11 13 11 7 9 7 9 2 1 2 1 28 diepht@vnu
  29. Trộn 2 mảng tăng 20 12 20 12 13 11 13 11 7 9 7 9 2 1 2 1 2 29 diepht@vnu
  30. Trộn 2 mảng tăng 20 12 20 12 20 12 13 11 13 11 13 11 7 9 7 9 7 9 2 1 2 1 2 30 diepht@vnu
  31. Trộn 2 mảng tăng 20 12 20 12 20 12 13 11 13 11 13 11 7 9 7 9 7 9 2 1 2 1 2 7 31 diepht@vnu
  32. Trộn 2 mảng tăng 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 7 9 7 9 7 9 9 2 1 2 1 2 7 32 diepht@vnu
  33. Trộn 2 mảng tăng 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 7 9 7 9 7 9 9 2 1 2 1 2 7 9 33 diepht@vnu
  34. Trộn 2 mảng tăng 20 12 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 13 11 7 9 7 9 7 9 9 2 1 2 1 2 7 9 34 diepht@vnu
  35. Trộn 2 mảng tăng 20 12 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 13 11 7 9 7 9 7 9 9 2 1 2 1 2 7 9 11 35 diepht@vnu
  36. Trộn 2 mảng tăng 20 12 20 12 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 13 11 13 7 9 7 9 7 9 9 2 1 2 1 2 7 9 11 36 diepht@vnu
  37. Trộn 2 mảng tăng 20 12 20 12 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 13 11 13 7 9 7 9 7 9 9 2 1 2 1 2 7 9 11 12 37 diepht@vnu
  38. Trộn 2 mảng tăng 20 12 20 12 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 13 11 13 7 9 7 9 7 9 9 2 1 2 1 2 7 9 11 12 Thời gian trộn là tuyến tính 38 diepht@vnu
  39. Phân tích độ phức tạp T(n) MERGE-SORT A[1 . . n] Θ(1) 1. If n = 1, done. 2T(n/2) 2. Recursively sort A[ 1 . . ⎡n/2⎤ ] and A[ ⎡n/2⎤+1 . . n ] . Θ(n) 3. “Merge” the 2 sorted lists 39 diepht@vnu
  40. Cây đệ quy Giải T(n) = 2T(n/2) + cn, với hằng c > 0 cn cn cn/2 cn/2 cn h = lg n cn/4 cn/4 cn/4 cn/4 cn Θ(1) số lá = n Θ(n) Tổng = Θ(n lg n) 40 diepht@vnu
  41. Quicksort 41 diepht@vnu
  42. Thuật toán sắp xếp nhanh  Chia để trị  “in place”  Hiệu quả trên dữ liệu thực  tuning  Ý tưởng Tony Hoare 42 diepht@vnu
  43. Mô tả Sắp xếp nhanh mảng n phần tử 1. Chia: Phân hoạch (chia) mảng cần sắp thành 2 mảng con ở 2 phía của chốt x ; sao cho các phần tử ở mảng con bên trái = x 2. Trị: Sắp xếp đệ quy các mảng con 3. Kết hợp: không làm gì. Điểm then chốt: thủ tục phân hoạch chạy trong thời gian tuyến tính. 43 diepht@vnu
  44. Giả mã thủ tục phân hoạch PARTITION(A, p, q) ⊳ A[ p . . q] x ← A[ p] ⊳ pivot = A[ p] Thời gian chạy i ← p là O(n) for j ← p + 1 to q do if A[ j] ≤ x then i ← i + 1 exchange A[i] ↔ A[ j] exchange A[ p] ↔ A[i] return i Duy trì: 44 diepht@vnu
  45. Minh họa thuật toán phân hoạch 6 10 13 5 8 3 2 11 i j 45 diepht@vnu
  46. Minh họa thuật toán phân hoạch 6 10 13 5 8 3 2 11 i > j 46 diepht@vnu
  47. Minh họa thuật toán phân hoạch 6 10 13 5 8 3 2 11 i > j 47 diepht@vnu
  48. Minh họa thuật toán phân hoạch 6 5 13 10 8 3 2 11 > i j 48 diepht@vnu
  49. Minh họa thuật toán phân hoạch 6 5 13 10 8 3 2 11 i > j 49 diepht@vnu
  50. Minh họa thuật toán phân hoạch 6 5 13 10 8 3 2 11 i > j 50 diepht@vnu
  51. Minh họa thuật toán phân hoạch 6 5 3 10 8 13 2 11 > i j 51 diepht@vnu
  52. Minh họa thuật toán phân hoạch 6 5 3 10 8 13 2 11 i > j 52 diepht@vnu
  53. Minh họa thuật toán phân hoạch 6 5 3 2 8 13 10 11 > i j 53 diepht@vnu
  54. Minh họa thuật toán phân hoạch 6 5 3 2 8 13 10 11 i > j 54 diepht@vnu
  55. Minh họa thuật toán phân hoạch 6 5 3 2 8 13 10 11 i > j 55 diepht@vnu
  56. Minh họa thuật toán phân hoạch 2 5 3 6 8 13 10 11 i 56 diepht@vnu
  57. Giả mã thuật toán sắp xếp nhanh QUICKSORT(A, p, r) if p < r then q ← PARTITION(A, p, r) QUICKSORT(A, p, q–1) QUICKSORT(A, q+1, r) Lời gọi ban đầu: QUICKSORT(A, 1, n) 57 diepht@vnu
  58. Cây đệ quy trường hợp xấu nhất T(n) = T(0) + T(n–1) + cn cn Θ(1) c(n–1) Θ(1) c(n–2) 2 h = n T(n) = Θ(n) + Θ(n ) (1) = Θ(n2) Θ O Θ(1) 58 diepht@vnu
  59. Trường hợp tốt nhất?  PARTITION chia mảng thành 2 nửa bằng nhau T(n) = 2T(n/2) + Θ(n) = Θ(n lg n) 59 diepht@vnu
  60. Heapsort 60 diepht@vnu
  61. Sắp xếp sử dụng cây thứ tự bộ phận  Ý tưởng  Nếu cần sắp tăng dần, dùng max heap  Nếu cần sắp giảm dần, dùng min heap  1: Bố trí lại dữ liệu trong mảng để nó thỏa mãn tính chất của heap.  2: Lặp lại:  Đảo chỗ gốc và đỉnh cuối của heap  Giảm cỡ của heap đi 1 rồi khôi phục tính chất của heap 61 INT2203/w13 diepht@vnu
  62. Giả mã Algorithm heapSort(A, n) buildHeap(A, n) // tao 1 max-heap tu A for end <- n-1 to 1 do swap(A[0], A[end]) downheap(A, end) 62 INT2203/w13 diepht@vnu
  63. Thuật toán sắp xếp có thể nhanh tới cỡ nào? 63 diepht@vnu
  64. Cận dưới của sắp xếp  Các thuật toán sắp xếp dựa trên so sánh các cặp phần tử  comparison sorting, comparison model  có thời gian xấu nhất không thể tốt hơn O(nlogn)  Chứng minh bằng mô hình cây quyết định.  Tham khảo: Lecture 5 64 diepht@vnu
  65. Sắp xếp trong thời gian tuyến tính  Thuật toán sắp xếp đếm  counting sort  không so sánh các cặp phần tử  Giả sử dãy số nguyên nằm trong một khoảng nào đó 65 diepht@vnu
  66. Counting sort  Input: A[1 . . n], trong đó A[ j] {1, 2, , k} .  Output: B[1 . . n] được sắp. ∈  Mảng nhớ phụ trợ: C[1 . . k] . 66 diepht@vnu
  67. Counting sort: giả mã for i 1 to k do C[i] 0 for j ← 1 to n do C[A[← j]] C[A[ j]] + 1 ⊳ C[i] = |{key = i}| for i ← 2 to k do C[i] C←[i] + C[i–1] ⊳ C[i] = |{key i}| for j ← n downto 1 do B[C[←A[ j]]] A[ j] ≤ ←C[A[ j]] C[A[ j]] – 1 ← 67 diepht@vnu ←
  68. Minh họa counting sort 1 2 3 4 5 1 2 3 4 A: 44 11 33 44 33 C: B: 68 diepht@vnu
  69. Vòng for thứ nhất 1 2 3 4 5 1 2 3 4 A: 44 11 33 44 33 C: 00 00 00 00 B: for i 1 to k do← C[i] 0 69 diepht@vnu ←
  70. Vòng for thứ 2 70 diepht@vnu
  71. Vòng for thứ 2 71 diepht@vnu
  72. Vòng for thứ 2 72 diepht@vnu
  73. Vòng for thứ 2 73 diepht@vnu
  74. Vòng for thứ 2 74 diepht@vnu
  75. Vòng for thứ 3 75 diepht@vnu
  76. Vòng for thứ 3 76 diepht@vnu
  77. Vòng for thứ 3 77 diepht@vnu
  78. Vòng for thứ 4 78 diepht@vnu
  79. Vòng for thứ 4 79 diepht@vnu
  80. Vòng for thứ 4 80 diepht@vnu
  81. Vòng for thứ 4 81 diepht@vnu
  82. Vòng for thứ 4 82 diepht@vnu
  83. Phân tích độ phức tạp for i 1 to k (k) do C[i] 0 for j ← 1 to n Θ(n) do C[A[← j]] C[A[ j]] + 1 ← for i 2 to k Θ(k) ← do C[i] C[i] + C[i–1] ← Θ for j n downto 1 (n) do B[C[←A[ j]]] A[ j] ←C[A[ j]] C[A[ j]] – 1 Θ ← (n + k) ← 83 diepht@vnu Θ
  84. Tính ổn định của thuật toán sắp xếp  Thuật toán sắp xếp đếm có tính ổn định: nó bảo toàn được thứ tự giữa các phần tử có giá trị bằng nhau. 84 diepht@vnu
  85. Thuật toán sắp xếp cơ số (radix sort)  Sắp xếp theo từng “chữ số”  bằng 1 thuật toán sắp xếp ổn định. VD: counting sort  Xuất phát từ chữ số ít quan trọng hơn 85 diepht@vnu
  86. Minh họa radix sort 86 diepht@vnu
  87. Chuẩn bị tuần tới  Lý thuyết: Bài tập  SV rà soát các chương học sau thi giữa kì  Thực hành: Các chiến lược thiết kế thuật toán 87 diepht@vnu