การเรียงลำดับแบบ Merge Sort และการประยุกต์ใช้ในภาษา C++

Merge Sort คืออะไร?

Merge Sort เป็นหนึ่งใน algorithm สำหรับการเรียงลำดับข้อมูลที่มีความเร็วและมีประสิทธิภาพสูง ซึ่งหลักการทำงานของมันคือ "แบ่งแล้วเรียง" (Divide and Conquer). Algorithm นี้จะเริ่มต้นด้วยการแบ่งข้อมูลออกเป็นกลุ่มย่อยๆ จนแต่ละกลุ่มมีข้อมูลเพียง 1 หรือไม่มีข้อมูลเลย หลังจากนั้นจะค่อยๆ รวมกลุ่มย่อยเหล่านี้กลับเข้าด้วยกันพร้อมทั้งเรียงลำดับขณะที่รวม จนได้กลุ่มข้อมูลที่เรียงลำดับครบถ้วน

การนำไปใช้งาน Merge Sort

Merge Sort สามารถนำไปใช้ได้ในหลายสถานการณ์ เช่น การเรียงลำดับข้อมูลในฐานข้อมูลขนาดใหญ่, การจัดเรียงไฟล์พื้นฐาน, หรือแม้กระทั่งใช้เรียงลำดับีการทำงานของเขตข้อมูลในงานวิจัยต่างๆ

ตัวอย่างการนำไปประยุกต์ใน Code ภาษา C++:

#include

// ประกาศฟังก์ชัน Merge ที่ใช้รวมข้อมูลหลังจากทำการแบ่ง
void Merge(int *a, int low, int high, int mid)
{
    int i, j, k, temp[high-low+1];
    i = low;
    k = 0;
    j = mid + 1;

    // รวมข้อมูลที่เรียงลำดับแล้วกลับเข้าด้วยกัน
    while (i <= mid && j <= high)
    {
        if (a[i] < a[j])
        {
            temp[k] = a[i];
            k++;
            i++;
        }
        else
        {
            temp[k] = a[j];
            k++;
            j++;
        }
    }

    // ถ้าเหลือข้อมูลในอาเรย์ที่ยังไม่ได้เรียงลำดับ
    while (i <= mid)
    {
        temp[k] = a[i];
        k++;
        i++;
    }

    while (j <= high)
    {
        temp[k] = a[j];
        k++;
        j++;
    }

    // โอนข้อมูลจาก temp[] กลับไปยัง a[]
    for (i = low; i <= high; i++)
    {
        a[i] = temp[i-low];
    }
}

// ประกาศฟังก์ชัน MergeSort ที่ใช้สำหรับการแบ่งข้อมูล
void MergeSort(int *a, int low, int high)
{
    int mid;
    if (low < high)
    {
        mid=(low+high)/2;
        MergeSort(a, low, mid);
        MergeSort(a, mid+1, high);

        Merge(a, low, high, mid);
    }
}

int main()
{
    int n, i;
    std::cout<<"Please enter the number of elements: ";
    std::cin>>n;
    int arr[n];
    for(i = 0; i < n; i++)
    {
        std::cout<<"Enter element "<<(i+1)<<": ";
        std::cin>>arr[i];
    }

    MergeSort(arr, 0, n-1);

    // แสดงผลข้อมูลที่เรียงลำดับแล้ว
    std::cout<<"Sorted data: ";
    for (i = 0; i < n; i++)
        std::cout<<" "<