Insertion Sort là một trong những thuật toán sắp xếp trực quan. Trong bài viết này, chúng ta sẽ khám phá không chỉ cách mà nó hoạt động, mà còn làm thế nào để trực quan hoá nó thông qua hoạt hình sử dụng CustomPainter và AnimationController.
1. Insertion Sort là gì?
Insertion Sort là một thuật toán sắp xếp đơn giản, nó hoạt dộng dựa trên việc xây dựng một mảng đã được sắp xếp 1 phần tử tại thời điểm. Về mặt khái niệm thì nó tương tự như việc chúng ta sắp xếp các quân bài trên tay – bạn chọn 1 lá bài tại một thời điểm và chèn nó vào ví trí đúng giữa các lá bài đã được sắp xếp.
Ý tưởng cốt lõi
- Bắt đầu với phần tử thứ 2 của mảng
- So sánh nó với tất cả phần từ trước
- Dịch chuyển các phần tử lớn hơn sang bên phải để tạo chổ trống
- Chèn phần tử hiện tại vào đúng vị trí
- Lăp lại cho đến khi tất cả phần tử trong mảng đã được sắp xếp
Ví dụ: cho mảng sau [5, 3, 4, 1, 2]
- So sánh 3 với 5 → dịch chuyển 5 → chèn 3 vào phái trước → [3, 5, 4, 1, 2]
- So sánh 4 với 5 → dịch chuyển 5 → so sánh 4 với 3 → chèn 4 → [3, 4, 5, 1, 2]
- So sánh 1 với 5, 4, 3 → dịch chuyển tất cả → chèn 1 → [1, 3, 4, 5, 2]
- Tiếp tục với 2 → [1, 2, 3, 4, 5]
2. Ví dụ Insertion Sort từng bước một
Hãy cùng nhau đi qua Insertion Sort trên mảng này:
Khởi tạo mảng: [6, 4, 2, 8, 5]
Step 1: i = 1 (current = 4)
So sánh với 6 → dịch chuyển 6
Chèn 4 tại index 0
→ [4, 6, 2, 8, 5]
Step 2: i = 2 (current = 2)
So sánh với 6 → dịch chuyển
So sánh với 4 → dịch chuyển
Chèn 2 tại index 0
→ [2, 4, 6, 8, 5]
Step 3: i = 3 (current = 8)
8 > 6 → không dịch chuyển
→ [2, 4, 6, 8, 5]
Step 4: i = 4 (current = 5)
So sánh với 8 → dịch chuyển
So sánh với 6 → dịch chuyển
Chèn 5 tại index 2
→ [2, 4, 5, 6, 8]
3. Performance
| Scenario | Time Complexity |
|---|---|
| Best Case (sorted) | O(n) |
| Average Case | O(n²) |
| Worst Case (reversed) | O(n²) |
| Space | O(1) — in-place |
| Stability | Yes |
Mặc dù độ phức tạp giải thuật O(n²) cho worst-case, nhưng Insertion Sort có thể vượt trội hơn những giải thuật phức tạp hơn trên một tập dữ liệu nhỏ hoặc gần như đã sắp xếp.
4. Mathematical Recursion Model
Không giống như các thuật toán sắp xếp đệ quy như QuickSort hay MergeSort, Insertion Sort là một thuật toán lặp và hoạt động với vòng lặp lồng nhau.
Vòng lặp bên trong thực hiện tối đa i phép so sánh/di chuyển cho mỗi i từ 1 đến n – 1: T(n)=O(1+2+3+…+n−1)=O(n2)T(n) = O(1 + 2 + 3 + … + n-1) = O(n²) T(n)=O(1+2+3+…+n−1)=O(n2)
Trong tường hợp tốt nhất (khi mảng đã được sắp xếp rồi), không cần di chuyển:
T(n)=O(n)T(n) = O(n) T(n)=O(n)
5. Flutter Implementation Highlights
Hãy xem cách trực quan hoá Insertion Sort trong Flutter bằng các chuyển động
Cấu trúc dữ liệu
class SortStep {
final List<int> arraySnapshot;
final int currentIndex; // the key being inserted
final int shiftIndex; // index of element being shifted
SortStep(
this.arraySnapshot,
this.currentIndex,
this.shiftIndex
);
}
List<int> _array;
List<SortStep> _steps; // Record of visual steps for animation
Insertion Sort Logic
Future<void> _insertionSort() async {
for (int i = 1; i < _array.length; i++) {
int key = _array[i];
int j = i - 1;
while (j >= 0 && _array[j] > key) {
_swap(j + 1, j);
_recordStep(j + 1, j);
j--;
}
_array[j + 1] = key;
_recordInsert(j + 1, key);
}
}void _recordStep(int current, int shifting) {
_steps.add(SortStep(List.from(_array), current, shifting));
}
SortStepđóng vai trò là giữ các index và các loại phép toán (swap, insert, compare, etc.).
Painting State
Các màu sắc cho animation:
- Normal bar: xanh dương
- Current key: đỏ
- Comparing: vàng
- Shifting: xanh lá
- Inserted: tím
6. Animation cho Insertion Sort trong Flutter
Chuyển động của các cột được xử lý bằng cách lăp qua các _steps sử dụng Timer.periodic:
Timer.periodic(Duration(milliseconds: 250), (timer) {
if (_currentStepIndex < _steps.length) {
setState(() {
_applyStep(_steps[_currentStepIndex++]);
});
} else {
timer.cancel();
}
});
Mỗi bước cập nhật lại một trang thái trực quan – chẳng hạn như dịch chuyển một cột hoặc thay đổi màu. Các cột được vẽ lên bằng CustomPainter trong đó chiều cao đại diện cho giá trị (mỗi cột có một chiều cao – đó là giá trị chúng ta cần sắp xếp)
7. Insertion Sort với những thuật toán khác
| Algorithm | Avg Time | Space | Stable |
|---|---|---|---|
| Insertion Sort | O(n²) | O(1) | Yes |
| QuickSort | O(n log n) | O(log n) | No |
| MergeSort | O(n log n) | O(n) | Yes |
| Bubble Sort | O(n²) | O(1) | Yes |
Use Insertion Sort when:
- Dataset is small (e.g., n < 50)
- Data is nearly sorted
- Stability is required
- Simplicity matters more than speed
8. Tổng kết
Insertion Sort dễ cho việc cài đặt và tốt cho tập dữ liệu nhỏ hoặc gần như đã sắp xếp. Trong khi nó không hiệu quả cho một tập dữ liệu lớn, nó được phục vụ như một công cụ mạnh mẽ cho việc giảng dạy và đóng một vai trò hỗ trợ cho thuật toán lai như TimSort và IntroSort.
Visualizing it in Flutter makes the learning process engaging and insightful. Watching each insertion unfold gives students and developers a tangible grasp of how the algorithm works.
Việc trực quan hoá nó trong Flutter làm cho quá trình học trở nên hấp dẫn và sâu sắc. Việc theo dõi mỗi bước chèn diễn ra giúp cho sinh viên và lập trình viên có được cái nhìn trực quan về cách nó hoạt động.
Up Next: Phân tích và trực quan hoá Selection Sort
Tiếp theo, chúng ta sẽ tìm hiểu về Selection Sort – một thuật toán ít ổn định hơn nhưng thú vị, luôn tìm ra phần tử nhỏ nhất và xây dựng danh sách từ đầu đến cuối
