Câu hỏi mở đầu trang 99

Đề bài: Cho dãy A gồm n phần tử: A[0], A[1], …, A[n-1]. Cần xếp dãy A theo thứ tự tăng dần: A[0] ≤ A[1] ≤ … ≤ A[n-1]. Em hãy trình bày ý tưởng của mình để giải bài toán sắp xếp với dãy có bốn phần tử.

Lời giải:

Với dãy 4 phần tử, có thể sử dụng một trong các ý tưởng sau:

• Cách 1: Chọn phần tử nhỏ nhất trong dãy đưa lên đầu, sau đó tìm nhỏ nhất trong 3 phần tử còn lại đưa vào vị trí thứ hai, cứ tiếp tục cho đến hết.
• Cách 2: So sánh từng cặp phần tử liền kề, nếu chưa đúng thứ tự thì đổi chỗ. Lặp lại cho đến khi dãy sắp xếp đúng.
• Cách 3: Xét từng phần tử từ trái sang, chèn phần tử đang xét vào vị trí đúng trong phần dãy đã được sắp xếp phía trước.

→ Đây chính là các ý tưởng của sắp xếp chọn, sắp xếp nổi bọt và sắp xếp chèn sẽ học trong bài.

1. Thuật toán sắp xếp chèn

Hoạt động 1 trang 99

Đề bài: Quan sát sơ đồ mô phỏng, trao đổi, thảo luận về ý tưởng chính của thuật toán sắp xếp chèn. Cho dãy A = [5, 3, 9, 7, 2]. Trả lời các câu hỏi:

1) So sánh số bước lặp với độ dài của dãy số ban đầu.

Lời giải:

Dãy có 5 phần tử, thuật toán thực hiện 4 vòng lặp.

→ Số bước lặp = n – 1 (với n là độ dài dãy).

2) Vị trí xuất phát của mũi tên màu đỏ có quan hệ gì với chỉ số bước lặp?

Lời giải:

Vị trí xuất phát của mũi tên đỏ chính là chỉ số i của bước lặp, tức là phần tử A[i] đang được xét để chèn vào vị trí đúng trong dãy con A[0], A[1], …, A[i-1] đã sắp xếp.

3) Khi kết thúc lặp ta thu được kết quả gì?

Lời giải:

Khi kết thúc lặp, ta thu được dãy đã được sắp xếp theo thứ tự tăng dần: [2, 3, 5, 7, 9].

Câu hỏi củng cố mục 1 trang 100

Đề bài:

1. Mô phỏng chi tiết các bước lặp sắp xếp chèn dãy A = [5, 0, 4, 2, 3].

Lời giải:

2. Nếu dãy ban đầu đã được sắp xếp thì thuật toán sắp xếp chèn sẽ thực hiện như thế nào?

Lời giải:

• Nếu dãy đã sắp xếp, mọi phần tử A[i] đều lớn hơn hoặc bằng phần tử ngay trước nó A[i-1].
• Với mỗi vòng lặp, điều kiện A[j] > value không đúng ngay từ đầu, nên vòng while không chạy lần nào.
• Kết quả: mỗi phần tử được giữ nguyên vị trí, không đổi chỗ.

→ Thuật toán vẫn duyệt qua đủ n – 1 vòng lặp, nhưng không thực hiện thao tác chèn nào. Dãy giữ nguyên như ban đầu.

2. Thuật toán sắp xếp chọn

Hoạt động 2 trang 100

Đề bài: Quan sát sơ đồ mô phỏng, trao đổi, thảo luận về ý tưởng chính của thuật toán sắp xếp chọn. Xét dãy A = [5, 3, 9, 7, 2]. Trả lời các câu hỏi:

1) Có bao nhiêu vòng lặp? Chỉ số i bắt đầu bằng bao nhiêu?

Lời giải:

Có 4 vòng lặp (n – 1 = 5 – 1 = 4 vòng). Chỉ số i bắt đầu bằng 0, chạy đến n – 2 = 3.

2) Tại mỗi vòng lặp đều có một thao tác đổi chỗ hai phần tử, đó là các phần tử nào?

Lời giải:

Mỗi vòng lặp đổi chỗ phần tử nhỏ nhất trong dãy con A[i], A[i+1], …, A[n-1] với phần tử A[i].

Cụ thể với dãy [5, 3, 9, 7, 2]:

• Vòng 1 (i = 0): đổi chỗ 2 và 5 (2 là nhỏ nhất trong toàn dãy).
• Vòng 2 (i = 1): 3 đã là nhỏ nhất trong dãy con → giữ nguyên.
• Vòng 3 (i = 2): đổi chỗ 5 và 9.
• Vòng 4 (i = 3): 7 đã là nhỏ nhất trong dãy con → giữ nguyên.

3) Khi kết thúc vòng lặp ta thu được kết quả gì?

Lời giải:

Khi kết thúc, ta thu được dãy đã sắp xếp theo thứ tự tăng dần: [2, 3, 5, 7, 9].

Câu hỏi củng cố mục 2 trang 102

Đề bài:

1. Thực hiện mô phỏng sắp xếp theo thuật toán sắp xếp chọn dãy sau: 4, 5, 2, 1, 3.

Lời giải:

2. Theo thuật toán sắp xếp chọn, sau mỗi bước thứ i thì các phần tử A[0], A[1], …, A[i] đã được sắp xếp đúng. Đúng hay sai?

Lời giải:

Đúng.

Giải thích:

• Sau bước i, phần tử A[i] là nhỏ nhất trong dãy con A[i], A[i+1], …, A[n-1].
• A[i] chắc chắn lớn hơn hoặc bằng các phần tử A[0], A[1], …, A[i-1] đã đặt đúng ở các bước trước.
• Do đó dãy con A[0], A[1], …, A[i] đã ở đúng vị trí cuối cùng.

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

