Thầy giáo lớp Thanh An mời 5 bạn học sinh lên bảng, xếp ngẫu nhiên thành một hàng ngang, từ trái sang phải là các bạn có tên Thi, An, Hoà, Lâm, Mai. Em hãy giúp thầy giáo yêu cầu 5 bạn thực hiện lần lượt các bước trong hai giai đoạn sau để sắp xếp hàng tăng dần theo chiều cao từ trái sang phải.

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

}

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