Giao diện
So sánh các thuật toán sắp xếp
🎯 Mục tiêu
Luyện tập cài đặt Bubble Sort, Merge Sort, phân tích độ phức tạp thời gian và so sánh hiệu năng thực tế giữa các thuật toán sắp xếp.
Mô tả bài tập
Sắp xếp là bài toán nền tảng trong khoa học máy tính. Trong bài tập này, bạn sẽ cài đặt hai thuật toán sắp xếp phổ biến, đo lường hiệu năng và rút ra kết luận về khi nào nên dùng thuật toán nào.
Yêu cầu
Bài 1: Cài đặt Bubble Sort
Cài đặt thuật toán Bubble Sort với tối ưu cờ hiệu (early termination) khi mảng đã được sắp xếp.
python
def bubble_sort(arr: list[int]) -> list[int]:
"""Sắp xếp mảng bằng Bubble Sort với tối ưu early termination."""
# TODO: Cài đặt thuật toán
pass
# Test cases
assert bubble_sort([5, 3, 8, 1, 2]) == [1, 2, 3, 5, 8]
assert bubble_sort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5]
assert bubble_sort([]) == []Bài 2: Cài đặt Merge Sort
Cài đặt thuật toán Merge Sort sử dụng đệ quy chia để trị.
python
def merge_sort(arr: list[int]) -> list[int]:
"""Sắp xếp mảng bằng Merge Sort (chia để trị)."""
# TODO: Cài đặt thuật toán
pass
# Test cases
assert merge_sort([38, 27, 43, 3, 9, 82, 10]) == [3, 9, 10, 27, 38, 43, 82]
assert merge_sort([1]) == [1]Bài 3: Phân tích và so sánh hiệu năng
Viết hàm đo thời gian thực thi của cả hai thuật toán trên các mảng có kích thước khác nhau (100, 1000, 5000 phần tử). Trả về bảng so sánh.
python
import time, random
def benchmark(sort_func, sizes: list[int], trials: int = 3) -> dict:
"""Đo thời gian trung bình của sort_func trên các kích thước mảng."""
# TODO: Cài đặt hàm benchmark
pass
# So sánh kết quả
sizes = [100, 1000, 5000]
print("Bubble Sort:", benchmark(bubble_sort, sizes))
print("Merge Sort:", benchmark(merge_sort, sizes))Bài 4: Nhận xét kết quả
Trả lời các câu hỏi sau dựa trên kết quả benchmark:
- Tại sao Merge Sort nhanh hơn đáng kể khi n lớn?
- Trong trường hợp nào Bubble Sort có thể nhanh hơn Merge Sort?
- Giải thích tại sao Bubble Sort tối ưu có O(n) best-case.
Phân tích độ phức tạp
| Bài | Time | Space |
|---|---|---|
| 1 - Bubble Sort | O(n²) worst/avg, O(n) best | O(1) |
| 2 - Merge Sort | O(n log n) | O(n) |
| 3 - Benchmark | O(trials × n²) hoặc O(trials × n log n) | O(n) |
Gợi ý
Gợi ý Bài 1
Dùng biến swapped để kiểm tra xem vòng lặp trong có thực hiện hoán đổi nào không. Nếu không có hoán đổi, mảng đã sắp xếp → dừng sớm.
Gợi ý Bài 2
Chia mảng thành hai nửa, gọi đệ quy sắp xếp từng nửa, sau đó dùng hàm merge() riêng để trộn hai mảng đã sắp xếp.
Gợi ý Bài 3
Dùng time.perf_counter() thay vì time.time() để đo chính xác hơn. Tạo mảng ngẫu nhiên bằng random.sample(range(n*10), n).
Lời giải tham khảo
Xem lời giải
python
def bubble_sort(arr: list[int]) -> list[int]:
result = arr[:]
n = len(result)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if result[j] > result[j + 1]:
result[j], result[j + 1] = result[j + 1], result[j]
swapped = True
if not swapped:
break
return result
def merge_sort(arr: list[int]) -> list[int]:
if len(arr) <= 1:
return arr[:]
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left: list[int], right: list[int]) -> list[int]:
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result