จะทำการ Merge Sort โดยใช้ C # ได้อย่างไร?

Merge Sort คืออัลกอริธึมการเรียงลำดับที่ใช้วิธีการแบ่งและพิชิต มันแบ่งอาร์เรย์ออกเป็นสองส่วนแล้วเรียกตัวเองว่าแต่ละส่วนทั้งสองส่วน กระบวนการนี้จะดำเนินต่อไปจนกว่าจะจัดเรียงอาร์เรย์

โปรแกรมที่แสดงการเรียงลำดับการผสานใน C# มีดังต่อไปนี้ -

ตัวอย่าง

using System;
namespace QuickSortDemo {
   class Example {
      static public void merge(int[] arr, int p, int q, int r) {
         int i, j, k;
         int n1 = q - p + 1;
         int n2 = r - q;
         int[] L = new int[n1];
         int[] R = new int[n2];
         for (i = 0; i < n1; i++) {
            L[i] = arr[p + i];
         }
         for (j = 0; j < n2; j++) {
            R[j] = arr[q + 1 + j];
         }
         i = 0;
         j = 0;
         k = p;
         while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
               arr[k] = L[i];
               i++;
            } else {
               arr[k] = R[j];
               j++;
            }
            k++;
         }
         while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
         }
         while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
         }
      }
      static public void mergeSort(int[] arr, int p, int r) {
         if (p < r) {
            int q = (p + r) / 2;
            mergeSort(arr, p, q);
            mergeSort(arr, q + 1, r);
            merge(arr, p, q, r);
         }
      }
      static void Main(string[] args) {
         int[] arr = {76, 89, 23, 1, 55, 78, 99, 12, 65, 100};
         int n = 10, i;
         Console.WriteLine("Merge Sort");
         Console.Write("Initial array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
         mergeSort(arr, 0, n-1);
         Console.Write("\nSorted Array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
      }
   }
}

ผลลัพธ์

ผลลัพธ์ของโปรแกรมข้างต้นมีดังนี้

Merge Sort
Initial array is: 76 89 23 1 55 78 99 12 65 100
Sorted Array is: 1 12 23 55 65 76 78 89 99 100

ตอนนี้ให้เราเข้าใจโปรแกรมข้างต้น

ในฟังก์ชัน main() อันดับแรกจะแสดงอาร์เรย์เริ่มต้น จากนั้น ฟังก์ชัน mergeSort() จะถูกเรียกให้ทำการ merge sort ในอาร์เรย์ ข้อมูลโค้ดสำหรับสิ่งนี้มีดังต่อไปนี้

int[] arr = {76, 89, 23, 1, 55, 78, 99, 12, 65, 100};
int n = 10, i;
Console.WriteLine("Merge Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}
mergeSort(arr, 0, n-1);

ในฟังก์ชัน mergeSort() q จะถูกคำนวณเป็นจุดกึ่งกลางของอาร์เรย์ จากนั้น mergeSort() จะถูกเรียกในอาร์เรย์ย่อยทั้งสองที่สร้าง ในที่สุด merge() จะถูกเรียกที่รวม sub-array เหล่านี้เข้าด้วยกัน ข้อมูลโค้ดสำหรับสิ่งนี้มีดังต่อไปนี้

if (p < r) {
   int q = (p + r) / 2;
   mergeSort(arr, p, q);
   mergeSort(arr, q + 1, r);
   merge(arr, p, q, r);
}

ในฟังก์ชัน merge() จะมีอาร์เรย์ย่อยที่จัดเรียงไว้สองชุด ฟังก์ชันนี้โดยทั่วไปจะรวมอาร์เรย์ย่อยเหล่านี้เป็นอาร์เรย์เดียวในลักษณะที่อาร์เรย์ผลลัพธ์จะถูกจัดเรียงด้วย ข้อมูลโค้ดสำหรับสิ่งนี้มีดังต่อไปนี้

int i, j, k;
int n1 = q - p + 1;
int n2 = r - q;
int[] L = new int[n1];
int[] R = new int[n2];
for (i = 0; i < n1; i++) {
   L[i] = arr[p + i];
}
for (j = 0; j < n2; j++) {
   R[j] = arr[q + 1 + j];
}
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
   if (L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
   } else {
      arr[k] = R[j];
      j++;
   }
   k++;
}
while (i < n1) {
   arr[k] = L[i];
   i++;
   k++;
}
while (j < n2) {
   arr[k] = R[j];
   j++;
   k++;
}
while (j < n2) {
   arr[k] = R[j];
   j++;
   k++;
}