Giải Tin học 11 Bài 8: Lập trình một số thuật toán sắp xếp
Lời giải:
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.
2. Thuật toán sắp xếp nổi bọt (Bubble Sort)
Lời giải:
Nội dung đang được cập nhật
4. Thực hành
Nhiệm vụ 1 trang 125 Tin học 11: 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.
Lời giả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:
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
Nhiệm vụ 2 trang 126 Tin học 11: Viết chương trình Phython thực hiện thuật toán sắp xếp nổi bọt.
Lời giải:
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=" ")
Lời giải:
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:
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
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:"<
for(int i=0;i<5;i++){
cout<
}
system("pause");
Vận dụng
Lời giải:
#include
#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
Lời giải:
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.
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ó sẽ so sánh nó với các phần tử đã được sắp xếp trước đó, và chèn phần tử đó vào vị trí thích hợp trong mảng. Điều này đòi hỏi í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 cần 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. Nó 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 hiệu quả và tính đơn giản của nó.
Xem thêm lời giải bài tập Tin học lớp 11 sách Cánh diều hay, chi tiết khác:
