I. Lý thuyết trọng tâm

Giới thiệu bài toán sắp xếp

Ở bài học trước, ta đã thấy tìm kiếm nhị phân trên dãy đã sắp xếp nhanh hơn rất nhiều so với tìm kiếm tuần tự. Vì vậy, bài toán sắp xếp có vai trò quan trọng, gắn liền với bài toán tìm kiếm.

Phát biểu bài toán sắp xếp:

• Đầu vào: Dãy A gồm n phần tử: A[0], A[1], …, A[n−1].
• Đầu ra: Dãy A được sắp xếp lại theo thứ tự tăng dần: A[0] ≤ A[1] ≤ … ≤ A[n−1].

Có nhiều thuật toán sắp xếp khác nhau. Trong bài này, ta tìm hiểu ba thuật toán đơn giản và dễ hiểu nhất: sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt.

1. Thuật toán sắp xếp chèn (Insertion Sort)

1.1. Ý tưởng

Hãy tưởng tượng bạn đang cầm một bộ bài trên tay và muốn xếp theo thứ tự. Bạn lấy từng lá bài từ trái sang phải, mỗi lá bài mới được chèn vào đúng vị trí trong phần đã sắp xếp phía trước.

Cụ thể, thuật toán cho chỉ số i chạy từ 1 (phần tử thứ hai) đến n − 1 (phần tử cuối). Tại mỗi bước, phần tử A[i] được “nhấc lên” rồi chèn vào vị trí đúng trong dãy con đã sắp xếp A[0], A[1], ..., A[i−1]. Sau n − 1 bước lặp, toàn bộ dãy được sắp xếp xong.

Thao tác chèn thực hiện bằng cách: lưu giá trị A[i] vào biến tạm, sau đó dịch chuyển các phần tử bên trái lớn hơn A[i] sang phải một vị trí, cuối cùng đặt A[i] vào ô trống.

1.2. Minh hoạ từng bước

Xét dãy A = [5, 3, 9, 7, 2]:

Quy luật: Tại mỗi bước, phần in đậm là dãy con đã sắp xếp. Phần tử tiếp theo được chèn vào đúng vị trí trong dãy con này.

1.3. Cài đặt bằng Python

def InsertionSort(A):
    n = len(A)
    for i in range(1, n):
        value = A[i]
        j = i - 1
        while j >= 0 and A[j] > value:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = value

Giải thích từng dòng:

• Dòng 3: Vòng for chạy i từ 1 đến n−1 (duyệt từ phần tử thứ hai đến cuối).
• Dòng 4: Lưu giá trị A[i] vào biến value (giống việc “nhấc” phần tử lên).
• Dòng 5: Biến j bắt đầu từ vị trí ngay bên trái i, dùng để duyệt ngược dãy con đã sắp xếp.
• Dòng 6–8: Vòng while kiểm tra: nếu A[j] lớn hơn value thì dịch A[j] sang phải một ô (A[j+1] = A[j]), rồi lùi j về trái. Quá trình này tạo ra “khoảng trống” cho value.
• Dòng 9: Đặt value vào vị trí đúng (ô trống vừa tạo ra).

2. Thuật toán sắp xếp chọn (Selection Sort)

2.1. Ý tưởng

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

Cụ thể, chỉ số i chạy từ 0 đến n − 2. Tại bước thứ i, tìm phần tử nhỏ nhất trong đoạn A[i], A[i+1], ..., A[n−1] rồi đổi chỗ phần tử đó với A[i]. Sau mỗi bước, A[0], A[1], ..., A[i] đã nằm đúng vị trí cuối cùng.

2.2. Minh hoạ từng bước

Xét dãy A = [5, 3, 9, 7, 2]:

Quy luật: Phần in đậm là các phần tử đã được đặt đúng vị trí cuối cùng. Mỗi vòng lặp thêm một phần tử vào phần đã sắp xếp.

2.3. Cài đặt bằng Python

