[Wiki] Sort cơ bản 2 - Merge Sort - Sắp xếp trộn

Tiếp theo với Merge sort.

Coi video này để lấy ý tưởng về Merge sort

Code lại bằng C++ [Code by @minh_vu_03]

/*
Merge Sort is a Divide and Conquer algorithm.
It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
See following C implementation for details.

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)
*/

#include <iostream>
using namespace std;

void PrintArray(int * arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void Merge(int * arr, int left, int mid, int right)
{
    int * arrLeft = new int[mid - left + 1];
    int * arrRight = new int[right - mid];
    if (!arrLeft || !arrRight)
    {
        if (arrLeft)
            delete [] arrLeft;
        if (arrRight)
            delete [] arrRight;
        
        return;
    }

    int arrIndex = left;
    for (int i = 0; i < mid - left + 1; i++)
        arrLeft[i] = arr[arrIndex++];
    for (int i = 0; i < right - mid; i++)
        arrRight[i] = arr[arrIndex++];
    
    arrIndex = left;
    int leftIndex = 0;
    int rightIndex = 0;

    while (leftIndex < mid - left + 1 && rightIndex < right - mid)
    {
        if (arrLeft[leftIndex] <= arrRight[rightIndex])
        {
            arr[arrIndex] = arrLeft[leftIndex];
            leftIndex++;
        }
        else
        {
            arr[arrIndex] = arrRight[rightIndex];
            rightIndex++;
        }
        arrIndex++;
    }

    while (leftIndex < mid - left + 1)
    {
        arr[arrIndex] = arrLeft[leftIndex];
        leftIndex++;
        arrIndex++;
    }

    while (rightIndex < right - mid)
    {
        arr[arrIndex] = arrRight[rightIndex];
        rightIndex++;
        arrIndex++;
    }

    if (arrLeft)
        delete [] arrLeft;
    if (arrRight)
        delete [] arrRight;
}

void MergeSort(int * arr, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        Merge(arr, left, mid, right);
    }
}

void MergeSort(int * arr, int n)
{
    MergeSort(arr, 0, n - 1);
}

int main()
{
    int arr[] = { 1, 5, 2, 3, 7, 4, 9 };
    int n = sizeof(arr) / sizeof(int);

    PrintArray(arr, n);
    MergeSort(arr, n);
    PrintArray(arr, n);

    return 0;
}

Độ phức tạp

Thời gian chạy: O(nlogn)
Bộ nhớ: N
4 Likes
/*
Merge Sort is a Divide and Conquer algorithm.
It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
See following C implementation for details.

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)
*/

#include <iostream>
using namespace std;

void PrintArray(int * arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void Merge(int * arr, int left, int mid, int right)
{
    int * arrLeft = new int[mid - left + 1];
    int * arrRight = new int[right - mid];
    if (!arrLeft || !arrRight)
    {
        if (arrLeft)
            delete [] arrLeft;
        if (arrRight)
            delete [] arrRight;
        
        return;
    }

    int arrIndex = left;
    for (int i = 0; i < mid - left + 1; i++)
        arrLeft[i] = arr[arrIndex++];
    for (int i = 0; i < right - mid; i++)
        arrRight[i] = arr[arrIndex++];
    
    arrIndex = left;
    int leftIndex = 0;
    int rightIndex = 0;

    while (leftIndex < mid - left + 1 && rightIndex < right - mid)
    {
        if (arrLeft[leftIndex] <= arrRight[rightIndex])
        {
            arr[arrIndex] = arrLeft[leftIndex];
            leftIndex++;
        }
        else
        {
            arr[arrIndex] = arrRight[rightIndex];
            rightIndex++;
        }
        arrIndex++;
    }

    while (leftIndex < mid - left + 1)
    {
        arr[arrIndex] = arrLeft[leftIndex];
        leftIndex++;
        arrIndex++;
    }

    while (rightIndex < right - mid)
    {
        arr[arrIndex] = arrRight[rightIndex];
        rightIndex++;
        arrIndex++;
    }

    if (arrLeft)
        delete [] arrLeft;
    if (arrRight)
        delete [] arrRight;
}

void MergeSort(int * arr, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        Merge(arr, left, mid, right);
    }
}

void MergeSort(int * arr, int n)
{
    MergeSort(arr, 0, n - 1);
}

int main()
{
    int arr[] = { 1, 5, 2, 3, 7, 4, 9 };
    int n = sizeof(arr) / sizeof(int);

    PrintArray(arr, n);
    MergeSort(arr, n);
    PrintArray(arr, n);

    return 0;
}
3 Likes

Ai test dùm code @minh_vu_03 viết rồi sửa post 1 bỏ vào phần code luôn đi :smile:

I moved 2 posts to a new topic: [Wiki] Sort cơ bản 3 - Quick Sort

Em cập nhật lại độ phức tạp nhé @minh_vu_03 :+1:

Em đã học độ phức tạp gì đâu. Nghe người ta nói vậy em bắt chước nói theo thế thôi :grin:

1 Like

@Gio đã cập nhật rồi. Cảm ơn @minh_vu_03@Gio nhé :+1:

Đạt ủng hộ video
@Gio cho cái độ phức tạp
@minh_vu_03 cho cái code

Phối hợp rất nhịp nhàng, để đi tìm vài cái videos nữa :trollface: Công việc tìm videos khá là cực nhọc =))

đoạn này mấy biến mid right left nó báo lỗi expression must have a constant value a @ltd ơi :cry:

@nguyenchiemminhvu Please help :slight_smile:

cho nó bằng 1 số cụ thể thì chạy ngon. Nhưng mà mình tưởng mảng 2 chiều mới phải khai báo thêm 1 chiều chứ sao mảng 1 chiều nó cũng báo lỗi nhỉ @@

Code này C++ chứ có phải C đâu bạn :smiley:

int * arrLeft = new int[mid - left + 1];
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?