Chuyên đề thuật toán cơ bản

🧩 Sắp xếp mảng: Selection Sort, Insertion Sort, Bubble Sort

Bài học này giúp học sinh hiểu vì sao cần sắp xếp, cách cài đặt ba thuật toán cơ bản, phân biệt khi nào nên tự cài đặt và khi nào nên dùng sort có sẵn trong bài thi.

3 thuật toánSelection / Insertion / Bubble

O(n²)Độ phức tạp cơ bản

Mô phỏngChạy từng bước trực quan

Bài tậpPhân loại rõ mức độ

Mục tiêu Vì sao sắp xếp? So sánh Mô phỏng Code mẫu Lỗi hay nhầm Bài tập

Mục tiêu bài học

Học xong cần làm được

Biết cách cài đặt Selection Sort, Insertion Sort, Bubble Sort.
Hiểu vì sao có nhiều cách sắp xếp khác nhau.
So sánh được hiệu quả giữa các thuật toán sắp xếp cơ bản.
Biết khi nào nên dùng sort có sẵn thay vì tự viết.

Ví dụ đời sống

Xếp học sinh theo điểm từ thấp đến cao.
Xếp danh sách sản phẩm theo giá.
Xếp thời gian hoàn thành bài thi.
Xếp số báo danh / mã học sinh để tìm kiếm nhanh hơn.

1. Vì sao phải sắp xếp?

Sắp xếp là thao tác đưa các phần tử về một thứ tự nhất định, thường là tăng dần hoặc giảm dần. Sau khi sắp xếp, nhiều bài toán trở nên dễ hơn: tìm kiếm nhị phân, tìm cặp số, thống kê, xếp hạng.

Hình dung: Nếu một lớp có 45 điểm kiểm tra lộn xộn, giáo viên muốn biết bạn nào thấp nhất, cao nhất, hoặc xếp hạng theo điểm. Sắp xếp giúp danh sách trở nên có trật tự.

Tăng dần

Ví dụ: 1 2 3 5 8

Giảm dần

Ví dụ: 8 5 3 2 1

Theo tiêu chí

Ví dụ: sắp xếp học sinh theo điểm, nếu bằng điểm thì theo tên.

2. So sánh các thuật toán sắp xếp cơ bản

Thuật toán	Ý tưởng ngắn gọn	Dấu hiệu nhận biết	Độ phức tạp	Dễ nhầm
Selection Sort	Ở mỗi vị trí `i`, tìm phần tử nhỏ nhất trong đoạn còn lại rồi đổi lên.	Luôn có biến `min_pos` hoặc `min_idx`.	O(n²)	Nhầm với Bubble Sort vì cũng dùng 2 vòng lặp.
Insertion Sort	Lấy từng phần tử và chèn vào đúng vị trí trong đoạn đã sắp xếp.	Có biến `key`, dịch các phần tử lớn hơn sang phải.	O(n²)	Quên gán lại `a[j + 1] = key`.
Bubble Sort	So sánh từng cặp kề nhau, đổi chỗ nếu sai thứ tự.	Dùng `a[j]` và `a[j+1]`; phần tử lớn dần “nổi” về cuối.	O(n²)	Sai giới hạn `j < n - i - 1`.
sort có sẵn	Hàm thư viện đã tối ưu.	C++: `sort(a.begin(), a.end())`; Python: `a.sort()`.	thường O(n log n)	Trong bài thi thật, nên dùng nếu đề không yêu cầu tự cài.

Ghi nhớ cho học sinh mới học: Ba thuật toán cơ bản giúp hiểu bản chất. Nhưng khi làm bài thi yêu cầu xử lý dữ liệu lớn, nếu đề không bắt tự cài đặt, nên dùng sort có sẵn.

3. Mô phỏng từng bước

Chọn thuật toán Mảng ví dụ

Nhật ký thuật toán

Nhấn “Nạp mảng”, sau đó bấm “Bước tiếp”.

Cách quan sát: Cột màu vàng/cam là đang so sánh, cột đỏ là đang đổi/chèn, cột xanh là phần đã gần hoàn tất.

4. Code mẫu rõ ràng

Mỗi thuật toán có code C++ và Python riêng. Các tab dưới đây dùng JavaScript thuần, không phụ thuộc Bootstrap JS.

4.1. Bubble Sort

Ý tưởng: So sánh cặp kề nhau a[j] và a[j+1]. Nếu sai thứ tự thì đổi chỗ.

#include 
using namespace std;

int main() {
    int n;
    cin >> n;
    vector a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        }
    }

    for (int x : a) cout << x << ' ';
    return 0;
}

n = int(input())
a = list(map(int, input().split()))

for i in range(n - 1):
    for j in range(n - i - 1):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]

print(*a)

4.2. Selection Sort

Ý tưởng: Ở vị trí i, tìm phần tử nhỏ nhất từ i đến cuối rồi đưa về vị trí i.

#include 
using namespace std;

int main() {
    int n;
    cin >> n;
    vector a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n; i++) {
        int min_pos = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min_pos]) min_pos = j;
        }
        swap(a[i], a[min_pos]);
    }

    for (int x : a) cout << x << ' ';
    return 0;
}

n = int(input())
a = list(map(int, input().split()))

for i in range(n):
    min_pos = i
    for j in range(i + 1, n):
        if a[j] < a[min_pos]:
            min_pos = j
    a[i], a[min_pos] = a[min_pos], a[i]

print(*a)

4.3. Insertion Sort

Ý tưởng: Giống như xếp bài trên tay: lấy lá bài mới rồi chèn vào vị trí đúng trong phần đã xếp.

#include 
using namespace std;

