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)

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

69
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ể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) 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 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 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 92
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) 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
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 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 j chốt đổi chỗ 2 1 4 9 0 3 5 8 7 6 i j chốt dịch 2 1 4 9 0 3 5 8 7 6 i j chốt đổi chỗ 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
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