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ữ). Thầy giáo chủ nhiệm chọn ra n bạn nam có chiều cao A0, A1,...An-1, đứng thành một hàng ngang và n bạn nữ có chiều cao B0, B1,...Bn-1 đứng thành một hàng ngang để ghép thành nở cặp (nam. nữ). Để tiện ghép cặp, thầy giáo sắp xếp lại vị trí đứng các bạn nam trong hàng theo thứ tự chiều cao tăng dần và vị trí đứng các bạn nữ trong hàng cũng theo thứ tự chiều cao tăng dần. Sau đó thầy giáo tiến hành ghép cặp bạn nam thấp nhất với bạn nữ thấp nhất, bạn nam thấp thứ hai với bạn nữ thấp thứ hai và cứ như vậy đến bạn nam cao nhất với bạn nữ cao nhất. Em hãy viết chương trình áp dựng thuật toán sắp xếp trộn đề giúp thầy giáo thực hiện công việc ghép cặp này.

Chương trình cần nhập vào một số nguyên n, tiếp theo nhập vào n giá trị A0, A1, An-1 và n giá trị B0, B1, Bn-1 Chương trình cần in ra n cặp số Ai, Bj (0<i, j <n-1) là cách xếp cặp (nam, nữ) theo mong muốn của thầy giáo ở trên.

// 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;

}