def SelectionSort(A):
    n = len(A)
    for i in range(n - 1):
        iMin = i
        for j in range(i + 1, n):
            if A[j] < A[iMin]:
                iMin = j
        A[i], A[iMin] = A[iMin], A[i]

Giải thích từng dòng:

• Dòng 3: Vòng for ngoài chạy i từ 0 đến n−2 (không cần đến n−1 vì phần tử cuối tự động đúng chỗ).
• Dòng 4: Giả sử phần tử nhỏ nhất nằm tại vị trí i (biến iMin lưu chỉ số).
• Dòng 5–7: Vòng for trong duyệt từ i+1 đến n−1, nếu tìm thấy phần tử nhỏ hơn A[iMin] thì cập nhật iMin.
• Dòng 8: Đổi chỗ A[i] với A[iMin] bằng phép gán đồng thời của Python.

3. Thuật toán sắp xếp nổi bọt (Bubble Sort)

3.1. Ý tưởng

Thuật toán lấy cảm hứng từ hiện tượng bọt khí nổi dần lên mặt nước. Ý tưởng: liên tục so sánh hai phần tử cạnh nhau, nếu chúng chưa đúng thứ tự thì đổi chỗ. Phần tử lớn sẽ dần “nổi” về cuối dãy sau mỗi vòng lặp.

Cụ thể, thuật toán dùng hai vòng lặp lồng nhau. Vòng ngoài (biến i) chạy n − 1 lần. Vòng trong (biến j) duyệt từ đầu dãy, so sánh A[j] với A[j+1] – nếu A[j] > A[j+1] thì đổi chỗ. Sau vòng lặp thứ nhất, phần tử lớn nhất được đẩy về cuối dãy. Sau vòng thứ hai, phần tử lớn thứ hai về đúng chỗ. Cứ tiếp tục cho đến khi dãy sắp xếp xong.

3.2. Minh hoạ vòng lặp đầu tiên

Xét dãy A = [5, 3, 9, 7, 2], theo dõi chi tiết vòng lặp 1 (i = 0):

Kết thúc vòng 1: [3, 5, 7, 2, 9]. Phần tử lớn nhất (9) đã “nổi” về cuối dãy.

Tiếp tục các vòng sau:

3.3. Cài đặt bằng Python

def BubbleSort(A):
    n = len(A)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]

Giải thích từng dòng:

• Dòng 3: Vòng for ngoài chạy n − 1 lần (cần tối đa n − 1 vòng để sắp xếp xong).
• Dòng 4: Vòng for trong chạy j từ 0 đến n − 2 − i. Tại sao lại trừ i? Vì sau i vòng lặp ngoài, i phần tử lớn nhất đã nằm đúng chỗ ở cuối dãy → không cần so sánh lại.
• Dòng 5–6: Nếu hai phần tử cạnh nhau ngược thứ tự (A[j] > A[j+1]) thì đổi chỗ.

4. So sánh ba thuật toán

II. Phương pháp giải các dạng bài tập

Dạng 1: Sắp xếp dãy cho trước bằng ba thuật toán

Phương pháp: Áp dụng trực tiếp ba hàm InsertionSort, SelectionSort, BubbleSort đã học. Lưu ý cả ba thuật toán đều sắp xếp tại chỗ (thay đổi trực tiếp trên dãy A), nên cần tạo bản sao nếu muốn giữ dãy gốc.

Bài 1 (Luyện tập SGK). Cho dãy A = [5, 8, 1, 0, 10, 4, 3]. Viết các chương trình sắp xếp dãy A theo thứ tự tăng dần theo ba thuật toán.

Lời giải:

# --- Sắp xếp chèn ---
def InsertionSort(A):
    n = len(A)
    for i in range(1, n):
        value = A[i]
        j = i - 1
        while j >= 0 and A[j] > value:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = value

