Hướng dẫn giải nhanh Tin học 11 định hướng Khoa học máy tính Cánh diều bài 8: Lập trình một số thuật toán sắp xếp

KHỞI ĐỘNG

Câu hỏi: 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.

Hướng dẫn trả lời:

- Sắp xếp nổi bọt

=> Ưu điểm:

• Là một thuật toán cơ bản, dễ hiểu, phù hợp cho người mới bắt đầu tìm hiểu về sắp xếp.

• Mã nguồn ngắn gọn, dễ nhớ.

- Sắp xếp chèn tuyến tính

=> Ưu điểm:

• Thực hiện thao tác đơn giản, dễ hiểu.

• Hiệu quả đối với các tập dữ liệu nhỏ.

• Trong các tình huống thực tế, Insertion Sort thường hiệu quả hơn so với các thuật toán có độ phức tạp O(n^2) khác (như Bubble sort).

• Là lựa chọn tốt khi dữ liệu đã sắp xếp trước đó.

• Đảm bảo tính ổn định, không thay đổi nhiều vị trí ban đầu của các phần tử.

• Thuật toán này có phương pháp cụ thể, tuân theo nguyên tắc riêng, dễ nhớ và sử dụng.

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.

Hướng dẫn trả lời:

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 như sau:

Vòng lặp for ở bên ngoài quản lý việc thực hiện chính xác n-1 bước. Trong khi đó, vòng lặp while lồng bên trong thực hiện đồng thời hai tác vụ a) và b), bằng cách di chuyển từng bước từ vị trí i đến vị trí k+1 theo hướng sang trái.

THỰC HÀNH

Nhiệm vụ 1: 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.

Hướng dẫn trả lời:

Gợi ý chương trình Python thực hiện thuật toán sắp xếp nổi bọt:

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]

#Thực thi đoạn mã
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
for i in range(len(arr)):
    print("%d" % arr[i], end=" ")

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.

Hướng dẫn trả lời:

Gợi ý 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:

void Insertion_Sort(int a[], int n){

int pos, i;

int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử

for(i=1; i<n; i++){//đoạn a[0] đã sắp xếp

x = a[i]; pos = i-1;

//tìm vị trí chèn x

while((pos>=0)&&(a[pos]>x)){

//kết hợp dời chỗ các phần tử sẽ đứng sau x trong danh sách mới

a[pos+1] = a[pos];

pos--;

}

a[pos+1] = x;//chèn x vào danh sách

}

}

void main()

{

int a[5] = {8, 4, 1, 6, 5};

Insertion_Sort(a, 5);

cout<<"Mang sau khi sap xep:"<<endl;

for(int i=0;i<5;i++){

cout<<a[i]<<" ";

}

system("pause");

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

Hướng dẫn trả lời:

Gợi ý chương trình sắp xếp Bảng điểm theo điểm môn Tin học giảm dần:

   #include <stdio.h>

#define GIOI "\nXep loai gioi"

#define KHA "\nXep loai kha"

#define TB "\nXep loai trung binh"

#define YEU "\nXep loai yeu"

/*

    Format code: Alt + Shift + F

*/

int main()

{

    // Nhập điểm 3 môn

    float diemToan;

    float diemVan;

    float diemAnh;

    float dtb;

    printf("\nNhap diem toan = ");

    scanf("%f", &diemToan);

    printf("\nNhap diem van = ");

    scanf("%f", &diemVan);

    printf("\nNhap diem anh = ");

    scanf("%f", &diemAnh);

    dtb = (diemToan + diemVan + diemAnh) / 3;

    printf("\nDTB = %.2f", dtb);

    if (dtb < 4)

    {

        printf(YEU);

    }else if (dtb < 6.5){

        printf(TB);

    }else if(dtb < 8.0){

        printf(KHA);

    }else{

        printf(GIOI);

    }

}

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?

Hướng dẫn trả lời:

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

- Thuật toán sắp xếp chèn thực hiện việc chèn một phần tử vào một mảng đã được sắp xếp trước đó. Với mỗi phần tử trong mảng, nó so sánh phần tử đó với các phần tử đã được sắp xếp trước đó và sau đó chèn phần tử đó vào vị trí thích hợp trong mảng. Điều này yêu cầu ít phép so sánh hơn so với thuật toán sắp xếp nổi bọt, do đó thuật toán sắp xếp chèn có hiệu suất tốt hơn khi sắp xếp một mảng lớn.

- Trong khi đó, thuật toán sắp xếp nổi bọt yêu cầu thực hiện nhiều phép so sánh hơn và có thể không hiệu quả khi sắp xếp mảng lớn. Thuật toán này hoạt động bằng cách so sánh các cặp phần tử liên tiếp trong mảng và đổi chỗ chúng nếu chúng không được sắp xếp đúng thứ tự. Vì vậy, trong nhiều trường hợp, thuật toán sắp xếp chèn được ưa chuộng hơn do tính đơn giản và hiệu suất của nó.