Làm thế nào để thực hiện Merge Sort bằng C #?

Merge Sort là một thuật toán sắp xếp sử dụng phương pháp chia để trị. Nó chia mảng thành hai phần và sau đó gọi chính nó cho mỗi phần trong số hai phần này. Quá trình này được tiếp tục cho đến khi mảng được sắp xếp.

Một chương trình thể hiện sắp xếp hợp nhất trong C # được đưa ra như sau -

Ví dụ

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] + " ");
         }
      }
   }
}

Đầu ra

Kết quả của chương trình trên như sau.

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

Bây giờ chúng ta hãy hiểu chương trình trên.

Trong hàm main (), đầu tiên mảng ban đầu được hiển thị. Sau đó, hàm mergeSort () được gọi để thực hiện sắp xếp hợp nhất trên mảng. Đoạn mã cho điều này được đưa ra như sau.

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

Trong hàm mergeSort (), q được tính là điểm giữa của mảng. Sau đó, mergeSort () được gọi trên cả hai mảng con đã tạo. Cuối cùng, merge () được gọi là hợp nhất các mảng con này. Đoạn mã cho điều này được đưa ra như sau.

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

Trong hàm merge (), hai mảng con được sắp xếp được cung cấp. Hàm này về cơ bản hợp nhất các mảng con này thành một mảng duy nhất theo cách mà mảng kết quả cũng được sắp xếp. Đoạn mã cho điều này được đưa ra như sau.

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++;
}