Em hãy cho biết trong mô tả thuật toán sắp xếp trộn và trong chương tình cài đặt

Giải Chuyên đề Tin học 11 Bài 4: Kĩ thuật chia để trị trong thuật toán sắp xếp trộn - Cánh diều

Luyện tập trang 45 Chuyên đề Tin học 11: Em hãy cho biết trong mô tả thuật toán sắp xếp trộn và trong chương tình cài đặt ở trên cần thay đổi thế nào để sắp xếp một dãy theo thứ tự giảm dần của giá trị.

Lời giải:

Các thuật toán sắp xếp đơn giản như Bubble Sort, Insertion Sort . . . đều không thể xử lý được dữ liệu lớn. Thuật toán sắp xếp trộn lấy ý tưởng từ việc chia để trị để chia nhỏ bài toán thành các bài toán nhỏ hơn, sau đó giải quyết chúng. Từ đó sẽ giúp xử lý dữ liệu lớn một cách tốt hơn, tối ưu về mặt thời gian.

Ý tưởng đưa ra như sau:

Chia danh sách gồm n phần tử chưa được sắp xếp thành n danh sách con, mỗi danh sách chứa một phần tử (danh sách một phần tử được coi là đã sắp xếp).

Liên tục hợp nhất các danh sách con để tạo ra các danh sách con được sắp xếp mớ cho đến khi chỉ còn lại một danh sách. Đây sẽ là danh sách được sắp xếp.

Ví dụ:

void Swap(int &a, int &b){

int temp = a;

a = b;

b = temp;

}

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

for (int i = 0; i < n - 1; i++)

for (int j = i + 1; j < n; j++)

if(a[i] > a[j]) //nếu có nghịch thế thì đổi chỗ

Swap(a[i], a[j]);

}

Lời giải Chuyên đề Tin 11 Bài 4: Kĩ thuật chia để trị trong thuật toán sắp xếp trộn hay, ngắn gọn khác:

• Khởi động trang 38 Chuyên đề Tin học 11: Bài 2 giới thiệu kĩ thuật đệ quy trong phương pháp chia để trị. Nhiều bài được giải quyết dễ dàng bằng cách sử dụng kĩ thuật đệ quy ....

• Hoạt động trang 38 Chuyên đề Tin học 11: Thầy giáo lớp Thanh An mời 5 bạn học sinh lên bảng, xếp ngẫu nhiên thành một hàng ngang, từ trái sang phải là các bạn có tên Thi, An, Hoà, Lâm, Mai ....

• Vận dụng trang 45 Chuyên đề Tin học 11: Hội diễn văn nghệ của trường năm nay, lớp Thanh An tham gia biểu diễn khiêu vũ tập thể theo cặp (nam, nữ) ....

• Câu hỏi tự kiểm tra trang 45 Chuyên đề Tin học 11: Trong các câu sau đây, câu nào đúng khi mô tả trình tự các bước cơ bản của phương pháp chia để trị? ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 11 Cánh diều hay, ngắn gọn khác:

• Chuyên đề Tin học 11 Bài 5: Thực hành tổng hợp ứng dụng chia để trị

• Chuyên đề Tin học 11 Bài 1: Kĩ thuật duyệt

• Chuyên đề Tin học 11 Bài 2: Kĩ thuật quay lui

• Chuyên đề Tin học 11 Bài 3: Thực hành kĩ thuật quay lui

• Chuyên đề Tin học 11 Bài 4: Thực hành tổng hợp kĩ thuật duyệt

Xem thêm các tài liệu học tốt lớp 11 hay khác:

• Giải Chuyên đề Tin học 11 Kết nối tri thức
• Giải Chuyên đề Tin học 11 Chân trời sáng tạo
• Giải Chuyên đề Tin học 11 Cánh diều

---