सी # का उपयोग कर मर्ज सॉर्ट कैसे करें?

मर्ज सॉर्ट एक सॉर्टिंग एल्गोरिथम है जो डिवाइड एंड कॉनकॉट विधि का उपयोग करता है। यह सरणी को दो भागों में विभाजित करता है और फिर इन दो भागों में से प्रत्येक के लिए स्वयं को कॉल करता है। यह प्रक्रिया तब तक जारी रहती है जब तक कि सरणी क्रमबद्ध नहीं हो जाती।

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

आइए अब उपरोक्त कार्यक्रम को समझते हैं।

मुख्य () फ़ंक्शन में, पहले प्रारंभिक सरणी प्रदर्शित होती है। फिर, फ़ंक्शन मर्जसॉर्ट () को सरणी पर मर्ज सॉर्ट करने के लिए कहा जाता है। इसके लिए कोड स्निपेट इस प्रकार दिया गया है।

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

फ़ंक्शन मर्जसॉर्ट () में, q की गणना सरणी के मध्य बिंदु के रूप में की जाती है। फिर बनाए गए दोनों उप-सरणी पर mergeSort() को कॉल किया जाता है। अंत में, मर्ज () को कहा जाता है जो इन उप-सरणी को मर्ज करता है। इसके लिए कोड स्निपेट इस प्रकार दिया गया है।

if (p < r) {
   int q = (p + r) / 2;
   mergeSort(arr, p, q);
   mergeSort(arr, q + 1, r);
   merge(arr, p, q, 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++;
}
while (j < n2) {
   arr[k] = R[j];
   j++;
   k++;
}