07. Sorting Algorithms (Thuật toán sắp xếp)
🎯 Mục tiêu học tập
- Hiểu các thuật toán sắp xếp cơ bản
- Phân tích độ phức tạp time & space
- So sánh ưu nhược điểm từng thuật toán
- Chọn thuật toán phù hợp cho từng trường hợp
📊 Tổng quan các thuật toán
| Thuật toán | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | ✅ |
🔥 Thuật toán cơ bản (O(n²))
1. Bubble Sort
Ý tưởng: So sánh cặp kề nhau, đẩy phần tử lớn về cuối
// Mỗi lần duyệt, phần tử lớn nhất "nổi" lên cuối
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr, j, j+1);
}
}
}
2. Selection Sort
Ý tưởng: Tìm min trong phần chưa sắp xếp, đưa về đầu
// Mỗi lần tìm min trong [i...n-1], đặt ở vị trí i
for (int i = 0; i < n-1; i++) {
int minIdx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
swap(arr, i, minIdx);
}
3. Insertion Sort
Ý tưởng: Chèn từng phần tử vào vị trí đúng trong phần đã sắp xếp
// Giống như sắp xếp bài trong tay
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
⚡ Thuật toán hiệu quả (O(n log n))
1. Merge Sort
Ý tưởng: Chia để trị - chia nhỏ rồi gộp lại có thứ tự
// Divide and Conquer
// 1. Chia array thành 2 nửa
// 2. Recursive sort từng nửa
// 3. Merge 2 nửa đã sort
2. Quick Sort
Ý tưởng: Chọn pivot, partition thành 2 phần < pivot và > pivot
// 1. Chọn pivot
// 2. Partition: < pivot | pivot | > pivot
// 3. Recursive sort 2 phần
3. Heap Sort
Ý tưởng: Dùng heap để lấy max/min liên tục
// 1. Build max heap
// 2. Lần lượt lấy root (max) đặt ở cuối
// 3. Heapify phần còn lại
🎨 Thuật toán đặc biệt
1. Counting Sort (Non-comparison)
Điều kiện: Biết range của dữ liệu (0 ≤ arr[i] ≤ k)
// 1. Đếm frequency của từng số
// 2. Tính cumulative count
// 3. Đặt vào đúng vị trí
2. Radix Sort
Ý tưởng: Sort theo từng digit (LSD hoặc MSD)
// Sort từ digit thấp nhất đến cao nhất
// Dùng counting sort cho từng digit
3. Bucket Sort
Ý tưởng: Chia vào các bucket, sort từng bucket
// 1. Chia input vào n buckets
// 2. Sort từng bucket
// 3. Concatenate buckets
🔍 Khi nào dùng thuật toán nào?
Bubble Sort:
- ❌ Hầu như không dùng trong thực tế
- ✅ Chỉ dùng để học thuật toán
Selection Sort:
- ✅ Array nhỏ, memory hạn chế
- ❌ Không stable
Insertion Sort:
- ✅ Array nhỏ hoặc gần như đã sorted
- ✅ Online algorithm (sort khi nhận data)
- ✅ Adaptive và stable
Merge Sort:
- ✅ Cần stable sort
- ✅ Worst case performance quan trọng
- ❌ Memory overhead O(n)
Quick Sort:
- ✅ Average case tốt nhất
- ✅ In-place sorting
- ❌ Worst case O(n²)
Heap Sort:
- ✅ Worst case O(n log n) guaranteed
- ✅ In-place
- ❌ Không stable, cache performance kém
📋 Bài tập thực hành
Cơ bản:
- Implement tất cả sorting algorithms
- Count inversions trong array
- Sort array of 0s, 1s, 2s
- Find Kth largest element
Nâng cao:
- External sorting (file quá lớn)
- Sort linked list
- Merge K sorted arrays
- Sort colors (Dutch flag problem)
💡 Tips tối ưu
1. Hybrid Approaches:
- Java Arrays.sort(): Quick Sort + Insertion Sort
- Python Timsort: Merge Sort + Insertion Sort
2. Stability matters:
- Nếu cần giữ thứ tự relative: Merge Sort
- Không cần stable: Quick Sort, Heap Sort
3. Memory constraints:
- Limited memory: Quick Sort, Heap Sort
- Memory plenty: Merge Sort
🚀 Chuẩn bị code
mkdir 07-sorting
# Files:
# - BasicSorts.java (Bubble, Selection, Insertion)
# - AdvancedSorts.java (Merge, Quick, Heap)
# - SpecialSorts.java (Counting, Radix, Bucket)
# - SortingProblems.java (Practice problems)