# --- Sắp xếp chọn ---
def SelectionSort(A):
    n = len(A)
    for i in range(n - 1):
        iMin = i
        for j in range(i + 1, n):
            if A[j] < A[iMin]:
                iMin = j
        A[i], A[iMin] = A[iMin], A[i]

# --- Sắp xếp nổi bọt ---
def BubbleSort(A):
    n = len(A)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]

# Thử nghiệm
A1 = [5, 8, 1, 0, 10, 4, 3]
A2 = A1.copy()
A3 = A1.copy()

InsertionSort(A1)
print("Sắp xếp chèn:", A1)

SelectionSort(A2)
print("Sắp xếp chọn:", A2)

BubbleSort(A3)
print("Sắp xếp nổi bọt:", A3)

Kết quả cả ba đều cho: [0, 1, 3, 4, 5, 8, 10].

Giải thích: Dùng A1.copy() để tạo bản sao, vì mỗi thuật toán sắp xếp tại chỗ sẽ thay đổi dãy truyền vào. Nếu không copy, sau khi chạy InsertionSort(A1) thì A1 đã thay đổi, ảnh hưởng đến kết quả của hai thuật toán còn lại.

Dạng 2: Nhập dãy từ bàn phím rồi sắp xếp

Phương pháp: Dùng input().split() để nhập dãy số trên một dòng, chuyển đổi kiểu bằng list comprehension, sau đó gọi hàm sắp xếp.

Bài 2 (Luyện tập SGK). Viết chương trình nhập một dãy số từ bàn phím (các số cách nhau bởi dấu cách), sắp xếp rồi in kết quả.

Lời giải:

def BubbleSort(A):
    n = len(A)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]

line = input("Nhập dãy số cách nhau bởi dấu cách: ")
A = [int(x) for x in line.split()]

print("Dãy ban đầu:", A)
BubbleSort(A)
print("Dãy sau khi sắp xếp:", A)

Giải thích: Bài này có thể dùng bất kỳ thuật toán nào trong ba thuật toán. Ở đây dùng Bubble Sort cho ngắn gọn. Phần nhập dữ liệu dùng kỹ thuật quen thuộc: input() → split() → chuyển int().

Dạng 3: Viết thuật toán sắp xếp giảm dần

Phương pháp: Để đổi từ sắp xếp tăng dần sang giảm dần, chỉ cần đảo chiều điều kiện so sánh. Cụ thể: thay > thành < (hoặc ngược lại) trong các phép so sánh quyết định đổi chỗ/dịch chuyển.

Bài 3 (Vận dụng SGK). Viết lại các thuật toán sắp xếp trong bài theo thứ tự giảm dần.

Lời giải:

# --- Sắp xếp chèn – giảm dần ---
def InsertionSortDesc(A):
    n = len(A)
    for i in range(1, n):
        value = A[i]
        j = i - 1
        while j >= 0 and A[j] < value:    # Đổi > thành <
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = value

# --- Sắp xếp chọn – giảm dần ---
def SelectionSortDesc(A):
    n = len(A)
    for i in range(n - 1):
        iMax = i                            # Tìm phần tử LỚN NHẤT thay vì nhỏ nhất
        for j in range(i + 1, n):
            if A[j] > A[iMax]:             # Đổi < thành >
                iMax = j
        A[i], A[iMax] = A[iMax], A[i]

# --- Sắp xếp nổi bọt – giảm dần ---
def BubbleSortDesc(A):
    n = len(A)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if A[j] < A[j + 1]:            # Đổi > thành <
                A[j], A[j + 1] = A[j + 1], A[j]

# Thử nghiệm
A = [5, 8, 1, 0, 10, 4, 3]
BubbleSortDesc(A)
print("Giảm dần:", A)

Kết quả: [10, 8, 5, 4, 3, 1, 0].

Giải thích chi tiết sự thay đổi:

