Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 12: Các thuật toán sắp xếp nhanh O(nlogn)

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 12: Các thuật toán sắp xếp nhanh O(nlogn)

1. Bài 12. Các thuật toán sắp xếp nhanh O(nlogn) Sắp xếp nhanh – Quick sort Sắp xếp trộn - Merge sort Vun đống – Heap sort Sorting 1
2. Chia và trị - Divide and conquer Chia và trị là phương pháp thiết kế thuật toán theo kiểu: n Phân chia: Chia dữ liệu đầu vào S của bài toán thành 2 tập con rời nhau S1 và S2 n Đệ qui: Giải bài toán với dữ liệu vào là các tập con S1 và S2 n Trị: kết hợp các kết quả của S1 và S2 thành kết quả của S Trường hợp cơ sở cho thuật toán đệ qui ở đây là các bài toán có kích thước 0 hoặc 1 Sorting 2
3. Sắp xếp nhanh – Quick sort Ý tưởng (sử dụng phương pháp chia và trị): n Thực hiện phân hoạch dãy S cần sắp thành 3 dãy S1, S2, S3. Trong đó: • S2 chỉ có một phần tử, tất cả các phần tử của dãy S3 đều > phần tử của dãy S2. • Tất cả các phần tử của dãy S1 đều ≤ phần tử của dãy S2 • Dãy S1, S3 có thể là rỗng n Tiếp tục phân hoạch dãy S1 và S3 độc lập theo nguyên tắc trên đến khi dãy cần thực hiện phân hoạch chỉ có một phần tử thì dưng lại. Khi đó ta được dãy các phần tử được sắp. Sorting 3
4. Thuật toán sắp xếp Quick sort Từ ý tưởng của thuật toán, ta có thể dễ dàng xây dựng thuật toán sắp xếp dưới dạng đệ qui như sau: Algorithm QuickSort (array A, i, j ); Input: Dãy các phần tử A[i], ,A[j] và hai số nguyên i, j Output: Dãy A[i], ,A[j] được sắp. if i < j then Partition (A,i, j, k); //k lấy chỉ số của phần tử làm S2 Quicksort (A,i, k-1); Quicksort (A,k+1, j); Sorting 4
5. Ví dụ Sorting 5
6. Vấn đề đặt ra ở đây là phân hoạch dãy S như thế nào? Sorting 6
7. Thuật toán phân hoạch • Chọn một phần tử bất kỳ của dãy làm dãy S2 6 12 32 1 3 (phần tử này được gọi là phần tử chốt -pivot). 6 3 32 1 12 • Thực hiện chuyển các phần tử có khóa ≤ phần tử chốt về bên trái và các phần tử > phần tử chốt 6 3 1 32 12 về bên phải, sau đó đặt phần tử chốt về đúng vị trí của nó trong dãy. 1 3 6 32 12 Sau khi phân hoạch Sorting 7
8. Chú ý • Phần tử chốt có thể được chọn là một phần tử bất kỳ của dãy. - Phần tử chốt có thể chọn là phần tử đầu hoặc giữa hoặc cuối dãy. - Tốt nhấ là chọn phần tử chốt mà nó làm cho việc phân hoạch thành hai dãy S1 và S3 có số phần tử xấp xỉ bằng nhau. Sorting 8
9. Thuật toán • Phân hoạch dãy gồm các phần tử A[i], ,A[j] • Chọn phần tử đầu dãy làm chốt • Sử dụng 2 biến left và right: - left chạy từ trái sang phải bắt đầu từ i. - right chạy từ phải sang trái bắt đầu từ j - Biến left được tăng cho tới khi A[left].Key> A[i].Key hoặc left >right - Biến right được giảm cho tới khi A[right].Key right - Cuối cùng tráo đổi A[i] và A[right] Sorting 9
10. Ví dụ phân hoạch 10 3 24 1 4 21 54 5 i j ? Sorting 10
11. Thuật toán phân hoạch Algorithm Partition (Array A, i, j, &right ) Input: Dãy các phần tử A[i], ,A[j], 2 số nguyên i, j Output: Dãy A[i], ,A[j] được phân hoạch, right là chỉ số của phần tử làm S2. p  A[i]; left  i; right  j; while ( left p.Key ) right right-1; if left right then A[i]  A[right]; A[right]  p; Sorting 11
12. Ví dụ Sắp xếp dãy số A= 10 3 24 1 4 21 54 5 i=1 j=8 ? Sorting 12
13. Mô tả quá trình Sắp xếp 10 3 24 1 4 21 54 5 Quicksort(A,1, 8) i=1 j=8 i<j partition(A,1,8,k) 4 3 5 1 10 21 54 24 i=1 k=5 j=8 Quicksort(A,1, 4) 4 3 5 1 10 21 54 24 i=1 j=4 i<j partition(A,1,4,k) 1 3 4 5 10 21 54 24 i=1 k=3 j=4 Sorting 13
14. Quicksort(A,1, 2) 1 3 4 5 10 21 54 24 i=1 j=2 i<j partition(A,1,2,k) 1 3 4 5 10 21 54 24 i=k=1 j=2 Quicksort(A,2, 2) 1 3 4 5 10 21 54 24 i=j=2 Quicksort(A,4, 4) 1 3 4 5 10 21 54 24 i=j=4 Quicksort(A,6, 8) 1 3 4 5 10 21 54 24 i=6 j=8 i<j partition(A,6,8,k) 1 3 4 5 10 21 54 24 i=k=6 j=8 Sorting 14
15. Quicksort(A,6,5) 1 3 4 5 10 21 54 24 j=5 i=6 Quicksort(A,7,8) i<j Patiction(A,7,8,k) 1 3 4 5 10 21 54 24 i=7 k=j=8 Quicksort(A,7,7) 1 3 4 5 10 21 24 54 i=7 j=7 Quicksort(A,9,8) 1 3 4 5 10 21 24 54 i=9 j=8 Sorting 15
16. Thời gian chạy • Thủ tục partition kiểm tra tất cả các phần tử trong mảng nhiều nhất một lần, vì vậy nó mất thời gian tối đa là O(n). • Thủ tục partition sẽ chia phần mảng được sắp thành 2 phần. • Mặt khác cần chia liên tiêp n phần tử thành hai phần thì số lần chia nhiều nhất là log2n lần. • Vậy thời gian chạy của thuật toán QuickSort là O(nlogn) Sorting 16
17. Thuật toán MergeSort Ý tưởng: • Giả sử ta có hai dãy A[i], ,A[k] và A[k+1], ,A[j] và hai dãy này đã được sắp. • Thực hiện trộn hai dãy trên để được dãy A[i], ,A[j] cũng được sắp • Do hai dãy A[i], ,A[k] và dãy A[k+1], ,A[j] đã được sắp nên việc trộn hai dãy thành một dãy được sắp là rất đơn giản. • Vậy trộn như thế nào? Sorting 17
18. Ví dụ: Trộn hai dãy sau A 1 3 24 4 21 54 i k k+1 j Sorting 18
19. Thuật toán trộn • Sử dụng hai biến left, right, t và sử dụng mảng phụ B[i], ,B[j]. left xuất phát từ i, right xuất phát từ k+1, t xuất phát tử i trên mảng phụ B. • Nếu A[left].key k hoặc right>j thì dừng lại. Sorting 19
20. Thuật toán trộn (tiếp) • Nếu left>k thì B[t]A[right], ,B[j]A[j]. • Nếu right>j thì B[t]A[left], B[t+1]A[letf+1], , B[t+k-left]A[k]. • Gán A[i] B[i], , A[j] B[j] Sorting 20
21. Quá trình trộn dãy Left=i Right=k+1 A 1 3 24 4 21 54 i k j B 1 t=i Left=i+1 Right=k+1 A 1 3 24 4 21 54 i k j B 1 3 t=i+1 Sorting 21
22. Left=i+2 Right=k+1 A 1 3 24 4 21 54 i k j B 1 3 4 t=i+2 Left=i+2 Right=k+2 A 1 3 24 4 21 54 i k j B 1 3 4 21 t=i+3 Left=i+2 Right=k+3 A 1 3 24 4 21 54 i k j B 1 3 4 21 24 t=i+4 Sorting 22
23. Left=i+3 Right=k+3 A 1 3 24 4 21 54 i k j B 1 3 4 21 24 54 t=i+5 A 1 3 4 21 24 54 i k j B 1 3 4 21 24 54 Sorting 23
24. Thuật toán giả mã Algorithm Merge(array A, int i, int k, int If left>k then j) for rright to j do Input: Hai dãy A[i], ,A[k] và A[k+1], ,A[j] B[t]  A[r]; đã được sắp và các số nguyên i, j t++; Output: Dãy A[i], ,A[j] cũng được sắp else left i; rightk+1; t i; for r left to k do While (left≤k) and (right≤j) do B[t] A[r]; if A[left].key<A[right].key then t++; B[t]  A[left]; for r i to j do left left+1; A[r]  B[r] ; t t+1; else B[t]  A[right]; right right+1; t t+1 ; //kết thúc while Sorting 24
25. Thuật toán • Để sắp xếp dãy A[1], ,A[n] ta thực hiện như sau: • Chia dãy trên thành hai dãy:A[1], ,A[k] và dãy A[k+1], ,A[n], trong đó k=(n+1)/2 • Thực hiện sắp xếp 2 dãy A[1], ,A[k] và A[k+1], ,A[n] độc lập cũng theo thuật toán Mergesort. • Thực hiện trộn hai dãy:A[1], ,A[k] và dãy A[k+1], ,A[n] để được dãy A[1], A[n] cũng được sắp Sorting 25
26. Thuật toán giả mã Algorithm Mergesort(array A,int i, int j) Input: Dãy các phần tử A[i], ,A[j] Output:Dãy A[i], ,A[j] được sắp. if i<j then k(i+j)/2; Mergesort(A,i, k); Mergesort(A, k+1,j); Merge(A, i, k, j); Sorting 26
27. Mô tả quá trình thực hiện sắp xếp v Ví dụ xắp xếp dãy:A= 7 2 9 4 3 8 6 1 • Gọi thủ tục MergeSort(A, 1, 8), chia đôi dãy 7 2 9 4  3 8 6 1 1 2 3 4 6 7 8 9 7 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6 7 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6 7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1 Sorting 27
28. Tiếp v Gọi đệ qui và phân chia Mergesort(A,1,4) 7 2 9 4  3 8 6 1 1 2 3 4 6 7 8 9 7 2  9 4 2 4 7 9 3 8 6 1 1 3 8 6 7 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6 7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1 Sorting 28
29. Tiếp v Gọi đệ qui và phân chia Mergesort(A,1,2) 7 2 9 4  3 8 6 1 1 2 3 4 6 7 8 9 7 2  9 4 2 4 7 9 3 8 6 1 1 3 8 6 7  2 2 7 9 4 4 9 3 8 3 8 6 1 1 6 7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1 Sorting 29
30. Tiếp v Gọi đệ qui Mergesort(A,1,1), đây là trường hợp cơ sở 7 2 9 4  3 8 6 1 1 2 3 4 6 7 8 9 7 2  9 4 2 4 7 9 3 8 6 1 1 3 8 6 7  2 2 7 9 4 4 9 3 8 3 8 6 1 1 6 7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1 Sorting 30
31. Tiếp v Gọi đệ qui Mergesort(A,2,2), đây là trường hợp cơ sở 7 2 9 4  3 8 6 1 1 2 3 4 6 7 8 9 7 2  9 4 2 4 7 9 3 8 6 1 1 3 8 6 7  2 2 7 9 4 4 9 3 8 3 8 6 1 1 6 7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1 Sorting 31
32. Tiêp v Trộn merge(A,1,1,2) 7 2 9 4  3 8 6 1 1 2 3 4 6 7 8 9 7 2  9 4 2 4 7 9 3 8 6 1 1 3 8 6 7  2 2 7 9 4 4 9 3 8 3 8 6 1 1 6 7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1 Sorting 32
33. Execution Example (cont.) v Gọi đệ qui Mergesort(A,3,3), Mergesort(A,4,4) và trộn merge(A,3,3,4) 7 2 9 4  3 8 6 1 1 2 3 4 6 7 8 9 7 2  9 4 2 4 7 9 3 8 6 1 1 3 8 6 7  2 2 7 9 4 4 9 3 8 3 8 6 1 1 6 7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1 Sorting 33
34. Tiếp v Trộn merge(A,1,2,4) 7 2 9 4  3 8 6 1 1 2 3 4 6 7 8 9 7 2  9 4 2 4 7 9 3 8 6 1 1 3 8 6 7  2 2 7 9 4 4 9 3 8 3 8 6 1 1 6 7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1 Sorting 34
35. Tiếp v Tương tự như trên với nửa bên phải của dãy 7 2 9 4  3 8 6 1 1 2 3 4 6 7 8 9 7 2  9 4 2 4 7 9 3 8 6 1 1 3 6 8 7  2 2 7 9 4 4 9 3 8 3 8 6 1 1 6 7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1 Sorting 35
36. Tiếp v Trộn hai nửa dãy thành dãy được sắp merge(A, 1, 4, 8) 7 2 9 4  3 8 6 1 1 2 3 4 6 7 8 9 7 2  9 4 2 4 7 9 3 8 6 1 1 3 6 8 7  2 2 7 9 4 4 9 3 8 3 8 6 1 1 6 7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1 Sorting 36
37. Thời gian chạy của thuật toán Chiều cao h của cây merge-sort là O(log n) n Tại mỗi bước gọi đệ qui ta chia dãy cần sắp thành hai phần, Thời tổng thời gian làm việc trên các nút ở mức i nhiều nhất là O(n) n Chúng ta chia và trộn 2i chuỗi có kích thước là n/2i n Chúng ta gọi 2i+1 lần đệ qui Vì vậy, tổng thời gian chạy của thuật toán mergesort là O(n log n) ĐSâu #dãy size 0 1 n 1 2 n/2 i 2i n/2i Sorting 37
38. Cây Heap và Thuật toán sắp xếp vun đống Heapsort • Cây heap (đống) là một cây nhị phân được sắp xếp theo khóa của các nút với các tính chất sau: • Giá trị khóa của nút gốc giá trị khóa của hai con • Tất cả các mức đều đầy trừ mức thấp nhất có thể thiếu một số nút • Các nút lá phải xuất hiện liên tiếp từ trái qua phải • Như vậy nút gốc có giá trị khóa lớn nhất • Ví dụ: 10 10 0 0 90 70 90 70 60 60 73 60 50 73 60 50 23 31 43 23 45 31 43 ? Cây Heap Không phải cây Heap Sorting 38
39. Mảng biểu diễn cây heap • Mảng A[1], ,A[n] là mảng biểu diễn cây heap nếu: • A[i] A[2i] và A[i] A[2i+1] với i=1 n/2 • Như vậy phần tử đầu của mảng có giá trị lớn nhất • Ví dụ: A 100 90 70 73 60 50 60 23 45 31 43 A[1] A[2], A[1] A[3] A[3] A[6], A[3] A[7] A[2] A[4], A[2] A[5] A[4] A[8], A[4] A[9] A[5] A[10], A[5] A[11] Sorting 39
40. Thuật toán sắp xếp vun đống Ý tưởng: • Tạo mảng A[1], ,A[n] biểu diễn cây Heap. • Tráo đổi phần tử A[1] với phần tử A[n]. • Tạo mảng A[1], ,A[n-1] biểu diễn cây heap • Tráo đổi phần tử A[1] với phần tử A[n-1]. • Lặp lại quá trình trên đến khi mảng chỉ còn 1 phần tử Sorting 40
41. Tạo đống ? Sorting 41
42. Tạo mảng biểu diễn cây heap • Theo tính chất của mảng biểu diễn cây Heap thì các phần tử từ n/2+1 đến n không cần điều kiện ràng buộc. Vì vậy ta thực coi các phần tử này đã thỏa mãn điều kiện cây heap. • Ta thực hiện: - Bổ sung phần tử n/2 vào A[n/2+1], ,A[n] để được mảng gồm A[n/2], ,A[n] thỏa mãn kiện - Bổ sung phần tử n/2-1 vào A[n/2], ,A[n] để được mảng gồm A[n/2-1] , ,A[n] thỏa mãn kiện - Và cứ tiếp tục làm như vậy cho đến khi bổ sung phần tử A[1] vào A[2], ,A[n] để được mảng gồm A[1], ,A[n] thỏa mãn điều kiện Sorting 42
43. Ví dụ Cho mảng như dưới đây, hãy biến đổi mảng để được mảng thỏa mãn tính chất mảng biểu diễn cây heap 12 32 10 4 23 54 21 15 3 7 12 32 10 4 23 54 21 15 3 7 Cây tương ứng với mảng Sorting 43
44. Mô tả trên mảng: N=10 12 32 10 4 23 54 21 15 3 7 - Đổi chỗ A[5] và A[10] nếu A[5]<A[10] i=5 12 32 10 4 23 54 21 15 3 7 - Tính max(A[8], A[9]). Nếu A[4]<max thì đổi chỗ A[4] i=4 với phần tử đạt max 12 32 10 4 23 54 21 15 3 7 Cây tương ứng với mảng Sorting 44
45. 12 32 10 15 23 54 21 4 3 7 - Tính max(A[6], A[7]). Nếu A[3]<max thì đổi chỗ A[3] i=3 với phần tử đạt max 12 32 10 15 23 54 21 4 3 7 Cây tương ứng với mảng Sorting 45
46. 12 32 54 15 23 10 21 4 3 7 - Tính max(A[4], A[5]). Nếu A[2]<max thì đổi chỗ A[2] i=2 với phần tử đạt max 12 32 54 15 23 10 21 4 3 7 Cây tương ứng với mảng Sorting 46
47. 12 32 54 15 23 10 21 4 3 7 - Tính max(A[2], A[3]). Nếu A[1]<max thì đổi chỗ A[1] i=1 với phần tử đạt max 12 32 54 15 23 10 21 4 3 7 Cây tương ứng với mảng Sorting 47
48. 54 32 12 15 23 10 21 4 3 7 - Tính max(A[6], A[7]). Nếu A[3]<max thì đổi chỗ A[3] i=3 với phần tử đạt max 54 32 12 15 23 10 21 4 9 10 Cây tương ứng với mảng Sorting 48
49. 54 32 21 15 23 10 12 4 3 7 - Tính max(A[6], A[7]). Nếu A[3]<max thì đổi chỗ A[3] i=3 với phần tử đạt max 54 32 21 15 23 10 12 ` 4 9 10 Cây heap Sorting 49
50. Thuật toán bổ sung một phần tử để tạo mảng biểu diễn cây heap Algorithm Pushdown (Array A, i, n); Input: số nguyên i, n, mảng A[i], ,A[n], trong đó A[i+1], ,A[n] thỏa mãn tính chất cây heap Output: Mảng A[i], ,A[n] thỏa mãn tính chất cây heap j  i; kt  0; while (j≤ n/2) and (kt=0) do if 2*j = n then max  2*j; else if A[2*j].key ≤ A[2*j+1].key then max  2*j+1 else max  2*j; if A[j].key < A[max].key then swap (A[j], A[max]); j  max; else kt 1; Sorting 50
51. Thuật toán sắp xếp vun đống Algorithm Heapsort(Array A, n); Input: Mảng A có và số nguyên n Output: Mảng A được sắp theo thứ tự tăng dần của thuộc tính khóa for i n/2 downto 1 do Pushdown(A, i, n); for i ndownto 2 do swap(A[1],A[i]); Pushdown(A,1,i-1); Sorting 51
52. Ví dụ: Mô tả quá trình sắp xếp của dãy số 12 43 11 34 23 43 12 435 Sorting 52
53. Thời gian chạy • Thời gian thực hiện thủ tục Pushdown. § Là t/g thực hiện của vòng lặp while. k § Gọi k là số lần lặp, ta có i*2 n hay k log2(n/i). § T/g thực hiện hàm Pushdown (A,i, n) là 0(log(n/i) • Xét thủ tục HeapSort § Vòng lặp for đầu có số lần lặp là n/2 § Mỗi lần gọi hàm Pushdown 1 lần. Do đó t/g thực hiện là 0(log2n). § Tương tự, vòng lặp for thứ 2 có số lần lặp là n-1. 0(nlog2n). § Vì vậy t/g thực hiện HeapSort là O(nlog2n). Sorting 53
54. Hết Sorting 54
55. Bài tập Xây dựng các thủ tục sắp xếp theo 6 phương pháp đã học Sorting 55