কিভাবে C# ব্যবহার করে মার্জ সর্ট সঞ্চালন করবেন?

Merge Sort হল একটি সাজানোর অ্যালগরিদম যা divide and conquer পদ্ধতি ব্যবহার করে৷ এটি অ্যারেটিকে দুটি অংশে বিভক্ত করে এবং তারপর এই দুটি অংশের প্রতিটির জন্য কল করে। অ্যারে সাজানো না হওয়া পর্যন্ত এই প্রক্রিয়াটি অব্যাহত থাকে।

একটি প্রোগ্রাম যা 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() ফাংশনটিকে অ্যারেতে মার্জ সাজানোর জন্য বলা হয়। এর জন্য কোড স্নিপেট নিম্নরূপ দেওয়া হয়েছে।

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() বলা হয় যা এই সাব-অ্যারেগুলিকে একত্রিত করে। এর জন্য কোড স্নিপেট নিম্নরূপ দেওয়া হয়েছে।

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