Login

Các thuật toán sắp xếp cơ bản: Bubble, Selection và Insertion Sort

  • author-image

    Nguyễn Đình Cường

  • blog-tag
  • blog-comment 0 comment
  • created-date 09 Nov, 2026
blog-thumbnail

Sắp xếp là một trong những bài toán lâu đời nhất của tin học: từ xếp bảng điểm, danh sách sản phẩm theo giá đến xếp kết quả tìm kiếm. Ba thuật toán đơn giản dưới đây là điểm khởi đầu lý tưởng để hiểu cách máy tính "suy nghĩ".

Bubble Sort: nổi bọt

Ý tưởng: duyệt qua mảng, so sánh hai phần tử kề nhau và đổi chỗ nếu sai thứ tự. Sau mỗi lượt, phần tử lớn nhất "nổi" về cuối như bọt khí.

def bubble_sort(ds):
    n = len(ds)
    for i in range(n - 1):
        da_doi = False
        for j in range(n - 1 - i):
            if ds[j] > ds[j + 1]:
                ds[j], ds[j + 1] = ds[j + 1], ds[j]
                da_doi = True
        if not da_doi:
            break
    return ds

print(bubble_sort([5, 2, 9, 1, 3]))   # [1, 2, 3, 5, 9]

Biến da_doi giúp dừng sớm nếu mảng đã được sắp xếp. Độ phức tạp trung bình và xấu nhất là O(n^2).

Selection Sort: chọn phần tử nhỏ nhất

Ý tưởng: ở mỗi bước, tìm phần tử nhỏ nhất trong phần chưa sắp xếp rồi đưa nó về đầu phần đó.

def selection_sort(ds):
    n = len(ds)
    for i in range(n - 1):
        vi_tri_min = i
        for j in range(i + 1, n):
            if ds[j] < ds[vi_tri_min]:
                vi_tri_min = j
        ds[i], ds[vi_tri_min] = ds[vi_tri_min], ds[i]
    return ds

print(selection_sort([5, 2, 9, 1, 3]))   # [1, 2, 3, 5, 9]

Thuật toán này luôn là O(n^2) so sánh, nhưng số lần hoán đổi chỉ tối đa n - 1, hữu ích khi việc đổi chỗ tốn kém.

Insertion Sort: chèn như xếp bài

Hãy nghĩ đến lúc bạn cầm các lá bài trên tay: lấy từng lá mới và chèn vào đúng chỗ trong phần đã xếp xong.

def insertion_sort(ds):
    for i in range(1, len(ds)):
        khoa = ds[i]
        j = i - 1
        while j >= 0 and ds[j] > khoa:
            ds[j + 1] = ds[j]
            j -= 1
        ds[j + 1] = khoa
    return ds

print(insertion_sort([5, 2, 9, 1, 3]))   # [1, 2, 3, 5, 9]

Insertion sort rất nhanh với mảng gần như đã sắp xếp (gần O(n)) và thường tốt nhất trong ba cách với mảng nhỏ. Vì vậy nhiều thư viện thực tế dùng nó cho các đoạn ngắn bên trong thuật toán phức tạp hơn.

So sánh

Thuật toánTrường hợp xấu nhấtĐặc điểm
BubbleO(n^2)Dễ hiểu, hay dùng để dạy
SelectionO(n^2)Ít lần hoán đổi
InsertionO(n^2)Nhanh với dữ liệu gần sắp xếp

Vậy trong thực tế dùng gì?

Với dữ liệu lớn, các thuật toán O(n^2) quá chậm. Các thuật toán như Merge Sort và Quick Sort đạt trung bình O(n log n). Ngôn ngữ nào cũng có hàm sắp xếp sẵn, hãy dùng chúng thay vì tự viết:

ds = [5, 2, 9, 1, 3]
print(sorted(ds))                  # tạo danh sách mới
ds.sort(reverse=True)              # sắp xếp tại chỗ, giảm dần

nguoi = [("An", 20), ("Bình", 18), ("Chi", 22)]
print(sorted(nguoi, key=lambda p: p[1]))   # theo tuổi

Vậy tại sao vẫn phải học thuật toán đơn giản? Vì chúng rèn tư duy: so sánh, hoán đổi, bất biến của vòng lặp, và là bước đệm để hiểu những thuật toán nhanh hơn. Đây cũng là câu hỏi quen thuộc trong các buổi phỏng vấn.

Sắp xếp ổn định

Một thuật toán gọi là ổn định nếu hai phần tử bằng nhau giữ nguyên thứ tự ban đầu. Điều này quan trọng khi sắp xếp theo nhiều tiêu chí liên tiếp, ví dụ xếp theo lớp rồi theo tên. Bubble và Insertion ổn định, Selection (bản thông thường) thì không.

Trực quan hóa để hiểu sâu hơn

Cách nhanh nhất để thực sự hiểu một thuật toán sắp xếp là in ra trạng thái mảng sau mỗi bước:

def insertion_sort_in(ds):
    for i in range(1, len(ds)):
        khoa = ds[i]
        j = i - 1
        while j >= 0 and ds[j] > khoa:
            ds[j + 1] = ds[j]
            j -= 1
        ds[j + 1] = khoa
        print(f"Sau lượt {i}:", ds)

insertion_sort_in([5, 2, 9, 1, 3])

Kết quả cho thấy phần đầu mảng luôn đã sắp xếp và dài thêm một phần tử sau mỗi lượt. Hãy làm tương tự với bubble sort và selection sort rồi so sánh: bubble đẩy giá trị lớn về cuối, selection chọn giá trị nhỏ nhất đặt lên đầu.

Bài tập nâng cao: đếm số phép so sánh và số lần hoán đổi của mỗi thuật toán trên mảng ngẫu nhiên 1.000 phần tử, mảng đã sắp xếp và mảng sắp xếp ngược. Bạn sẽ tự khám phá vì sao insertion sort được ưa chuộng với dữ liệu gần sắp xếp.

Kết luận

Ba thuật toán sắp xếp cơ bản giúp bạn nhìn thấy "bên trong" một việc mà hàm sort vẫn làm hằng ngày. Hãy tự cài từng cái, chạy thử trên giấy với mảng nhỏ, rồi in từng bước để quan sát. Sau đó tiếp tục với Merge Sort và Quick Sort để thấy sức mạnh của chia để trị.

Khi đã sẵn sàng đi sâu hơn, bạn có thể tham khảo lộ trình học trong các khóa học tại codebem.com.

author_photo
Nguyễn Đình Cường

0 comment