Bài giảng Sắp xếp

Bài 7:Sắp xếp (Sorting) Yêu cầu về sắp xếp thường xuyên xuất hiện trong các ứng dụng tin học Các pp sắp xếp Sắp xếp trong Sắp xếp ngoài Cơ sở Xét dãy với số phần tử n≥0. Sắp xếp nghĩa là tổ chức lại các phần tử tạo ra dãy S’ mới sao cho các phần tử trong đó tuân theo một thứ tự nhất định Định nghĩa:  thứ tự là một quan hệ, ký hiệu pj với isj ii+1; j--) if (s[j] 42 thì so sánh sj với 42 → đổi chỗ (si, sj) cho nhau → j cố định, i tăng. Khi i  j thì khóa chốt được đặt vào đúng vị trí bằng cách đổi chỗ 42 với kj. → lặp lại tương tự cho đến khi dãy được sắp Void QuickSort(S, LB, UB) { B=true; if (LB key) j - -; if (isj hay sj>s2j, với 1  [j/2] =1; i--) ADJUST(i, n); for (i=n-1;i>= 1;i--) { Swap(1, i+1); ADJUST(1, i); } } Ví dụ 3. Sắp xếp kiểu vun đống… c. Phân tích và đánh giá Đánh giá Không cần bộ nhớ phụ như QuickSort Cây nhị phân đầy đủ n nút có chiều cao O(logn). Trường hợp xấu nhất O(nlogn) Định lý: Cây nhị phân hoàn chỉnh T có độ cao h thì tổng độ cao các nút của cây là 3. Sắp xếp kiểu vun đống… Cm: cây nhị phân hoàn chỉnh có 1 nút độ cao h, 2 nút độ cao h-1, 4 nút độ cao h-2,.. Tổng quát có 2i nút có độ cao h-i O(n) Thay đổi thuật toán để sắp xếp theo chiều giảm dần Tìm phần tử nhỏ nhất dãy sau khi vun thành cây Heap 4. Sắp xếp kiểu hòa nhập (Merge Sorting) a. Hòa nhập 2 đường (two-way merge) Hợp nhất các khóa của 2 dãy đã được sắp để thành 1 dãy có kích thước lớn hơn cũng được sắp Nguyên tắc: so sánh 2 khóa nhỏ nhất của 2 dãy con → đưa khóa nhỏ hơn ra miền sắp xếp, loại ra khỏi dãy chứa nó. Tiếp tục cho đến khi 1 trong 2 dãy đã hết. Chuyển phần còn lại ra miền sắp xếp. 4. Sắp xếp kiểu hòa nhập … Ví dụ 17 42 50 67 9 34 81 void Merge(x, b, m, n, z) { i=k=b; j=m+1; while (im) (zk,.., zn)=(xj,.., xn); Else (zk,.., zn)=(xj,.., xm); } 4. Sắp xếp kiểu hòa nhập … b. Sắp xếp kiểu hòa nhập 2 đường trực tiếp (straight two-way merge) Nguyên tắc: Xuất phát từ nx: 1 khóa có thể xem là 1 mạch có độ dài bằng 1. Hòa nhập 2 mạch đó ta được 1 mạch mới có độ dài 2, lại hòa nhập mạch này → mạch độ dài 4,... Được mạch độ dài n → dãy được sắp. Ví dụ 42 21 74 11 56 59 93 32 89 78 Giải thuật void MPass(x, y, n, l) { i=1; while (i Sắp xếp ngoài Bài tập Sắp xếp dãy sau theo thứ tự giảm dần bằng thuật toán đơn giản: 79 32 40 21 56 67 92 5 18 89 Xét thuật toán tìm phần tử lớn thứ k của dãy S gồm n phần tử như sau: If n≤ 5 sắp xếp lại S và tìm phần tử lớn thứ k else n>5: Phần hoạch dãy S thành các dãy con có độ dài bằng 5 (n/5 & n mod 5) Sắp xếp các dãy có độ dài bằng 5 này Hình thành dãy M={m1, m2, m3,…m n/5 } là median của các dãy. Sử dụng thuật toán đệ quy tìm median của M, gọi m là phần tử này Phân hoạch S thành 3 tập S={L, E, G}, trong đó L là phần tử nhỏ hơn m, E là những ptử bằng m, G là những phần tử lớn hơn m Nếu k ≤ |L| thì áp dụng đệ quy để tìm phần tử lớn thứ k trong L. Nếu |L|< k ≤ |L| + |E| thì đó là m, ngược lại tìm phần tử lớn thứ k-(|L|+|E|) trong G. Câu hỏi: 1. Thời gian thực hiện thuật toán là bao nhiêu? 2. Chứng minh rằng nếu ta dùng thuật toán này để tìm phần tử pivot của thuật toán sắp xếp nhanh thì thời gian thực hiện của thuật toán quicksort là O(nlogn).