int main() {
    int n;
    cin >> n;
    vector a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }

    for (int x : a) cout << x << ' ';
    return 0;
}

n = int(input())
a = list(map(int, input().split()))

for i in range(1, n):
    key = a[i]
    j = i - 1
    while j >= 0 and a[j] > key:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = key

print(*a)

4.4. Khi làm bài thi: dùng sort có sẵn

Nếu đề bài chỉ yêu cầu “sắp xếp mảng” mà không bắt cài thuật toán cụ thể, dùng hàm có sẵn thường an toàn và nhanh hơn.

#include 
using namespace std;

int main() {
    int n;
    cin >> n;
    vector a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end());                  // tăng dần
    // sort(a.rbegin(), a.rend());             // giảm dần
    // sort(a.begin(), a.end(), greater());

    for (int x : a) cout << x << ' ';
    return 0;
}

n = int(input())
a = list(map(int, input().split()))

a.sort()                    # tăng dần
# a.sort(reverse=True)      # giảm dần

print(*a)

4.5. Mở rộng nhẹ: Counting Sort khi giá trị nhỏ

Nếu biết 0 ≤ a[i] ≤ 100 hoặc giá trị nằm trong miền nhỏ, có thể đếm tần suất. Cách này rất hữu ích cho học sinh mới học mảng.

🔍 Ví dụ trực quan

Giả sử mảng là 4 2 2 8 3 3 1. Counting Sort không đổi chỗ liên tục như Bubble Sort. Thay vào đó, ta làm 2 bước rõ ràng:

Đếm tần suất: số 1 xuất hiện mấy lần, số 2 xuất hiện mấy lần, ...
Dựng lại mảng: đi từ nhỏ đến lớn, giá trị nào có tần suất k thì ghi ra k lần.

Điểm quan trọng: Counting Sort hợp khi miền giá trị nhỏ. Ví dụ điểm số từ 0 đến 10, số nguyên từ 0 đến 100,...

Mảng ban đầu:

📊 Bảng đếm tần suất

🧱 Mảng sau khi dựng lại

Chưa có phần tử nào được ghi ra.

Nhấn “Bước tiếp” để quan sát Counting Sort hoạt động.

#include 
using namespace std;

int main() {
    int n;
    cin >> n;
    vector cnt(101, 0);       // giả sử 0 <= a[i] <= 100

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    for (int x = 0; x <= 100; x++) {
        while (cnt[x] > 0) {
            cout << x << ' ';
            cnt[x]--;
        }
    }
    return 0;
}

n = int(input())
a = list(map(int, input().split()))

cnt = [0] * 101       # giả sử 0 <= a[i] <= 100
for x in a:
    cnt[x] += 1

ans = []
for x in range(101):
    ans += [x] * cnt[x]

print(*ans)

5. Lỗi học sinh hay nhầm

Nhầm Selection Sort với Bubble Sort.
Selection tìm vị trí nhỏ nhất rồi đổi một lần; Bubble đổi nhiều cặp kề nhau.

Sai giới hạn vòng lặp Bubble Sort.
Nên dùng j < n - i - 1 để không truy cập vượt a[j+1].

Quên đặt lại min_pos = i trong Selection Sort.
Mỗi vòng ngoài phải tìm lại vị trí nhỏ nhất của đoạn mới.

Quên gán a[j + 1] = key trong Insertion Sort.
Dịch phần tử xong phải đưa key vào vị trí trống.

Dùng thuật toán O(n²) cho n quá lớn.
Với n = 100000, nên dùng sort có sẵn hoặc thuật toán phù hợp hơn.

6. Thực hành nhanh trên mảng của em

Nhập mảng

Kết quả sẽ hiện ở đây.

7. Bài tập luyện tập phân loại

📘 Mức 1 - Cơ bản

Nhập n và mảng n số nguyên. In mảng tăng dần bằng Selection Sort.
Sắp xếp mảng giảm dần bằng Bubble Sort.
In ra mảng sau mỗi vòng ngoài của Bubble Sort để quan sát.

📗 Mức 2 - Trung bình

Đếm số lần đổi chỗ của Bubble Sort.
Sắp xếp danh sách điểm, in điểm thấp nhất và cao nhất.
Dùng Insertion Sort để sắp xếp mảng đã gần đúng thứ tự.

📙 Mức 3 - Nâng cao

Sắp xếp cặp (điểm, mã học sinh): điểm tăng dần, nếu bằng thì mã tăng dần.
Cho mảng đã sắp xếp, tìm median.
Sắp xếp rồi loại bỏ các giá trị trùng nhau.

🐉 Mức 4 - HSG định hướng

Sắp xếp để tìm hai số có tổng gần K nhất.
Sắp xếp sự kiện theo thời gian bắt đầu, nếu bằng thì theo thời gian kết thúc.
So sánh số phép gán của Selection Sort và Insertion Sort trên cùng input.

8. Quiz kiểm tra nhanh

Câu 1. Bubble Sort thường so sánh phần tử nào?

Câu 2. Selection Sort cần tìm gì ở mỗi vòng ngoài?

Câu 3. Nếu đề thi có n = 100000 và chỉ yêu cầu sắp xếp, lựa chọn hợp lý nhất là gì?

Tổng kết

Ba thuật toán Selection Sort, Insertion Sort, Bubble Sort đều có độ phức tạp cơ bản O(n²). Chúng rất tốt để học tư duy vòng lặp, so sánh và đổi chỗ. Khi làm bài thi với dữ liệu lớn, hãy ưu tiên sort có sẵn nếu đề cho phép.

➡ Tiếp theo: Luyện tập sắp xếp kết hợp tìm kiếm, đếm tần suất và xử lý cặp dữ liệu.