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 31 57 75 43 0 13 92 65 26
Chọn chốt
57 75 81 43 31 13 65 26 0 92
Phân vùng
31 57 13 81 65 26 0 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
j chốt
j
chốt
dịch
j
chốt
đổi chỗ
i 8 1 4 9 0 3 5 2 7 6 i 8 1 4 9 0 3 5 2 7 6 i 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
j
i
chốt
dịch
i và j cắt chéo
2 1 4 5 0 3 9 8 7 6
2 1 4 5 0 3 6 8 7 9
đổi chỗ S[i] 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
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)
