Soạn mới giáo án Khoa học máy tính 11 cánh diều Chủ đề F(CS) Bài 9: Lập trình thuật toán sắp xếp nhanh

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV chia lớp thành các nhóm đôi.

- GV yêu cầu các nhóm HS đọc hiểu mục 1, quan sát Hình 1 tr.127 SGK và trả lời các câu hỏi sau:

+ Trình bày về thuật toán sắp xếp nhanh (Quick Sort).

+ Quan sát Hình 1, hãy mô tả lược đồ phân đoạn dãy số.

Bước 2: HS thực hiện nhiệm vụ học tập

- Nhóm HS đọc hiểu mục 1, quan sát Hình 1 tr.127, thảo luận trả lời câu hỏi.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời 1 - 2 nhóm HS trả lời câu hỏi.

- HS nhóm khác lắng nghe, nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét câu trả lời của HS.

- GV nhấn mạnh: Thuật toán sắp xếp nhanh có thể sử dụng bất cứ lược đồ phân đoạn nào miễn là đáp ứng yêu cầu kết quả đầu ra là:

+ Chia dãy làm hai nửa, nửa bên trái chỉ gồm các phần tử nhỏ hơn hay bằng pivot; nửa bên phải chỉ gồm các phần tử lớn hơn hay bằng pivot.

+ Trả về vị trí của pivot, điểm phân tách dãy thành hai đoạn như trên.

- GV kết luận và yêu cầu HS ghi chép đầy đủ vào vở.

1. Lược đồ phân đoạn trong sắp xếp nhanh

Thuật toán sắp xếp nhanh (Quick Sort)

- Thuật toán theo chiến lược chia để trị, lặp lại nhiều lần việc phân đoạn dãy đầu vào thành hai đoạn con.

Lược đồ phân đoạn dãy số

- Lấy giá trị của một phần từ trong dãy làm pivot (giá trị chốt). Giá trị pivot có thể là bất cứ phần tử nào trong dãy.

- Kết quả phân đoạn:

+ Đoạn con ở nửa dãy bên trái chỉ gồm các phần tử nhỏ hơn hay bằng pivot.

+ Đoạn con ở nửa dãy bên phải chỉ gồm các phần tử lớn hơn hay bằng pivot.

+ Phần tử làm pivot được chuyển đến vị trí phân tách hai đoạn.

Hình 1. Kết quả phân đoạn: đoạn trái = {i|lo ≤ i ≤ p – 1}, đoạn phải = {j|p + 1 ≤ i ≤ hi}

- Hàm thực hiện phân đoạn cần trả về vị trí phân tách dãy thành hai đoạn con vì sau đó sẽ sắp xếp chỉ trong nội bộ hai đoạn con.

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu các HS đọc hiểu mục 2, quan sát Hình 2, 3, kết hợp với kiến thức vừa tìm hiểu ở mục 1, thảo luận nhóm đôi trả lời câu hỏi Hoạt động SGK tr.128:

Em hãy cho biết lược đồ phân đoạn Lomuto theo mã giả trong Hình 2 có đáp ứng yêu cầu phân đoạn để sắp xếp nhanh như trình bày ở mục 1 hay không.

- Trên cơ sở đó, GV yêu cầu các nhóm mô tả diễn biến từng bước thực hiện phân đoạn Lomuto.

- GV yêu cầu các nhóm tính số phép toán sơ cấp thực hiện phân đoạn Lomuto cho trường hợp dãy tăng dần.

- GV có thể thay đổi giá trị của số ở đầu dãy và cuối dãy để minh họa dịch chuyển pivot.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc hiểu mục 2, quan sát Hình 2, 3 kết hợp kiến thức đã học để thực hiện nhiệm vụ.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời một số HS báo cáo kết quả thảo luận.

- Các HS còn lại nhận xét, bổ sung (nếu có).

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét kết quả trả lời của HS.

- GV tổng quát kiến thức và yêu cầu HS ghi chép đầy đủ vào vở.

2. Thuật toán sắp xếp nhanh áp dụng phân đoạn Lomuto

- Mã giả của thuật toán Lomuto phân đoạn dãy số a, trong đó:

lo là chỉ số đầu mút trái

hi là chỉ số đầu mút phải

- Ý tưởng của thuật toán Lomuto: Chọn pivot là giá trị phần tử đứng cuối dãy số.

+ Duy trì chỉ số i ở vị trí phân tách;

+ Duyệt dãy số bằng một chỉ số j khác và đảo giá trị các phần tử sao cho các phần tử từ vị trí i – 1 về đầu mút trái nhỏ hơn hay bằng pivot; các phần tử từ vị trí i + 1 đến j lớn hơn pivot, riêng phần tử ở vị trí i đúng bằng pivot.

- Mã lệnh Python thực hiện sắp xếp nhanh bằng phân đoạn Lomuto:

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV đặt vấn đề, giới thiệu về tác giả Hoare của thuật toán sắp xếp nhanh:

Charles Antony Richard Hoare (Tony Hoare) - Nhà Khoa học máy tính

- GV yêu cầu HS tiếp tục hoạt động nhóm đôi, đọc hiểu mục 3, quan sát Hình 4, 5 SGK tr.129, kết hợp với kiến thức đã học, thảo luận trả lời các câu hỏi sau:

+ Ý tưởng chính của thuật toán sắp xếp nhanh áp dụng phân đoạn Hoare là gì?

