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)
lượt xem 3
download
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.
Bình luận(0) Đăng nhập để gửi bình luận!
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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 174 | 17
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p | 162 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p | 77 | 9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p | 116 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 78 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p | 77 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 57 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 157 | 6
-
Bài giảng Cấu trúc dữ liệu - Chương 3: Cấu trúc cây
65 p | 58 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AA - Bùi Tiến Lên
30 p | 35 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 105 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây - Bùi Tiến Lên
68 p | 40 | 4
-
Bài giảng Cấu trúc dữ liệu: Chương 1 - ThS. Thiều Quang Trung (2018)
44 p | 43 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên
38 p | 46 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Quang Thạch
24 p | 58 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 68 | 3
-
Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu
17 p | 50 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn