Trong bài viết này, mình sẽ cũng thực hiện những thuật toán sắp xếp thông dụng
1. Các thuật toán cơ bản (O(n²))
🔹 Insertion Sort
- Youtube: https://www.youtube.com/watch?v=8mJ-OhcfpYg
- Ý tưởng: Xây dựng mảng con đã sắp xếp bằng cách chèn từng phần tử vào đúng vị trí.
- Time: O(n²) (tốt nhất O(n) khi mảng gần sắp xếp).
- Space: O(1).
- Hiệu quả với mảng nhỏ hoặc gần có thứ tự.
void insertionSort(vector<int>& arr) { int temp = 0; int j; for(int i = 1; i < arr.size(); i++) { temp = arr[i]; j = i - 1; while(j >= 0 && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } }
🔹 Bubble Sort
- Ý tưởng: So sánh từng cặp liền kề, đổi chỗ nếu sai thứ tự. Lặp lại cho đến khi mảng được sắp xếp.
- Time: O(n²) (tốt nhất O(n) khi gần sắp xếp).
- Space: O(1).
- Đơn giản, nhưng chậm với n lớn.
🔹 Selection Sort
- Ý tưởng: Tìm phần tử nhỏ nhất, đặt vào đầu. Lặp lại với phần còn lại.
- Time: O(n²) trong mọi trường hợp.
- Space: O(1).
- Ít khi dùng thực tế vì kém hiệu quả.
2. Các thuật toán nâng cao (O(n log n))
🔹 Merge Sort
- Ý tưởng: Chia mảng thành 2 nửa, sắp xếp từng nửa, sau đó trộn (merge) lại.
- Time: O(n log n) trong mọi trường hợp.
- Space: O(n) (tốn thêm mảng phụ).
- Stable (giữ nguyên thứ tự phần tử bằng nhau).
🔹 Quick Sort
- Ý tưởng: Chọn pivot, chia mảng thành 2 phần (nhỏ hơn pivot và lớn hơn pivot), sắp xếp đệ quy.
- Time: Trung bình O(n log n), tệ nhất O(n²) (nếu pivot xấu).
- Space: O(log n) do stack đệ quy.
- Rất nhanh trong thực tế, thường dùng trong thư viện chuẩn (C++ std::sort).
🔹 Heap Sort
- Ý tưởng: Xây dựng cấu trúc heap, sau đó lấy max/min ra từng bước.
- Time: O(n log n) trong mọi trường hợp.
- Space: O(1).
- Không stable, nhưng tiết kiệm bộ nhớ.
3. Các thuật toán tuyến tính (O(n))
Chỉ áp dụng khi dữ liệu có giới hạn giá trị (ví dụ số nguyên trong khoảng nhỏ).
🔹 Counting Sort
- Ý tưởng: Đếm số lần xuất hiện của từng giá trị, rồi tái dựng mảng.
- Time: O(n + k) (k = giá trị lớn nhất).
- Space: O(k).
- Chỉ dùng cho dữ liệu nguyên, range nhỏ.
🔹 Radix Sort
- Ý tưởng: Sắp xếp theo từng chữ số (từ LSD hoặc MSD) bằng một thuật toán ổn định (thường Counting Sort).
- Time: O(n·d), d = số chữ số.
- Dùng cho số nguyên, chuỗi.
🔹 Bucket Sort
- Ý tưởng: Chia phần tử vào các "bucket" nhỏ, sắp xếp từng bucket (thường bằng InsertionSort), rồi gộp lại.
- Time: O(n + k), trung bình rất nhanh nếu dữ liệu phân bố đều.