Bài giảng Hệ điều hành - Chương 8: Sắp thứ tự

Nội dung text: Bài giảng Hệ điều hành - Chương 8: Sắp thứ tự

1. 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 11 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
2. Merge sort Start Finish 26 33 35 29 19 12 22 12 19 22 26 29 33 35 Trộn 26 33 35 29 26 29 33 35 19 12 22 12 19 22 Trộn Trộn 26 33 26 33 35 29 29 35 19 12 12 19 22 Trộn Trộn Trộn 26 33 35 29 19 12 12 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
3. Đánh giá Merge sort Độ phức tạp: Có tối đa lgn mức Ở mỗi mức, cần trộn n phần tử Hạn chế: Danh sách liên tục: di chuyển các phần tử nhiều Nên dùng trong DSLK 13 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
4. Giải thuật Merge sort - DSLK Algorithm Merge_sort Input: danh sách cần sắp thứ tự Output: danh sách đã được sắp thứ tự 1. if (có ít nhất 2 phần tử) //Chia danh sách ra 2 phần bằng nhau: 1.1. second_half = divide_from (sub_list) //Sắp xếp riêng từng phần 1.2. Call Merge_sort với sub_list 1.3. Call Merge_sort với second_half //Trộn hai phần này với nhau 1.4. Call Merge với sub_list và second_half End Merge_sort 14 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
5. Giải thuật chia đôi DSLK Algorithm divide_from Input: danh sách cần chia đôi Output: hai danh sách dài gần bằng nhau 1. if (có ít nhất 1 phần tử) //Dùng một con trỏ di chuyển nhanh gấp đôi con trỏ còn lại 1.1. midpoint = sub_list 1.2. position là phần tử kế của midpoint 1.3. while (position is not NULL) 1.3.1. Di chuyển position đến phần tử kế 2 lần 1.3.2. Di chuyển midpoint đến phần tử kế 1.4. Cắt danh sách ra 2 phần tại vị trí này End divide_from 15 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
6. Giải thuật trộn hai DSLK có thứ tự Algorithm Merge Input: hai DSLK first và second có thứ tự Output: một DSLK có thứ tự 1. last_sorted là một node giả 2. while (first và second khác NULL) //Cả hai vẫn còn 2.1. if (dữ liệu của first nhỏ hơn dữ liệu của second) 2.1.1. Nối first vào sau last_sorted //Gỡ phần tử từ 2.1.2. last_sorted là first //DSLK 1 2.1.3. Chuyển first đến phần tử kế //gắn vào kết quả 2.2. else 2.2.1. Nối second vào sau last_sorted //Gỡ phần tử từ 2.2.2. last_sorted là second //DSLK 2 2.2.3. Chuyển second đến phần tử kế //gắn vào kết quả 2.3. if (danh sách first còn) 2.3.1. Nối first vào sau last_sorted 2.4. else 2.4.1. Nối second vào sau last_sorted End Merge 16 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
7. Quick sort Sort (26, 33, 35, 29, 19, 12, 22) Phân thành (19, 12, 22) và (33,35,29) với pivot=26 Sort (19, 12, 22) Phân thành (12) và (22) với pivot=19 Sort (12) Sort (22) Combine into (12, 19, 22) Sort (33, 35, 29) Phân thành (29) và (35) với pivot=33 Sort (29) Sort (35) Combine into (29, 33, 35) Combine into (12, 19, 22, 26, 29, 33, 35) 17 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
8. Giải thuật Quick sort Algorithm quick_sort Input: danh sách cần sắp xếp Output: danh sách đã được sắp xếp 1. if (có ít nhất 2 phần tử) //Phân hoạch danh sách thà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 danh sách ra 3 phần 1.2. Call quick_sort cho phần bên trái 1.3. Call quick_sort 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 18 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
9. Phân hoạch cho quick sort 19 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
10. Giải thuật phân hoạch Algorithm partition Input: danh sách cần phân hoạch từ low đến high Output: đã phân hoạch làm 3 phần, vị trí pivot được ghi nhận //Chọn phần tử tại vị trí giữa là phần tử pivot và chuyển về đầu 1. swap list[low], list[(low+high)/2] 2. pivot = list[low] 3. last_small = low 4. for index = low+1 to high //Quét qua tất cả các phần tử còn lại 4.1. if list[index] < pivot 4.1.1. last_small = last_small + 1 4.1.2. swap list[last_small], list[index] //Chuyển qua phần nhỏ hơn 5. swap list[last_small], list[low] //Trả phần tử pivot về lại chính giữa 6. Vị trí pivot chính là last_small End partition 20 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
11. Đá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) 21 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
12. Heap và Heap sort Heap (định nghĩa lại): Danh sách 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 Danh sách chưa chắc có thứ tự 0 1 2 3 4 5 6 7 8 Nửa sau của danh sách bất kỳ thỏa định nghĩa heap 22 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
13. Giải thuật Heap sort Algorithm heap_sort Input: danh sách cần sắp xếp có n phần tử Output: danh sách đã sắp thứ tự //Xây dựng heap ban đầu 1. Call build_heap //Lần lượt lấy phần tử đầu ra đem về cuối danh sách hiện tại //rồi xây dựng heap trở lại 2. for index = size-1 to 0 //index là vị trí cuối của phần còn lại 2.1. swap list[0], list[index] //Đổi phần tử lớn nhất về cuối //Xây dựng lại heap với số phần tử giảm đi 1 2.2. Call rebuild_heap index-1 End heap_sort 23 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
14. Ví dụ Heap sort (tt.) r f p d c b k current a y 0 1 2 3 4 5 6 7 8 r f p d c b k a y 24 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
15. Ví dụ Heap sort (tt.) p f k d c b a current r y 0 1 2 3 4 5 6 7 8 p f k d c b a r y 25 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
16. Giải thuật tái tạo lại heap Algorithm insert_heap Input: danh sách là heap trong khoảng từ low+1 đến high, current là giá trị cần thêm vào Output: danh sách 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, list[2k+1], list[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 insert_heap 26 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
17. Giải thuật xây dựng heap ban đầu Algorithm build_heap Input: danh sách bất kỳ cần biến thành heap Output: danh sách đã là heap //Nửa sau của 1 danh sách bất kỳ thỏa tính chất của heap //Ta tìm cách xây dựng heap ngược từ giữa về đầu 1. for low = size/2 downto 0 //Từ vị trí low+1 đến cuối danh sách đang là heap 1.1. current = list[low]; //Xây dựng lại heap trong khoảng [low, size-1] 1.2. Call insert_heap với current, low và size − 1 End build_heap 27 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự
18. Ví dụ xây dựng heap ban đầu 0 1 2 3 4 5 6 7 8 Bước 1 p c y d f b k a r 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 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 Đánh giá: 0 1 2 3 4 5 6 7 8 - Xấu nhất: Bước 4 p r y d f b k a c C = 2n lg n + O(n) 0 1 2 3 4 5 6 7 8 M = n lg n + O(n) y r p d f b k a c 28 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 8. Sắp thứ tự