Giải SGK Tin học 11 Cánh diều Bài 8. Lập trình một số thuật toán sắp xếp có đáp án

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

=> Ưu điểm:

• 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

=> Ưu điểm:

• Thao tác thực hiện đơn giản, dễ hiểu.
• Thể hiện sự hiệu quả cao đối với các số liệu nhỏ.
• Tại các tình huống thực tế, Insertion Sort tỏ ra hiệu quả hơn so với các thuật toán có độ phức tạp �(�2)O(n2) khác (ví dụ Bubble sort).
• Rất phù hợp đối với các số liệu đã được sắp xếp theo thứ tự sẵn.
• Tính ổn định, không làm thay đổi nhiều thứ tự các nguyên tố gốc.
• Cách sắp xếp có tính phương pháp, tuân theo nguyên tắc cụ thể, dễ nhớ và sử dụng.

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:

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

Viết chương trình Phython 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=" ")

 #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);

    }

}