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