1. Sắp xếp Nổi bọt (Bubble Sort)
Ý tưởng thuật toán
- Duyệt qua danh sách, so sánh các cặp phần tử kề nhau.
- Nếu phần tử trước lớn hơn phần tử sau, thực hiện hoán đổi vị trí.
- Sau mỗi lượt duyệt, phần tử lớn nhất sẽ "nổi" về cuối dãy, vị trí đó được xem là đã sắp xếp.
| Lượt duyệt | Bước so sánh | So sánh (a[j], a[j+1]) | Trạng thái mảng |
|---|---|---|---|
| Lượt 1 Đẩy số 4 về cuối |
1.1 | So sánh (4, 2) → 4 > 2 (Đổi) | [2, 4, 1, 3] |
| 1.2 | So sánh (4, 1) → 4 > 1 (Đổi) | [2, 1, 4, 3] | |
| 1.3 | So sánh (4, 3) → 4 > 3 (Đổi) | [2, 1, 3, 4] | |
| Lượt 2 Đẩy số 3 về cuối |
2.1 | So sánh (2, 1) → 2 > 1 (Đổi) | [1, 2, 3, 4] |
| 2.2 | So sánh (2, 3) → 2 < 3 (Giữ) | [1, 2, 3, 4] | |
| Lượt 3 | 3.1 | So sánh (1, 2) → 1 < 2 (Giữ) | Xong! [1, 2, 3, 4] |
2. Sắp xếp Lựa chọn (Selection Sort)
Ý tưởng thuật toán
- Chia danh sách thành hai phần: phần đã sắp xếp và phần chưa sắp xếp.
- Trong phần chưa sắp xếp, tìm phần tử có giá trị nhỏ nhất (Min).
- Hoán đổi phần tử nhỏ nhất đó với phần tử đầu tiên của phần chưa sắp xếp.
| Bước | Phần chưa sắp xếp | Giá trị nhỏ nhất (Min) | Thực hiện Hoán đổi |
|---|---|---|---|
| Bước 1 | [4, 2, 1, 3] | 1 (vị trí số 2) | Đổi 4 và 1 → [1, 2, 4, 3] |
| Bước 2 | 1 | [2, 4, 3] | 2 (vị trí số 1) | Giữ nguyên → [1, 2, 4, 3] |
| Bước 3 | 1, 2 | [4, 3] | 3 (vị trí số 3) | Đổi 4 và 3 → [1, 2, 3, 4] |
| Bước 4 | 1, 2, 3 | [4] | 4 | Kết thúc [1, 2, 3, 4] |
3. Sắp xếp Chèn (Insertion Sort)
Ý tưởng thuật toán
- Lấy lần lượt các phần tử từ phần chưa sắp xếp làm "Key".
- So sánh Key với các phần tử thuộc phần đã sắp xếp (bên trái nó).
- Dịch chuyển các phần tử lớn hơn Key sang phải để tạo khoảng trống và chèn Key vào đúng vị trí.
| Lượt chèn | Khóa (Key) | So sánh & Dịch chuyển | Mảng sau khi chèn |
|---|---|---|---|
| Lượt 1 | 2 | 2 < 4: Đẩy 4 sang phải | [2, 4, 1, 3] |
| Lượt 2 | 1 | 1 < 4: Đẩy 4 sang phải | [2, _, 4, 3] |
| 1 < 2: Đẩy 2 sang phải | [1, 2, 4, 3] | ||
| Lượt 3 | 3 | 3 < 4: Đẩy 4 sang phải. 3 > 2: Dừng. | [1, 2, 3, 4] |
Bảng tổng kết Độ phức tạp
| Thuật toán | Trường hợp tệ nhất (Worst Case) | Trường hợp tốt nhất (Best Case) | Lý do kỹ thuật |
|---|---|---|---|
| Bubble Sort | O(n²) | O |
Cần 2 vòng lặp lồng nhau ($n \times n$). Nếu mảng đã xếp xong, chỉ cần 1 lần duyệt kiểm tra để thoát. |
| Selection Sort | O(n²) | O(n²) | Luôn quét toàn bộ phần chưa xếp để tìm giá trị nhỏ nhất, không phụ thuộc vào trạng thái dữ liệu. |
| Insertion Sort | O(n²) | O |
Tệ nhất khi mảng ngược hoàn toàn (phải dịch chuyển $n^2$ lần). Tốt nhất khi mảng đã xếp sẵn. |
