C# में मर्ज सॉर्ट कैसे करें

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

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("मर्ज सॉर्ट"); 
            Console.Write("प्रारंभिक सरणी है: "); 
            for (i = 0; i < n; i++) { 
                Console.Write(arr[i] + " "); 
            } 
            mergeSort(arr, 0, n-1); 
            Console.Write("\nक्रमबद्ध सरणी है: "); 
            for (i = 0; i < n; i++) { 
                Console.Write(arr[i] + " "); 
            } 
        } 
    } 
}

आउटपुट

उपरोक्त प्रोग्राम का आउटपुट निम्नलिखित है।

मर्ज सॉर्ट 
प्रारंभिक सरणी है: 76 89 23 1 55 78 99 12 65 100 
क्रमबद्ध सरणी है: 1 12 23 55 65 76 78 89 99 100

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

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

int[] arr = {76, 89, 23, 1, 55, 78, 99, 12, 65, 100}; 
int n = 10, i; 
Console.WriteLine("मर्ज सॉर्ट"); 
Console.Write("प्रारंभिक सरणी है: "); 
for (i = 0; i < n; i++) { 
    Console.Write(arr[i] + " "); 
} 
mergeSort(arr, 0, n-1);

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

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