Cấu trúc dữ liệu và giải thuật - Các thuật toán sắp xếp (phần 2)

Nội dung text: Cấu trúc dữ liệu và giải thuật - Các thuật toán sắp xếp (phần 2)

1. Các thuật toán sắp xếp (p2) (sorting algorithms) Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
2. Các thuật toán sắp xếp - phần 2 • Sắp xếp vun đống (heap sort) • Sắp xếp trộn (merge sort) • Sắp xếp nhanh (quick sort)
3. Sắp xếp vun đống (heap sort) • Đống nhỏ nhất (min-heap) − Xây dựng đống: O(N) − Thực hiện N phép deleteMin để lấy ra phần tử nhỏ nhất: O(N log N) − Độ phức tạp tổng thể: O(N log N) − Yêu cầu thêm một mảng nữa để lưu trữ các kết quả • Đống lớn nhất (max-heap): − Lưu trữ các phần tử bị xóa ở cuối vector đống
4. Ví dụ với đống lớn nhất (max-heap) Sau buildHeap() Sau deleteMax() đầu tiên
5. Cài đặt sắp xếp vun đống
6. Sắp xếp trộn (merge sort) • Ban đầu có N phần tử chưa sắp xếp • Chia N phần tử thành hai nửa • Sắp xếp đệ quy mỗi nửa dùng mergeSort − Trường hợp cơ sở: N = 1 (không cần sắp xếp) • Trộn (merge) hai nửa (đã được sắp xếp)
7. Ví dụ về trộn (merge) 1 15 24 26 2 13 27 38 1 15 24 26 2 13 27 38 1 1 15 24 26 2 13 27 38 1 2 1 15 24 26 2 13 27 38 1 2 13 • Có N bước • Mỗi bước có thể có một phép so sánh và có một phần tử được chèn vào mảng thứ ba mỗi bước mất thời gian hằng Tổng thời gian là O(N)
8. Ví dụ về sắp xếp trộn (merge sort) 1 24 26 15 13 2 27 38 1 24 26 15 13 2 27 38 1 24 26 15 13 2 27 38 1 24 26 15 13 2 27 38 1 24 15 26 2 13 27 38 1 15 24 26 2 13 27 38 1 2 13 15 24 26 27 38
9. Cài đặt sắp xếp trộn
10. Phân tích sắp xếp trộn • Gọi T(N) là độ phức tạp (N là số phần tử) • Ta có: − T(1) = 1 − T(N) = 2T(N/2) + N − T(N) = 4T(N/4) + 2N − T(N) = 8T(N/8) + 3N − − T(N) = 2kT(N/2k) + k*N • Chọn k = log N: − T(N) = N T(1) + N log N = O(N log N)
11. Sắp xếp nhanh (quick sort) • Cách tiếp cận chia để trị (tương tự sắp xếp trộn) • Cho mảng S: 1. Nếu |S| 1 thì kết thúc 2. Chọn một phần tử v S làm chốt (pivot) 3. Phân chia S – {v} (những phần tử còn lại trong S) thành hai nhóm: + S1 = { x | x S – {v} và x v } 4. Trả về { quicksort(S1), v, quicksort(S2) } • Các vấn đề cần xem xét: − Cách chọn chốt (bước 2) − Cách phân vùng (bước 3)
12. Ví dụ sắp xếp nhanh 81 43 31 57 75 13 92 65 26 0 Chọn chốt 81 43 31 57 75 13 92 65 26 0 Phân vùng 31 57 13 65 81 43 26 0 92 75 Gọi đệ quy Gọi đệ quy 0 13 26 31 43 57 75 81 92 Hợp nhất 0 13 26 31 43 57 65 75 81 92
13. Chọn chốt • Nên chọn chốt sao cho chia mảng thành hai phần đều nhau • Chốt lý tưởng là trung vị (median) (phần tử nằm chính giữa sau khi sắp xếp mảng) tính toán tốn kém! • Cách chọn ở đây là lấy trung vị của ba phần tử trái (left), phải (right) và chính giữa (center) của mảng
14. Ví dụ chọn chốt • Cho mảng S = { 6, 1, 4, 9, 0, 3, 5, 2, 7, 8 } − left = 0 và S[left] = 6 − right = 9 và S[right] = 8 − center = (left + right)/2 = 4 và S[center] = 0 • Chọn chốt: − chốt = trung vị của S[left], S[right] và S[center] − chốt = trung vị của 6, 8 và 0 − chốt = S[left] = 6
15. Thuật toán phân vùng • Đầu vào: S = { 6, 1, 4, 9, 0, 3, 5, 2, 7, 8 } • Xác định chốt (6) và đổi chỗ với phần tử cuối cùng (8) 8 1 4 9 0 3 5 2 7 6 chốt • Dùng hai chỉ số i và j : − i bắt đầu từ phần tử đầu tiên và dịch phải − j bắt đầu từ phần tử cuối cùng và dịch trái 8 1 4 9 0 3 5 2 7 6 i j chốt
16. Thuật toán phân vùng (tiếp) • Trong khi i < j : − Dịch i sang phải đến khi tìm thấy một số lớn hơn chốt − Dịch j sang trái đến khi tìm thấy một số nhỏ hơn chốt − Nếu i < j thì đổi chỗ S[i] và S[j] • Đổi chỗ S[i] và chốt
17. Ví dụ thuật toán phân vùng i j chốt 8 1 4 9 0 3 5 2 7 6 dịch i j chốt 8 1 4 9 0 3 5 2 7 6 đổi chỗ i j chốt 2 1 4 9 0 3 5 8 7 6 dịch i j chốt 2 1 4 9 0 3 5 8 7 6 đổi chỗ i j chốt 2 1 4 5 0 3 9 8 7 6 dịch j i chốt i và j 2 1 4 5 0 3 9 8 7 6 cắt chéo đổi chỗ S[i] 2 1 4 5 0 3 6 8 7 9 và chốt j i chốt
18. Xử lý các mảng nhỏ • Đối với các mảng nhỏ (ví dụ, N < 20): − Sắp xếp nhanh dùng đệ quy mất nhiều thời gian khi sắp xếp mảng nhỏ − Sắp xếp chèn nhanh hơn sắp xếp nhanh • Sẽ cài đặt theo kiểu lai ghép: − Ban đầu dùng sắp xếp nhanh − Sau chuyển sang sắp xếp chèn khi kích thước mảng trở nên nhỏ (ví dụ, N < 20)
19. Cài đặt sắp xếp nhanh
20. Hàm chọn chốt
21. Hàm sắp xếp nhanh
22. Độ phức tạp của sắp xếp nhanh (xem chứng minh trong sách) • Trường hợp trung bình: O(N log N) • Trường hợp tồi nhất (chốt là phần tử nhỏ nhất): O(N2)