Bài 8. Lập trình một số thuật toán sắp xếp

Chủ đề F^cs : Giải quyết vấn đề với sự trợ giúp của máy tính – Kĩ thuật lập trình – Bài 8. Lập trình một số thuật toán sắp xếp – sách giáo khoa trang 122 lớp 11 Khoa học máy tính – Cánh Diều, mời các em tham khảo cùng Bumbii.

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

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.

Lời giải:

Một trong những lựa chọn phổ biến khi hiển thị nội dung thư mục là sắp xếp theo tên: Hệ thống sẽ sắp xếp các tệp và thư mục trong thư mục hiện tại theo thứ tự abc, giúp dễ dàng tìm kiếm và quản lý tệp theo tên.

Một số tiêu chí sắp xếp khác cũng có thể bao gồm:

Theo kích thước.
Theo ngày tạo hoặc sửa đổi.
Theo loại.

THỰC HÀNH

Nhiệm vụ 1

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

a) 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.

b) 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.

c) Ướ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.

Lời giải:

a) Số lần lặp của vòng lặp bên trong với bước i sẽ không quá i.

b) Vòng lặp ngoài của thuật toán được thực hiện đúng n – 1 lần.

c) Ước lượng độ phức tạp thời gian thuật toán sắp xếp chèn tuyến tính là O(n²) vì không vượt quá tổng 1 + 2 + … + n – 1.

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 nổi bọt.

Lời giải:

def sxNoiBot(a):
    n = len(a)
    for i in range(n):
        for j in range(0, n-i-1):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
    return a

Nhiệm vụ 3

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.

Lời giải:

def sxChen_TuyenTinh(a):
    for i in range(1, len(a)):
        val = a[i]
        j = i - 1

        while j >= 0 and a[j] > val:
            a[j + 1] = a[j]
            j -= 1

        a[j + 1] = val
    
    return a

VẬN DỤNG

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 họ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.

Lời giải:

def sxChen(a): #chèn tuyến tính
    for i in range(1, len(a)):
        val = a[i][3]
        dsCon = a[i]
        j = i
        i = i + 1
        #dịch dần từng bước, tìm vị trí để chèn
        while (j > 0) and (a[j - 1][3] < val):
            a[j] = a[j - 1]
            j -= 1

        a[j] = dsCon