Trong lập trình hệ thống, việc sắp xếp dữ liệu không chỉ đơn thuần là đưa chúng về đúng thứ tự mà còn là bài toán về tối ưu hóa bộ nhớ và thời gian thực thi. Bài viết hôm nay sẽ hướng dẫn bạn chi tiết về 3 thuật toán sắp xếp “vỡ lòng” nhưng cực kỳ quan trọng trong khoa học máy tính: Sắp xếp nổi bọt, Sắp xếp chọn và Sắp xếp chèn.
🎯 Mục tiêu học tập
- Hiểu nguyên lý hoạt động của thuật toán Nổi bọt (Bubble Sort), Chọn (Selection Sort) và Chèn (Insertion Sort).
- Biết cách cài đặt các thuật toán này bằng ngôn ngữ C.
- Phân tích được độ phức tạp thời gian () của từng giải thuật.
- Đánh giá ưu và nhược điểm để áp dụng vào các bài toán thực tế trên hệ thống nhúng.
1. Thuật toán sắp xếp nổi bọt (Bubble Sort)
a) Định nghĩa
Sắp xếp nổi bọt là phương pháp so sánh các cặp phần tử kề nhau. Nếu phần tử đứng trước lớn hơn phần tử đứng sau (trong trường hợp sắp xếp tăng dần), chúng ta sẽ đổi chỗ chúng. Quá trình này được lặp lại cho đến khi phần tử lớn nhất “nổi” về cuối dãy (hoặc phần tử nhỏ nhất nổi lên đầu dãy tùy theo chiều duyệt).
b) Minh họa thuật toán
- Bước 1: Bắt đầu từ chỉ số
i = 0.
- Bước 2: Duyệt từ cuối dãy ngược về vị trí
i. Nếu a[j] < a[j-1] thì thực hiện đổi chỗ (Swap).
- Bước 3: Tăng
i lên 1 và lặp lại cho đến khi duyệt hết dãy.
c) Cài đặt chương trình C
#include
// Hàm swap dùng để đổi vị trí hai phần tử
void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}
// Hàm sắp xếp nổi bọt
void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { // Nếu phần tử trước lớn hơn thì đổi chỗ
swap(&arr[j], &arr[j + 1]);
}
}
}
}
void printArr(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {90, 5, 3, 1, 8, 7, 2, 4, 10};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
printf("Sorted array: ");
printArr(arr, size);
return 0;
}
d) Đánh giá thuật toán
- Độ phức tạp: .
- Ưu điểm: Code ngắn gọn, cực kỳ dễ hiểu và dễ nhớ.
- Nhược điểm: Hiệu suất rất thấp, không phù hợp với tập dữ liệu lớn.
2. Thuật toán sắp xếp chọn (Selection Sort)
a) Ý tưởng
Thuật toán chia mảng thành hai phần: phần đã sắp xếp và phần chưa sắp xếp. Ở mỗi bước, nó tìm phần tử nhỏ nhất trong phần chưa sắp xếp và hoán đổi nó với phần tử đầu tiên của phần chưa sắp xếp đó.
- Thiết lập giá trị nhỏ nhất (
min) tại vị trí đầu tiên của list chưa sắp xếp.
- Duyệt mảng để tìm giá trị thực sự nhỏ nhất.
- Đổi chỗ giá trị nhỏ nhất đó với vị trí
min ban đầu.
- Độ phức tạp: trong mọi trường hợp.
3. Thuật toán sắp xếp chèn (Insertion Sort)
a) Ý tưởng
Giống như cách chúng ta sắp xếp các lá bài trên tay. Thuật toán duyệt từng phần tử và “chèn” nó vào đúng vị trí trong dãy con đã được sắp xếp phía trước nó.
- Coi phần tử đầu tiên là dãy đã sắp xếp.
- Lấy phần tử tiếp theo, so sánh ngược lại với dãy đã sắp xếp để tìm vị trí thích hợp và chèn vào.
- Độ phức tạp:
- Trường hợp tốt (mảng đã sắp xếp): .
- Trung bình/Xấu: .
📝 Tóm tắt: Bubble, Selection và Insertion Sort là 3 thuật toán nền tảng. Dù có độ phức tạp trung bình là – không thực sự tối ưu cho dữ liệu lớn – nhưng chúng lại rất hiệu quả cho các mảng nhỏ và dễ triển khai trên các hệ thống nhúng có giới hạn về tài nguyên mã nguồn.
Người thực hiện: Nguyễn Đình Tuấn
Email: tuannguyen.aiot@gmail.com | Website: aiots.vn