Bài giảng Cấu trúc dữ liệu - Chương 3+4: Sắp xếp - Lê Minh Trung

TS. Lê Minh Trung Th.S Lương Trần Ngọc Khiết Khoa CNTT, Đại học Sư phạm TP. HCM Nội dung  Chọn trực tiếp (Selection Sort)  Chèn trực tiếp (Insertion Sort)  Nổi bọt (Bubble Sort)  Merge Sort  Quick Sort  Heap Sort  Radix Sort Khái niệm  Sắp thứ tự:  Đầu vào: một mảng  Đầu ra: mảng có thứ tự tăng (hoặc giảm) trên khóa  Phân loại:  Sắp thứ tự ngoại (external sort): tập tin  Sắp thứ tự nội (internal sort): bộ nhớ  Giả thiết:  Sắp thứ tự nội  Sắp tăng dần Chọn trực tiếp  Input: int a[n]  Output: mảng đã được sắp xếp  Ý tưởng:  Với mỗi i=0, 1, 2,, n-2  Tìm phần tử nhỏ nhất của mảng con a[i..n-1] và hoán vị phần tử này với a[i]. 23 78 45 8 32 56 8 78 45 23 32 56 8 23 45 78 32 56 8 23 32 78 45 56 8 23 32 45 78 56 8 23 32 45 56 78 Original List After pass 1 After pass 2 After pass 3 After pass 4 After pass 5 Sorted Unsorted Chọn trực tiếp Chọn trực tiếp void SelectionSort(int a[], int n){ for(int i=0;i<=n-2;i++){ int iMin =i; for(int j=i+1;j<n;j++){ if(a[j] <a[iMin])iMin =j; } int t= a[i]; a[i] = a[iMin]; a[iMin]=t; } } Đánh giá chọn trực tiếp  Vòng lặp for ngoài có n-1 lần lặp i=0,1,,n-2  Số phép so sánh của lần lặp thứ i: n-i-1  Số phép so sánh:  𝑆𝑆 = 𝑖=0 𝑛−2 𝑛 − 𝑖 − 1 =𝑛 − 1 + 𝑛 − 2 +⋯+ 1 = 𝑛−1 𝑛 2  Độ phức tạp của thuật toán: 𝑂 𝑛2 Chèn trực tiếp (Insertion Sort)  Input: int a[n]  Output: mảng đã được sắp xếp  Ý tưởng:  Với mỗi i=1,2,,n-1  Mảng con a[0..i-1] đã được sắp thứ tự tăng, chèn a[i] vào vị trí thích hợp để mảng con a[0..i] sắp thứ tự tăng. Original List After pass 1 After pass 2 After pass 3 After pass 4 After pass 5 23 78 45 8 32 56 23 78 45 8 32 56 23 45 78 8 32 56 8 23 45 78 32 56 8 23 32 45 78 56 8 23 32 45 56 78 Sorted Unsorted Chèn trực tiếp Chèn trực tiếp void InsertionSort(int a[], int n){ for(int i=1;i<n;i++){ int x = a[i]; int j= i-1; while(a[j]>x){ a[j+1]=a[j];j--; if(j==-1)break; } a[j+1]=x; } } Đánh giá chèn trực tiếp  Vòng lặp for ngoài có n-1 lần lặp i=1,2,,n-1  Tốt nhất  𝑆𝑆 = 𝑖=1 𝑛−11 = 𝑛 − 1 ≈ 𝑂(𝑛)  Xấu nhất  𝑆𝑆 = 𝑖=1 𝑛−12𝑖 = 2 1 + 2 +⋯+ 𝑛 − 1 = 𝑛(𝑛 − 1) ≈ 𝑂(𝑛2)  Trung bình  𝑆𝑆 ≈ 𝑂(𝑛2) Nổi bọt (Bubble Sort)  Input: int a[n]  Output: mảng đã được sắp xếp  Ý tưởng:  Với mỗi i=n-1, n-2,, 1  Với mỗi j=0, 1,, i  Nếu a[j]<a[j-1] thì swap(a[j],a[j-1]) Nổi bọt 6 4 7 2 3 4 6 2 3 7 Bước 1 Bước 2 Bước 3 Bước 4 4 2 3 6 7 2 3 4 6 7 sorted sorted sorted sorted Nổi bọt void BubbleSort(int a[],int n){ for(int i=n-1;i>=1;i--){ for(int j=1; j<=i;j++) if(a[j-1]>a[j]){ int temp =a[j-1]; a[j-1]=a[j]; a[j] = temp; } } } Đánh giá Bubble Sort  Vòng lặp for ngoài có n-1 lần lặp i=n-1, n-2, , 2, 1  Vòng lặp for trong có i lần lặp j=1, 2, , i  Mỗi lần lặp có 1 phép so sánh, số phép so sánh:  𝑆𝑆 = 𝑖=1 𝑛−1 𝑖 = 1 + 2 +⋯+ 𝑛 − 1 = 𝑛−1 𝑛 2 ≈ 𝑂(𝑛2)  Độ phức tạp của thuật toán: 𝑂(𝑛2) Cải tiến Bubble Sort  Cho phép nổi bọt theo hai chiều  Nổi bọt xuống, nổi bọt lên  Khi nổi bọt ghi nhận lại  Có sự nổi bọt thật sự hay không  exchange =false mảng đã được sắp thứ tụ  Vị trí nổi bọt cuối cùng Bubble Sort cải tiến void BubbleSort(int a[],int n){ int iMax=n-1, jMax=0,t,k; bool exchange = true; do { exchange =false; for(int i=jMax;i<iMax;i++) //nổi bọt xuống if(a[i]>a[i+1]){t=a[i]; a[i]=a[i+1]; a[i+1]=t;exchange=true;k=i;} iMax =k; if(!exchange)break; //nếu không có hoán vị nào trước đó thì thoát vì mảng đã được sắp thứ tự exchange = false; for(int i=iMax;i>jMax;i--) //nổi bọt lên if(a[i]<a[i-1]){t=a[i];a[i]=a[i-1]; a[i-1]=t; exchange=true; k=i;} jMax=k; }while(exchange); } Chia để trị  Ý tưởng:  Chia danh sách ra làm 2 phần  Sắp thứ tự riêng cho từng phần  Trộn 2 danh sách riêng đó thành danh sách có thứ tự  Hai giải thuật:  Merge sort:  Chia đều thành 2 danh sách  Sắp thứ tự riêng  Trộn lại  Quick sort:  Chia thành 3 phần: nhỏ, giữa (pivot), lớn  Sắp thứ tự riêng Đánh giá sơ lược giải thuật chia để trị  Giả sử 2 danh sách có số phần tử là n’ = n/2  Dùng insertion sort riêng cho từng mảnh  Trộn 2 danh sách tốn (n’ + n’) = n lần so sánh  Số lần so sánh tổng cộng: 2*((n/2)2/2 + O(n/2)) + n = n2/4 + O(n)  So sánh với insertion sort là n2/2 + O(n)  Có vẻ nhanh hơn Merge sort Start 26 33 29 35 26 29 33 35 12 19 22 12 19 22 26 29 33 35 12 19 Finish 26 33 35 29 19 12 22 26 33 26 33 35 29 35 29 26 33 35 29 19 12 22 19 12 19 12 22 Trộn Trộn Trộn Trộn Trộn Trộn Trộn hai mảng con tăng void Merge(int a[], int first, int last){ int mid = (first +last)/2; int first1= first, last1=mid; int first2=mid+1, last2=last; int temp[MAX_SIZE]; int i=first1, j=first2, k=0; while ((i<=last1)&&(j<=last2)) { if(a[i]<=a[j])temp[k++]=a[i++]; else temp[k++] = a[j++]; } if(i>last1) //mảng bên trái hết phần tử while(j<=last2)temp[k++]=a[j++]; if(j>last2) //mảng bên phải hết phần tử while(i<=last1)temp[k++]=a[i++]; for(i=first;i<=last;i++)a[i]=temp[i-first]; //copy mảng tạm vào a[first..last] } Merge Sort void MergeSort(int a[], int first, int last){ if(first<last){//mảng con có nhiều hơn một phần tử int mid = (first +last)/2; MergeSort(a,first,mid); MergeSort(a, mid+1, last); Merge(a,first, last); } } Merge Sort – Ví dụ 6 3 9 1 5 4 7 2 5 4 7 26 3 9 1 6 3 9 1 7 25 4 6 3 19 5 4 27 3 6 1 9 2 74 5 2 4 5 71 3 6 9 1 2 3 4 5 7 8 9 divide dividedividedivide dividedivide divide merge merge merge merge merge merge merge Phân tích thuật toán Merge Trường hợp xấu nhất Phân tích thuật toán Merge Trộn hai mảng kích cỡ k  Tốt nhất:  Tất cả phần tử trong mảng trái nhỏ hơn phần tử trong mảng phải.  Số phép so sánh: k + 1  Xấu nhất:  i = k-1 và j = k-1  Số phép so sánh: 2k ...... ...... ...... 0 k-1 0 k-1 0 2k-1 Phân tích Merge Sort Các cấp gọi đệ qui của mảng có 8 phần tử Phân tích Merge Sort . . . . . . . . . . . . . . . . . . . . . . . 2m 2m-1 2 m-1 2m-2 2m-2 2m-2 2m-2 20 2 0 level 0 : 1 merge (size 2m-1) level 1 : 2 merges (size 2m-2) level 2 : 4 merges (size 2m-3) level m level m-1 : 2m-1 merges (size 20) Đánh giá Merge Sort  Xấu nhất Số phép so sánh: = (2*20 )*2m-1 + (2*21)*2m-2 + ... + (2*2m-1)*20 = 2m + 2m + ... + 2m ( m hạng tử ) = m*2m Thay m = log n Số phép so sánh: = n * log2n O (n * log2n ) Đánh giá Merge Sort  Merge Sort là thuật toán hiệu quả xét trên phương diện độ phức tạp tính toán và thời gian.  Độ phức tạp trong cả trường hợp tốt nhất và xấu nhất: O (n * log2n )  Để trộn hai mảng con của một mảng cho trước, đòi hỏi một mảng có kích cỡ bằng kích cỡ mảng ban đầu . Quick Sort Sort (26, 33, 35, 29, 19, 12, 22) Sort (19, 12, 22) Sort (33, 35, 29) Combine into (12, 19, 22, 26, 29, 33, 35) Phân thành (19, 12, 22) và (33,35,29) với pivot=26 Phân thành (12) và (22) với pivot=19 Phân thành (29) và (35) với pivot=33 Sort (12) Sort (22) Combine into (12, 19, 22) Sort (29) Sort (35) Combine into (29, 33, 35) Quick Sort Algorithm Quick Sort Input: mảng cần sắp Output: mảng đã được sắp xếp 1. if (có ít nhất 2 phần tử) //Phân hoạch mảngthành 3 phần: //- Phần nhỏ hơn phần tử giữa //- Phần tử giữa //- Phần lớn hơn phần tử giữa 1.1. Phân hoạch mảng thành 3 phần 1.2. Call QuickSort cho phần bên trái 1.3. Call QickSort cho phần bên phải //Chỉ cần ghép lại là thành danh sách có thứ tự End Quick Sort void QuickSort(int a[], int low, int high){ if(low<high){ int pivot_pos = Partition(a, low, high); QuickSort(a,low,pivot_pos); QuickSort(a, pivot_pos+1, high); } } Phân hoạch cho Quick Sort Phân hoạch cho Quick Sort Partition Quick Sort int Partition(int a[], int low, int high){ int mid = (low + high)/2; Swap(a[low], a[mid]); int pivot = a[low]; int last_small = low; for(int i= low+1; i<=high; i++) if(a[i]<pivot){ last_small ++; Swap(a[last_small],a[i]); } Swap(a[low],a[last_small]); return last_small; } Ví dụ Quick Sort 19 35 33 26 29 12 22 0 1 2 3 4 5 6 low=0 high=6 mid=(low+high)/2=3 QuickSort(0,6) pivot_position = Partition(0,6)= 3 pivot last_small index 26 pivot_position QuickSort(0,2) QuickSort(4,6) Ví dụ Quick Sort 22 19 12 26 29 33 35 0 1 2 3 4 5 6 low=0 high=2 mid=(low+high)/2=1 QuickSort(0,2) pivot_position = Partition(0,2) = 1 last_small index pivot 19 pivot_position QuickSort(0,0) QuickSort(2,2) (Không làm gì cả) Ví dụ Quick Sort 29 33 352612 19 22 0 1 2 3 4 5 6 low=4 high=6 mid=(low+high)/2=5 QuickSort(4,6) pivot_position = Partition(4,6)= 5 last_small index pivot 33 pivot_position QuickSort(4,4) QuickSort(6,6) (Không làm gì cả) Các trường hợp của Quick sort Đánh giá Quick Sort  Trường hợp xấu nhất:  Một bên rỗng và một bên là n-1 phần tử => n(n-1)/2  Chọn phần tử pivot:  Đầu (hay cuối): trường hợp xấu xảy ra khi danh sách đang có thứ tự (hoặc thứ tự ngược)  Ở trung tâm, hoặc ngẫu nhiên: trường hợp xấu khó xảy ra  Trường hợp trung bình:  C(n) = 2n ln n + O(n) ≈ 1.39 n lg n + O(n) ≈O(nlogn) Heap và Heap Sort  Heap (định nghĩa lại):  Mảng có n phần tử (từ 0 đến n-1)  ak ≥ a2k+1 và ak ≥ a2k+2 (ak lớn nhất trong 3 phần tử)  Đặc tính:  a0 là phần tử lớn nhất  Heap chưa chắc có thứ tự  Nửa sau của mảng bất kỳ thỏa định nghĩa heap  Heap sort:  Lấy a0 ra, tái tạo lại heap => Phần tử lớn nhất  Lấy a0 mới ra, tái tạo lại heap => Phần tử lớn kề  Heap Sort void HeapSort(int a[], int n){ //xây dựng heap ban đâu BuildHeap(a,n); //mảng đã là một heap for(int i=n-1; i>=1; i--){ int current = a[i]; a[i]= a[0]; //chuyển phần tử lớn nhất về cuối //a[1..i-1] đang là heap, thêm current vào để vẫn là heap InsertHeap(current,a,0,i-1); } } Biểu diễn Heap  Dạng cây nhị phân:  Node gốc là a0  2 node con của phần tử ak là 2 phần tử a2k+1 và a2k+2  Ở mức cuối cùng, các node lấp đầy từ bên trái sang bên phải (cây nhị phân gần đầy đủ) 0 1 2 3 4 5 6 7 8 Ví dụ Heap Sort y r p d f b k a c 0 1 2 3 4 5 6 7 8 y r p d f b k a c current Ví dụ Heap Sort r f p d c b k a y 0 1 2 3 4 5 6 7 8 r f p d c b k a y current Ví dụ Heap Sort p f k d c b a r y 0 1 2 3 4 5 6 7 8 p f k d c b a r y current Ví dụ Heap Sort k f b d c a p r y 0 1 2 3 4 5 6 7 8 k f b d c a p r y current Ví dụ Heap Sort f d b a c k p r y 0 1 2 3 4 5 6 7 8 f d b a c k p r y current Ví dụ Heap Sort d c b a f k p r y 0 1 2 3 4 5 6 7 8 d c b a f k p r y current Ví dụ Heap Sort c a b d f k p r y 0 1 2 3 4 5 6 7 8 c a b d f k p r y current Ví dụ Heap Sort b a c d f k p r y 0 1 2 3 4 5 6 7 8 b a c d f k p r y current Algorithm InsertHeap Input: mảng là heap trong khoảng từ low+1 đến high, current là giá trị cần thêm vào Output: mảng là heap trong khoảng từ low đến high 1. Bắt đầu kiểm tra tại vị trí low 2. while (chưa kiểm tra xong đến high) 2.1. Tìm lớn nhất trong bộ ba phần tử current, a[2k+1], a[2k+2] 2.2. if (phần tử đó là current) 2.2.1. Ngừng vòng lặp 2.3. else 2.3.1. Dời phần tử lớn nhất lên vị trí hiện tại 2.3.2. Kiểm tra bắt đầu từ vị trí của phần tử lớn nhất này 3. Đưa current vào vị trí đang kiểm tra End Giải thuật tái tạo lại Heap Giải thuật tái tạo Heap  Input: InsertHeap(current, a[], low, high)  Mảng a[low+1high] đã là một heap  Output: thêm current vào sao cho mảng a[lowhigh] vẫn là một heap void InsertHeap(int current,int a[], int low, int high) { int large = 2*low +1; while(large <=high){//chưa xét hết phần tử if(large<high) //có đủ hai con if(a[large +1]>a[large])large++; if(current>=a[large])break; a[low]=a[large]; //di chuyển phần tử max low = large; large = 2*low +1; } a[low]=current; //chuyển current vào vị trí đang xét } Xây dựng Heap ban đầu void BuildHeap(int a[],int n){ //nửa sau từ n/2 --> n-1 đã là một heap for(int i=n/2-1; i>=0; i--){ int current = a[i]; InsertHeap(current,a,i,n-1); } } Ví dụ xây dựng Heap ban đầu p c y d f b k a r 0 1 2 3 4 5 6 7 8 Bước 1 p c y r f b k a d 0 1 2 3 4 5 6 7 8 Bước 2 p c y r f b k a d 0 1 2 3 4 5 6 7 8 Bước 3 p r y c f b k a d 0 1 2 3 4 5 6 7 8 Bước 3’ p r y d f b k a c 0 1 2 3 4 5 6 7 8 Bước 4 y r p d f b k a c 0 1 2 3 4 5 6 7 8 Đánh giá Heap Sort  Trường hợp xấu nhất và trung bình:  C = 2n lg n + O(n)  M = n lg n + O(n)  So với Quick Sort  Trung bình: chậm hơn quick sort  Xấu nhất: O(n lg n) < n(n-1)/2 Radix Sort  Radix sort khác với các phương pháp sắp xếp khác.  Radix sort  Xem các phần tử như các chuỗi  Nhóm các phần tử có cùng kí tự tận cùng phải  Nhập các nhóm lại với nhau  Lập lại bước trên cho tất cả các vị trí từ vị trí tận cùng phải (rightmost) cho đến vị trí tận cùng trái (leftmost) mom, dad, god, fat, bad, cat, mad, pat, bar, him original list (dad,god,bad,mad) (mom,him) (bar) (fat,cat,pat) group strings by rightmost letter dad,god,bad,mad,mom,him,bar,fat,cat,pat combine groups (dad,bad,mad,bar,fat,cat,pat) (him) (god,mom) group strings by middle letter dad,bad,mad,bar,fat,cat,pat,him,god,mom combine groups (bad,bar) (cat) (dad) (fat) (god) (him) (mad,mom) (pat) group strings by first letter bad,bar,cat,dad,fat,god,him,mad,mom,par combine groups (SORTED) Radix Sort – Ví dụ Radix Sort – Ví dụ void RadixSort(inout theArray:ItemArray, in n:integer, in d:integer) // sort n d-digit integers in the array theArray for (j=d; j>=1; j--) { Khởi tạo 10 nhóm bằng rỗng Khởi tạo các counter của các nhóm bằng 0 for (i=0; i<n; i++) { k = chữ số thứ j của theArray[i] Đặt theArrar[i] vào nhóm thứ k Tăng counter thứ k thêm 1 } Thay thế các phần tử trong theArray bởi các phần tử trong nhóm 1, nhóm 2, theo thứ tự } Radix Sort - Algorithm Đánh giá Radix Sort  Đòi hỏi 2*n*d phép gán để sắp n chuỗi có chiều dài là d  Độ phức tạp O(n) So sánh các giải thuật Luyện tập  Trình bày cách thực hiện sắp xếp mảng sau theo các thuật toán (ghi kết quả sau từng bước)  Selection Sort  Insertion Sort  Buble Sort  Merge Sort  Quick Sort  A={10, 3, 7, 6, 2, 5, 4, 16, 20, 1 }