Trong bài trước, chúng ta đã làm quen với các thuật toán sắp xếp cơ bản có độ phức tạp . Tuy nhiên, khi đối mặt với lượng dữ liệu lớn hoặc yêu cầu về thời gian thực (Real-time) trong hệ thống nhúng, chúng ta cần những giải thuật mạnh mẽ hơn. Bài viết này sẽ giới thiệu về Quick Sort và Binary Search – hai “vũ khí” tối thượng để tối ưu hóa hiệu năng chương trình.
🎯 Mục tiêu học tập
- Hiểu và vận dụng tư duy Chia để trị (Divide and Conquer) trong Quick Sort.
- Biết các chiến lược chọn Pivot (điểm đánh dấu) và ảnh hưởng của nó tới tốc độ sắp xếp.
- Nắm vững điều kiện và quy trình của thuật toán Tìm kiếm nhị phân (Binary Search).
- So sánh được hiệu năng giữa Tìm kiếm tuyến tính () và Tìm kiếm nhị phân ().
1. Thuật toán sắp xếp nhanh (Quick Sort)
Quick Sort là một thuật toán sắp xếp dựa trên tư duy Chia để trị. Ý tưởng chính là chọn một phần tử làm “điểm chốt” (Pivot) và phân chia mảng thành hai mảng con: một bên chứa các phần tử nhỏ hơn Pivot và một bên chứa các phần tử lớn hơn Pivot.
Các cách chọn Pivot phổ biến:
- Luôn chọn phần tử đầu tiên của mảng.
- Luôn chọn phần tử cuối cùng của mảng (Phương pháp phổ biến và dễ cài đặt nhất).
- Chọn một phần tử ngẫu nhiên (Random).
- Chọn phần tử trung vị (Median element).
Độ phức tạp thuật toán:
- Trường hợp tốt/Trung bình: – Nhanh hơn rất nhiều so với Bubble Sort khi dữ liệu lớn.
- Trường hợp xấu nhất: (Xảy ra khi chọn Pivot rơi vào các phần tử cực đại hoặc cực tiểu của mảng đã sắp xếp).
2. Thuật toán tìm kiếm nhị phân (Binary Search)
Giả sử bạn có một mảng đã được sắp xếp. Thay vì kiểm tra từng phần tử từ đầu đến cuối (Tìm kiếm tuyến tính – ), thuật toán nhị phân sẽ “chặt đôi” phạm vi tìm kiếm sau mỗi bước, giúp tốc độ tìm kiếm đạt mức kinh ngạc .
Nguyên lý hoạt động:
Xét đoạn mảng arr[left...right], ta so sánh giá trị x cần tìm với phần tử ở giữa mid = (left + right) / 2:
- Nếu
arr[mid] == x: Tìm thấy, kết thúc chương trình.
- Nếu
arr[mid] < x: Giá trị cần tìm nằm ở nửa bên phải, ta chỉ tìm tiếp trên đoạn [mid + 1...right].
- Nếu
arr[mid] > x: Giá trị cần tìm nằm ở nửa bên trái, ta chỉ tìm tiếp trên đoạn [left...mid - 1].
Kết quả: Trong khi Tìm kiếm tuyến tính có thể mất 1000 bước cho mảng 1000 phần tử, thì Tìm kiếm nhị phân chỉ mất tối đa khoảng 10 bước!
🚀 Bài tập về nhà
Cho một mảng tĩnh gồm 20 bytes: uint8_t assignment3[20]. Hãy quản lý các phần tử này bằng Danh sách liên kết đơn (Sắp xếp theo giá trị tăng dần) với các yêu cầu khắt khe sau:
- Không được dùng cấp phát bộ nhớ động (malloc/calloc).
- Xây dựng Menu chương trình:
- Phím 1 – Nhập giá trị: Nhập vào vị trí (0-19) và giá trị (0-100). Kiểm tra lỗi trùng vị trí hoặc trùng giá trị.
- Phím 2 – Xóa giá trị: Tìm và xóa giá trị khỏi mảng, báo lỗi nếu không tồn tại.
- Phím 3 – In danh sách: Lựa chọn in mảng chưa sắp xếp hoặc in theo thứ tự đã sắp xếp (dùng liên kết đơn).
- Phím 4 – Kết thúc.
📝 Tóm tắt: Quick Sort và Binary Search là những kỹ thuật nền tảng để tối ưu hóa tài nguyên. Việc hiểu cách chúng hoạt động không chỉ giúp bạn viết code nhanh hơn mà còn giúp bạn tư duy giải quyết vấn đề một cách khoa học và hệ thống.
Gợi ý bài tiếp theo: Xử lý file định dạng Srec. Chúng ta sẽ học cách làm việc với định dạng file quan trọng nhất trong việc nạp firmware cho vi điều khiển!
Người thực hiện: Nguyễn Đình Tuấn
Email: tuannguyen.aiot@gmail.com | Website: aiots.vn