• Sắp xếp chèn: Điều kiện A[j] > value (dịch phần tử lớn hơn sang phải) → đổi thành A[j] < value (dịch phần tử nhỏ hơn sang phải).
• Sắp xếp chọn: Thay vì tìm phần tử nhỏ nhất (A[j] < A[iMin]), ta tìm phần tử lớn nhất (A[j] > A[iMax]) rồi đưa về đầu.
• Sắp xếp nổi bọt: Điều kiện đổi chỗ A[j] > A[j+1] → đổi thành A[j] < A[j+1]. Phần tử nhỏ nhất sẽ “chìm” về cuối thay vì phần tử lớn nhất “nổi” lên.

Dạng 4: Ý nghĩa thực tế của thuật toán sắp xếp

Bài 4 (Vận dụng SGK). Nêu ý nghĩa thực tế của các thuật toán sắp xếp đã học.

Lời giải:

Các thuật toán sắp xếp có ứng dụng rộng rãi trong thực tế:

• Sắp xếp học sinh theo chiều cao tăng dần để xếp hàng trong giờ thể dục hay chụp ảnh lớp. Có thể dùng thuật toán sắp xếp chọn: mỗi lần tìm bạn thấp nhất trong nhóm chưa xếp và đưa lên đầu hàng.
• Sắp xếp danh sách học sinh theo tên (thứ tự bảng chữ cái) để dễ tra cứu trong sổ điểm, danh sách lớp. Khi có học sinh mới chuyển đến, có thể dùng ý tưởng sắp xếp chèn: tìm đúng vị trí trong danh sách theo bảng chữ cái rồi chèn vào.
• Sắp xếp điểm thi từ cao xuống thấp để xếp hạng, trao giải. Sau khi sắp xếp, việc tìm kiếm (ví dụ tìm ai đạt trên 8 điểm) sẽ nhanh hơn nhờ áp dụng tìm kiếm nhị phân.
• Sắp xếp sản phẩm theo giá trên các trang thương mại điện tử, sắp xếp email theo thời gian, sắp xếp danh bạ điện thoại theo tên,… đều là ứng dụng của bài toán sắp xếp.

Nói chung, sắp xếp giúp dữ liệu trở nên có tổ chức, từ đó việc tìm kiếm, tra cứu và xử lí trở nên nhanh chóng và hiệu quả hơn.

III. Sơ đồ tư duy

                          ┌─ Ý tưởng: chèn A[i] vào đúng vị trí
        ┌─ Sắp xếp chèn ─┤   trong dãy con đã sắp xếp phía trước
        │  (Insertion)     ├─ i: 1 → n-1
        │                  ├─ Dịch phần tử lớn hơn sang phải
        │                  └─ Đặt A[i] vào ô trống
        │
        │                  ┌─ Ý tưởng: chọn phần tử nhỏ nhất
 CÁC    ├─ Sắp xếp chọn ──┤   trong phần chưa sắp, đổi chỗ với A[i]
 THUẬT  │  (Selection)     ├─ i: 0 → n-2
 TOÁN   │                  └─ Dùng biến iMin lưu chỉ số min
 SẮP    │
 XẾP    │                  ┌─ Ý tưởng: đổi chỗ 2 phần tử cạnh nhau
        ├─ Sắp xếp nổi bọt┤   nếu chưa đúng thứ tự
        │  (Bubble)        ├─ 2 vòng for lồng nhau
        │                  ├─ Vòng trong: j chạy n-1-i bước
        │                  └─ Phần tử lớn "nổi" về cuối sau mỗi vòng
        │
        └─ Điểm chung ──── Cả 3 đều sắp xếp tại chỗ trên dãy A
                           Đổi sang giảm dần: chỉ cần đảo chiều so sánh

Thầy Phạm Thành Danh

(Người kiểm duyệt, ra đề)

Chức vụ: Trưởng ban biên soạn môn Tin Học THPT

Trình độ: Cử nhân Sư phạm Tin học, Chứng chỉ hạng II, Chứng chỉ Tin học, Ngoại ngữ B1

Kinh nghiệm: 8+ năm kinh nghiệm tại Trường THPT Thuận Hóa