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

đoàn việt cường Ngày: 30-08-2023 Lớp 11

174

Với giải Luyện tập trang 45 Chuyên đề Tin học 11 Cánh diều chi tiết trong Bài 4: Kĩ thuật chia để trị trong thuật toán sắp xếp trộn giúp học sinh dễ dàng xem và so sánh lời giải, từ đó biết cách làm bài tập Chuyên đề Tin học 11. Mời các bạn đón xem:

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

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

}