+ Trình bày mã giả thực hiện phân đoạn Hoare và mã lệnh Python tương ứng.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc và tìm hiểu nhiệm vụ mục 3 quan sát Hình 4,5 SGK trang 129, thực hiện nhiệm vụ được giao.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời một số nhóm trình bày kết quả thảo luận.

- GV mời HS nhóm khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét kết quả thảo luận của HS, thái độ làm việc của HS trong nhóm.

- GV kết luận và yêu cầu HS ghi chép đầy đủ vào vở.

3. Thuật toán sắp xếp nhanh áp dụng phân đoạn Hoare

Lược đồ phân đoạn Hoare

- Ý tưởng của thuật toán:

+ Đổi chỗ nhảy qua điểm phân tách (pivot), rà soát từ hai phía, trái và phải, cùng tiến dần từng bước vào giữa.

+ Tạm dừng khi phát hiện phần tử vi phạm yêu cầu phân đoạn ở mỗi phía và đổi chỗ chúng cho nhau.

+ Rà soát từ hai điểm tạm dừng đi vào giữa cho đến khi gặp nhau thì kết thúc việc phân đoạn.

+ Điểm gặp nhau là vị trí phân tách dãy thành hai đoạn con.

- Mã giả của thuật toán sắp xếp nanh áp dụng phân đoạn Hoare:

- Mã lệnh Python của thuật toán phân đoạn dãy số a, xuất phát với pivot là đầu dãy.

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV nêu các nhiệm vụ, yêu cầu HS hoạt động nhóm (3 - 4 HS) thực hiện nhiệm vụ:

Nhiệm vụ 1. Viết chương trình thực hiện sắp xếp nhanh một dãy số và chạy thử kiểm tra.

a) Dựa trên mã lệnh thuật toán cho trong Hình 3.

b) Dựa trên mã lệnh thuật toán cho trong Hình 5.

Nhiệm vụ 2. Bổ sung thêm các câu lệnh in kết quả trung gian vào các chương trình nói trên để có thể quan sát diễn biến từng bước thực hiện sắp xếp nhanh một dãy số.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS vận dụng kiến thức đã học, thực hành nhiệm vụ tr.130 SGK.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- Các nhóm báo cáo kết quả thực hành.

- GV mời HS nhóm khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét kết quả thảo luận của HS, thái độ làm việc của HS trong nhóm.

- GV kết luận và yêu cầu HS ghi chép đầy đủ vào vở.

4. Thực hành

Đính kèm dưới Hoạt động 4.

⇨ Kết luận:

- Thuật toán sắp xếp nhanh có thể áp dụng một trong hai lược đồ phân đoạn: theo Lomuto hoặc theo Hoare.

- Lược đồ Lomuto thực hiện phân đoạn bằng cách kiểm tra theo một chiều từ trái sang phải đổi chỗ và dịch chuyển dần vị trí phân tách hai dãy con cho đến khi thỏa mãn yêu cầu phân đoạn.

- Lược đồ Hoare thực hiện phân đoạn bằng cách kiểm tra theo hai chiều, từ hai đầu dây số tiến dần vào giữa, đổi chỗ để thoả mãn yêu cầu phân đoạn; kết thúc khi gặp nhau.

Nhiệm vụ 1:

def phandoanLomuto(a, lo, hi):

    i = (lo-1)                       #i là vị trí phân tách

    pivot = a[hi]

    for j in range(lo,hi ):          #Duyệt dãy a[lo...hi]

        if a[j] <= pivot:            #Phần tử a[j] <= pivot

            i = i+1                  #Tăng i lên

            a[i], a[j] = a[j], a[i]     #Đảo giá trị a[i], a[j]

    a[i+1], a[hi] = a[hi], a[i+1]      #Đảo giá trị a[i+1], a[hi]

    return (i+1)                     #Hết vòng lặp, i là vị trí phân đoạn

                                     #a[i] = pivot

def quickSort(a, lo, hi):

    if lo < hi:

        p = phandoanLomuto(a, lo, hi #p là vị trí phân tách

                                     #a[p] đã ở đúng chỗ

        quickSort(a, lo, p-1)        #Sắp xếp đoạn bên trái

        quickSort(a, p+1, hi)        #Sắp xếp đoạn bên phải

data = [8, 7, 2, 1, 0, 9, 6]

print("Dãy ban đầu a:")

print(data)

size = len(data)

quickSort(data, 0, size - 1)

print('Dãy được sắp xếp:')

print(data)

Nhiệm vụ 2:

def partitionHoare(a, lo, hi):

    pivot = a[lo]

    i, j = lo, hi

    phanDoan = True

    while phanDoan:              #Đang phân đoạn

        #i qua phải đến khi a[i] >= pivot

        while a[i] < pivot:

            i = i + 1

        #j qua trái đến khi a[j] <= pivot

        while a[j] > pivot:

            j = j - 1

        if i < j:                   #i chưa gặp j  

        #Hoán đổi a[i] với a[j]

            a[i], a[j] = a[j], a[i]

            i = i + 1               # i qua phải

            j = j - 1               #j qua trái

        else:

            phanDoan = False        #Kết thúc phân đoạn

    return j

def quickSortHoare(a, lo, hi):

    if lo < hi:

        p = partitionHoare(a, lo, hi)

        quickSortHoare(a, lo, p)

        quickSortHoare(a, p+1, hi)

data = [8, 7, 2, 1, 0, 9, 6]

print("Dãy ban đầu a:")

print(data)

size = len(data)

quickSortHoare(data, 0, size - 1)

print('Dãy được sắp xếp:')

print(data)