Giáo án điện tử Khoa học máy tính 11 kết nối Bài 21: Các thuật toán sắp xếp đơn giản

CHÀO MỪNG CẢ LỚP ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

Bài toán sắp xếp cơ bản có dạng như sau:

Cho dãy A gồm n phần tử:                     A[0], A[1],…, A[n-1]     (1)

Cần sắp xếp dãy theo thứ tự tăng dần: A[0] ≤ A[1] ≤ … ≤ A[n-1]          (2)

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ử.

BÀI 21: CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN

NỘI DUNG BÀI HỌC

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

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

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

01 THUẬT TOÁN SẮP XẾP CHÈN

Hoạt động 1: Tìm hiểu ý tưởng thuật toán sắp xếp chèn

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

Dựa vào sơ đồ mô phỏng và trả lời các câu hỏi sau:

• So sánh số bước lặp với độ dài của dãy số ban đầu.
• 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?
• Khi kết thúc lặp ta thu được kết quả gì?

GHI NHỚ

Ý tưởng của thuật toán sắp xếp chèn là thực hiện vòng lặp duyệt từ phần tử thứ hai đến cuối dãy. Sau mỗi bước lặp phần tử tương ứng sẽ được chèn vào vị trí đúng của dãy con đã sắp xếp là các phần tử phía trước vị trí đang duyệt.

Thuật toán sắp xếp chèn có thể mô tả bằng hàm InsertSort(A) như sau:

1  deft InsertionSort(A):

2        n = len(A)

3        for i in range(1,n):

4                 value = A[i]

5                 j = i – 1

6                 while j >= 0 and A[j] > value:

7                           A[j+1] = A[j]

8                           j = j – 1

9                 A[j+1] = value

Câu hỏi củng cố kiến thức

Câu 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]

• Bước 1. Chèn phần tử 0 vào trước 5, dãy thu được: [0, 5, 4, 2, 3]
• Bước 2. Chèn phần tử 4 vào trước 5, thu được: [0, 4, 5, 2, 3]
• Bước 3. Chèn phần tử 2 vào trước 4, thu được: [0, 2, 4, 5, 3]
• Bước 4. Chèn phần tử 3 vào trước 4, thu được: [0, 2, 3, 4, 5]

Câu 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?

Nếu dãy ban đầu đã được sắp xếp đúng thì tại mỗi bước duyệt không cần thực hiện thao tác "chèn" nữa vì A[i] đã ở đúng vị trí rồi. Do vậy, thuật toán sắp xếp chèn sẽ không thực hiện bất cứ thao tác gì trên dãy đã cho.

02 THUẬT TOÁN SẮP XẾP CHỌN

Hoạt động 2: Tìm hiểu ý tưởng thuật toán sắp xếp chọn

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.

Bài toán: Xét dãy A = [5, 3, 9, 7, 2]. Quan sát sơ đồ Hình 21.2 SGK trang 101 và 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?
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?
3. Khi kết thúc vòng lặp ta thu được kết quả gì?

Hình 21.2. Mô phỏng thuật toán sắp xếp chọn

MỞ RỘNG:

Video sau đây hướng dẫn sắp xếp số hạng trong dãy số bằng cách sắp xếp chọn.

GHI NHỚ

Thuật toán sắp xếp chọn thực hiện một vòng lặp với chỉ số i chạy từ 0 (phần tử đầu tiên) đến n – 2 (phần tử gần cuối). Tại mỗi bước lặp, chọn phần tử nhỏ nhất nằm trong dãy A[i], A[i+1],…,A[n – 1] và đổi chỗ phần tử này với A[i].

Thuật toán sắp xếp chọn có thể mô tả bằng hàm SelectSort(A) như sau:

1 def SelectionSort(A):

2        n = len(A)

3        for i in range(n-1):

4                 iMin = i

5                 for j in range(i+1,n):

6                           if A[j] < A[iMin]:

7                                    iMin = j

8                 A[i],A[iMin] = A[iMin],A[i]

Câu hỏi củng cố kiến thức