โปรแกรม C++ อัลกอริทึม Merge Sort

Merge Sort

เทคนิคการจัดเรียงแบบ Merge Sort พัฒนามาจากเทคนิคแบ่งแยกและเอาชนะ (divide and conquer technique) เราแบ่งชุดข้อมูลทั้งหมดออกเป็นส่วนย่อยๆ และรวมมันเข้าด้วยกันเป็นชิ้นส่วนที่ใหญ่ขึ้นในลำดับที่จัดเรียงแล้ว มันมีประสิทธิภาพมากสำหรับกรณีแย่ที่สุดด้วย เพราะอัลกอริทึมนี้มีความซับซ้อนด้านเวลาต่ำสำหรับกรณีแย่ที่สุดเช่นกัน

ความซับซ้อนของ Merge Sort

• Time Complexity: O(n log n) สำหรับทุกกรณี

• Space Complexity: O(n)

Input - รายการที่ไม่ได้จัดเรียง: 14 20 78 98 20 45
Output - Array after Sorting: 14 20 20 45 78 98

อัลกอริทึม

merge(array, left, middle, right)

Input: อาร์เรย์ชุดข้อมูล, ดัชนี left, middle และ right

Output: รายการที่รวมแล้ว

เริ่มต้น
  nLeft := m - left + 1
  nRight := right - m
  ประกาศอาร์เรย์ leftArr และ rightArr ขนาด nLeft และ nRight ตามลำดับ
  for i := 0 ถึง nLeft
    leftArr[i] := array[left + i]
  for j := 0 ถึง nRight
    rightArr[j] := array[middle + j + 1]
  i := 0, j := 0, k := left
  while i < nLeft AND j < nRight
    if leftArr[i] <= rightArr[j] then
      array[k] = leftArr[i]
      i := i+1
    else
      array[k] = rightArr[j]
      j := j+1
    k := k+1
  while i < nLeft
    array[k] := leftArr[i]
    i := i+1
    k := k+1
  while j < nRight
    array[k] := rightArr[j]
    j := j+1
    k := k+1
สิ้นสุด

mergeSort(array, left, right)

Input: อาร์เรย์ข้อมูล, และขอบเขตล่างและบนของอาร์เรย์

Output: อาร์เรย์ที่จัดเรียงแล้ว

เริ่มต้น
  if left < right then
    mid := left + (right - left) / 2
    mergeSort(array, left, mid)
    mergeSort(array, mid+1, right)
    merge(array, left, mid, right)
สิ้นสุด

โค้ดตัวอย่าง

#include <iostream>
using namespace std;

void swapping(int &a, int &b) {
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void display(int *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void merge(int *array, int l, int m, int r) {
    int i, j, k, nl, nr;
    nl = m-l+1; nr = r-m;
    int larr[nl], rarr[nr];
    for(i = 0; i < nl; i++)
        larr[i] = array[l+i];
    for(j = 0; j < nr; j++)
        rarr[j] = array[m+1+j];
    i = 0; j = 0; k = l;
    while(i < nl && j < nr) {
        if(larr[i] <= rarr[j]) {
            array[k] = larr[i];
            i++;
        } else {
            array[k] = rarr[j];
            j++;
        }
        k++;
    }
    while(i < nl) {
        array[k] = larr[i];
        i++; k++;
    }
    while(j < nr) {
        array[k] = rarr[j];
        j++; k++;
    }
}

void mergeSort(int *array, int l, int r) {
    if(l < r) {
        int m = l+(r-l)/2;
        mergeSort(array, l, m);
        mergeSort(array, m+1, r);
        merge(array, l, m, r);
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n];
    cout << "Enter elements:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    mergeSort(arr, 0, n-1);
    cout << "Array after Sorting: ";
    display(arr, n);
}

ผลลัพธ์ตัวอย่าง

Enter the number of elements: 6
Enter elements: 14 20 78 98 20 45
Array before Sorting: 14 20 78 98 20 45
Array after Sorting: 14 20 20 45 78 98