CHỦ ĐỀ F^CS: GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH

BÀI 8: LẬP TRÌNH MỘT SỐ THUẬT TOÁN SẮP XẾP

KHỞI ĐỘNG

Câu 1: Trình quản lí tệp của hệ điều hành cho phép lựa chọn hiển thị nội dung của thư mục được sắp xếp thứ tự theo vài cách khác nhau. Em hãy cho biết một trong số các lựa chọn này và giải thích rõ thêm tiêu chí (yêu cầu) sắp xếp tương ứng.

Giải nhanh:

• Sắp xếp nổi bọt: Là thuật toán cơ bản, dễ hiểu, phù hợp cho người bắt đầu học về sắp xếp; đoạn code ngắn gọn, dễ nhớ.
• Sắp xếp chèn tuyến tính: Thao tác thực hiện đơn giản, dễ hiểu; phù hợp đối với các số liệu đã được sắp xếp theo thứ tự sẵn; có tính ổn định.

HOẠT ĐỘNG

Câu 1: Em hãy thực hiện các công việc sau:

1. Tính số lần lặp của vòng lặp bên trong của thuật toán sắp xếp chèn tuyến tính.
2. Tính số lần lặp của vòng lặp ngoài của thuật toán sắp xếp chèn tuyến tính.
3. Ước lượng độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính.

Giải nhanh:

1. 

2. 

3. Vòng lặp for bên ngoài kiểm soát việc thực hiện đúng n-1 bước. Vòng lặp while lồng bên trong thực hiện đồng thời cùng lúc hai việc a) và b) theo cách dịch chuyển dần từng bước sang trái, từ vị trí i tới vị trí k+1.

THỰC HÀNH

Nhiệm vụ 1: Em hãy viết chương trình Python thực biện thuật toán sắp xếp nổi bọt.

Giải nhanh:

Gợi ý:

def bubbleSort(arr):
    n = len(arr)
    #Duyệt qua tất cả các phần tử
    for i in range(n-1):
        for j in range(0, n-i-1):
            #Hoán đổi phần tử nếu nó lớn hơn phần tử sau nó
            if arr[j] > arr[j + 1] :
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

Nhiệm vụ 2: Em hãy viết chương trình Python thực hiện thuật toán sắp xếp chèn tuyến tính dựa trên mã giả đã cho trong báo học

Giải nhanh:

def sap_xep_chen(arr):

    # Lặp từ phần tử thứ hai đến phần tử cuối cùng

    for i in range(1, len(arr)):

         key = arr[i]  # Lấy phần tử hiện tại

        j = i - 1

      # Di chuyển các phần tử lớn hơn key về phía sau để tạo chỗ trống

       while j >= 0 and arr[j] > key:

            arr[j + 1] = arr[j]

            j -= 1

        # Đặt key vào đúng vị trí

        arr[j + 1] = key

VẬN DỤNG

Câu 1: Cho danh sách Bảng điểm là kết quá học tập gồm các cột Họ và tên, điểm Toán, điểm ngữ văn, điểm Tin bọc... Hãy viết chương trình sắp xếp Bảng điểm theo điểm môn Tin học giảm dần.

Gợi ý: Mỗi phân tử của Bảng điểm là một danh sách con, ứng với một học sinh. So sánh theo thành phân điểm Tin học của danh sách con để sắp xếp.

Giải nhanh:

def sap_xep_theo_diem_tin(bang_diem):

    # Sắp xếp bảng điểm theo điểm Tin học giảm dần, sử dụng hàm sorted với key là điểm Tin học

    bang_diem_sap_xep = sorted(bang_diem, key=lambda x: x[3], reverse=True)

    return bang_diem_sap_xep

CÂU HỎI TỰ KIỂM TRA

Câu 1: Theo em, thuật toán sắp xếp nổi bọt và thuật toán sắp xếp chèn, thuật toán nào đơn giản và để cài đặt hơn?

Giải nhanh:

Cả hai thuật toán sắp xếp nổi bọt và sắp xếp chèn đều đơn giản và dễ cài đặt. Tuy nhiên, thuật toán sắp xếp chèn có thể được coi là đơn giản hơn vì nó sử dụng ít phép so sánh hơn so với thuật toán sắp xếp nổi bọt.