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 Cánh diều Bài 4: Kĩ thuật chia để trị trong thuật toán sắp xếp trộn

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

}