Hoạt động 3 trang 102

Đề bài: Cùng trao đổi, thảo luận về các ý tưởng của thuật toán sắp xếp nổi bọt.

Lời giải:

Ý tưởng: Liên tục so sánh và đổi chỗ hai phần tử cạnh nhau nếu chúng chưa đúng thứ tự. Sau mỗi vòng lặp, phần tử lớn nhất “nổi” dần về cuối dãy giống bọt khí nổi lên mặt nước.

Vòng lặp bên trong (tổng quát): chỉ số j chạy từ 0 đến n – 2, so sánh A[j] và A[j+1]:

for j in range(n-1):
    if A[j] > A[j+1]:
        Đổi chỗ A[j], A[j+1]

Sau vòng lặp đầu tiên: phần tử lớn nhất được chuyển về cuối dãy.

Kết hợp hai vòng lặp lồng nhau để sắp xếp toàn bộ dãy:

• Vòng ngoài chạy n – 1 lần.
• Sau lần lặp thứ i, đã có i phần tử lớn nhất nằm đúng vị trí ở cuối dãy → vòng trong chỉ cần chạy đến n – 1 – 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]

Câu hỏi củng cố mục 3 trang 103

Đề bài:

1. Mô tả các bước thuật toán sắp xếp nổi bọt của dãy A = [4, 3, 1, 2].

Lời giải:

Dãy có n = 4 phần tử, vòng ngoài i chạy từ 0 đến 2.

Vòng lặp 1 (i = 0), j chạy từ 0 đến 2:

Vòng lặp 2 (i = 1), j chạy từ 0 đến 1:

Vòng lặp 3 (i = 2), j chạy từ 0 đến 0:

Kết thúc: dãy được sắp xếp: [1, 2, 3, 4].

2. Khi nào thì các mũi tên ở tất cả các bước trong sơ đồ mô phỏng thuật toán sắp xếp nổi bọt đều có màu đỏ?

Lời giải:

Mũi tên đỏ biểu thị có đổi chỗ, mũi tên tím biểu thị không đổi chỗ.

→ Tất cả mũi tên đỏ khi tại mọi bước so sánh đều xảy ra đổi chỗ, tức là A[j] > A[j+1] tại mọi j.

→ Điều đó xảy ra khi dãy ban đầu sắp xếp giảm dần (ngược với thứ tự cần sắp xếp).

Ví dụ: A = [5, 4, 3, 2, 1] → tại mọi bước so sánh, phần tử bên trái đều lớn hơn phần tử bên phải nên đều phải đổi chỗ.

Luyện tập

Luyện tập trang 103

Đề bài:

1. 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 các thuật toán sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt.

Lời giải:

A = [5, 8, 1, 0, 10, 4, 3]

# 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]

# Chạy thử với dãy A (dùng bản sao để không ảnh hưởng lẫn nhau)
A1 = A.copy(); InsertionSort(A1); print("Sắp xếp chèn:", A1)
A2 = A.copy(); SelectionSort(A2); print("Sắp xếp chọn:", A2)
A3 = A.copy(); BubbleSort(A3); print("Sắp xếp nổi bọt:", A3)

Kết quả in ra:

Sắp xếp chèn: [0, 1, 3, 4, 5, 8, 10]
Sắp xếp chọn: [0, 1, 3, 4, 5, 8, 10]
Sắp xếp nổi bọt: [0, 1, 3, 4, 5, 8, 10]

2. 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, thực hiện sắp xếp dãy đã nhập theo một trong các thuật toán sắp xếp rồi in kết quả ra màn hình.

Lời giải:

# Nhập dãy số từ bàn phím
A = input("Nhập dãy số: ").split()
for i in range(len(A)):
    A[i] = int(A[i])

# Dùng thuật toán 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]

SelectionSort(A)
print("Dãy sau khi sắp xếp:", A)

Giải thích:

• input().split() tách chuỗi nhập theo dấu cách thành danh sách các chuỗi.
• Duyệt để chuyển từng phần tử về số nguyên bằng int().
• Gọi hàm sắp xếp, rồi in kết quả.

Vận dụng

Vận dụng trang 103

Đề bài:

1. 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:

Chỉ cần đảo chiều phép so sánh trong mỗi thuật toán:

# Sắp xếp chèn giảm dần
def InsertionSortGiam(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 (tìm phần tử lớn nhất thay vì nhỏ nhất)
def SelectionSortGiam(A):
    n = len(A)
    for i in range(n-1):
        iMax = i
        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 BubbleSortGiam(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]

2. Nêu ý nghĩa thực tế của các thuật toán sắp xếp đã học, chẳng hạn sắp xếp các học sinh trong lớp theo chiều cao tăng dần.

Lời giải:

Một số ứng dụng thực tế của thuật toán sắp xếp:

• Sắp xếp học sinh theo chiều cao để xếp hàng chào cờ, thể dục.
• Sắp xếp điểm học sinh theo thứ tự giảm dần để xếp hạng cuối kì.
• Sắp xếp danh sách theo bảng chữ cái giúp tìm kiếm nhanh trong danh bạ, danh sách lớp.
• Sắp xếp sản phẩm theo giá trên trang thương mại điện tử để người mua dễ chọn lựa.
• Sắp xếp bài viết, tin nhắn theo thời gian để hiển thị nội dung mới nhất trước.
• Sắp xếp dữ liệu trước khi tìm kiếm nhị phân để tăng tốc độ tra cứu.

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