Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán sắp xếp - Nguyễn Mạnh Hiển (P2)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Các thuật toán sắp xếp (P2)" có cấu trúc gồm 3 phần cung cấp cho người học các kiến thức: Sắp xếp vun đống (heap sort), sắp xếp trộn (merge sort), sắp xếp nhanh (quick sort). Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán sắp xếp - Nguyễn Mạnh Hiển (P2)Các thuật toán sắp xếp (p2)(sorting algorithms)Nguyễn Mạnh HiểnKhoa Công nghệ thông tinhiennm@tlu.edu.vnCá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)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 đốngVí dụ với đống lớn nhất (max-heap) Sau buildHeap() Sau deleteMax() đầu tiênCài đặt sắp xếp vun đốngSắ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)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)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 38Cài đặt sắp xếp trộnPhâ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)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 } + S2 = { 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)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 65 26 0 92 Phân vùng 13 31 57 81 26 0 65 92 75 43 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 92Chọ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ảngVí 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] = 6Thuậ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ốtThuậ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ốtVí 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 ...