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

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 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) 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 Ví dụ với đống lớn nhất (max-heap) Sau buildHeap() Sau deleteMax() đầu tiên Cài đặt sắp xếp vun đống 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) Ví dụ về trộn (merge) • 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) 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 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 27 38 13 2 1 24 26 15 13 2 27 38 1 24 15 26 27 38 2 13 1 15 24 26 2 13 27 38 1 2 13 15 24 26 27 38 Cài đặt sắp xếp trộn 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) 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 13 81 92 43 31 65 57 26 75 0 13 81 92 43 31 65 57 26 75 0 13 43 31 57 26 0 81 92 75 65 13 43 31 57 26 0 81 92 75 13 43 31 57 26 0 65 81 92 75 Chọn chốt Phân vùng Gọi đệ quy Gọi đệ quy Hợp nhất 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 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 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) • 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 chốt 8 1 4 9 0 3 5 2 7 6 i j chốt 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 Ví dụ thuật toán phân vùng 8 1 4 9 0 3 5 2 7 6 i j chốt 8 1 4 9 0 3 5 2 7 6 i j chốt 2 1 4 9 0 3 5 8 7 6 i j chốt dịch đổi chỗ 2 1 4 9 0 3 5 8 7 6 i j chốt dịch 2 1 4 5 0 3 9 8 7 6 i j chốt đổi chỗ 2 1 4 5 0 3 9 8 7 6 i j chốt dịch 2 1 4 5 0 3 6 8 7 9 i j chốt đổi chỗ S[i] và chốt i và j cắt chéo 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) Cài đặt sắp xếp nhanh Hàm chọn chốt Hàm sắp xếp nhanh Độ 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)