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

Em chia đôi dãy gồm bốn số {7, 3, 8, 2} làm hai nửa để thực hiện công việc sắp xếp bốn số này theo thứ tự tăng dần của giá trị: 7 3 8 2->3 7 2 8 ->2 3 7 8

Giai đoạn I: Ở giai đoạn này. với mỗi lượt, mỗi dãy được chia làm hai dây nhỏ với mục tiêu sắp xếp tăng dần trên từng dãy nhỏ hình 1). Quá trình kết thúc khi mỗi

Lượt 1:  Chia thành hai dãy, một dãy 2 bạn (Thi, An) và một dãy 3 bạn (Hoa, Lâm, Mai).

Lượt 2: Chia mỗi đây trong hai dây trên thành hai dãy nhỏ. lần hượt lá: (Thi), (An) (Hoa) và (Lâm, Mai).

Lượt 3: Chia dãy (Lâm, Mai) thành hai đây mỗi dãy có đúng một bạn: (Lâm), (Mai)

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

// Code from https://nguyenvanhieu.vn

#include<stdlib.h>

#include<stdio.h>

// Gộp hai mảng con arr[l...m] và arr[m+1..r]

void merge(int arr[], int l, int m, int r)

{

    int i, j, k;

    int n1 = m - l + 1;

    int n2 =  r - m;

    /* Tạo các mảng tạm */

    int L[n1], R[n2];

    /* Copy dữ liệu sang các mảng tạm */

    for (i = 0; i < n1; i++)

        L[i] = arr[l + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[m + 1+ j];

    /* Gộp hai mảng tạm vừa rồi vào mảng arr*/

    i = 0; // Khởi tạo chỉ số bắt đầu của mảng con đầu tiên

    j = 0; // Khởi tạo chỉ số bắt đầu của mảng con thứ hai

    k = l; // IKhởi tạo chỉ số bắt đầu của mảng lưu kết quả

    while (i < n1 && j < n2)

    {

        if (L[i] <= R[j])

        {

            arr[k] = L[i];

            i++;

        }

        else

        {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

    /* Copy các phần tử còn lại của mảng L vào arr nếu có */

    while (i < n1)

    {

        arr[k] = L[i];

        i++;

        k++;

    }

    /* Copy các phần tử còn lại của mảng R vào arr nếu có */

    while (j < n2)

    {

        arr[k] = R[j];

        j++;

        k++;

    }

} 

/* l là chỉ số trái và r là chỉ số phải của mảng cần được sắp xếp */

void mergeSort(int arr[], int l, int r)

{

    if (l < r)

    {

        // Tương tự (l+r)/2, nhưng cách này tránh tràn số khi l và r lớn

        int m = l+(r-l)/2;

        // Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng

        mergeSort(arr, l, m);

        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);

    }

}

/* Hàm xuất mảng */

void printArray(int A[], int size)

{

    int i;

    for (i=0; i < size; i++)

        printf("%d ", A[i]);

    printf("\n");

}

int main()

{

    int arr[] = {12, 11, 13, 5, 6, 7};

    int arr_size = sizeof(arr)/sizeof(arr[0]);

    printf("Given array is \n");

    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");

    printArray(arr, arr_size);

    return 0;

}// Code from https://nguyenvanhieu.vn

#include<stdlib.h>

#include<stdio.h>

// Gộp hai mảng con arr[l...m] và arr[m+1..r]

void merge(int arr[], int l, int m, int r)

{

    int i, j, k;

    int n1 = m - l + 1;

    int n2 =  r - m;

    /* Tạo các mảng tạm */

    int L[n1], R[n2];

    /* Copy dữ liệu sang các mảng tạm */

    for (i = 0; i < n1; i++)

        L[i] = arr[l + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[m + 1+ j];

    /* Gộp hai mảng tạm vừa rồi vào mảng arr*/

    i = 0; // Khởi tạo chỉ số bắt đầu của mảng con đầu tiên

    j = 0; // Khởi tạo chỉ số bắt đầu của mảng con thứ hai

    k = l; // IKhởi tạo chỉ số bắt đầu của mảng lưu kết quả

    while (i < n1 && j < n2)

    {

        if (L[i] <= R[j])

        {

            arr[k] = L[i];

            i++;

        }

        else

        {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

    /* Copy các phần tử còn lại của mảng L vào arr nếu có */

    while (i < n1)

    {

        arr[k] = L[i];

        i++;

        k++;

    }

    /* Copy các phần tử còn lại của mảng R vào arr nếu có */

    while (j < n2)

    {

        arr[k] = R[j];

        j++;

        k++;

    }

}

/* l là chỉ số trái và r là chỉ số phải của mảng cần được sắp xếp */

void mergeSort(int arr[], int l, int r)

{

    if (l < r)

    {

        // Tương tự (l+r)/2, nhưng cách này tránh tràn số khi l và r lớn

        int m = l+(r-l)/2;

        // Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng

        mergeSort(arr, l, m);

        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);

    }

}

/* Hàm xuất mảng */

void printArray(int A[], int size)

{

    int i;

    for (i=0; i < size; i++)

        printf("%d ", A[i]);

    printf("\n");

}

int main()

{

    int arr[] = {12, 11, 13, 5, 6, 7};

    int arr_size = sizeof(arr)/sizeof(arr[0]);

    printf("Given array is \n");

    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");

    printArray(arr, arr_size);

    return 0;

}