পুনরাবৃত্তিমূলক মার্জ সাজানোর জন্য সি প্রোগ্রাম

বিভাজন এবং বিজয় কৌশলের উপর ভিত্তি করে সাজানোর অ্যালগরিদম কী তা মার্জ করুন। মার্জ সাজানোর সময় জটিলতা হল O(n log n)। অ্যালগরিদম প্রথমে অ্যারেটিকে সমান অর্ধে ভাগ করে এবং তারপর একটি নির্দিষ্ট পদ্ধতিতে একত্রিত করে।

পুনরাবৃত্ত মার্জ বাছাই

পুনরাবৃত্তিমূলক মার্জ সাজানোর ক্ষেত্রে, আমরা একটি পুনরাবৃত্ত পদ্ধতি ব্যবহার করে উপাদানগুলিকে সমান অর্ধে ভাগ করব এবং তারপরে পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করে একটি সাজানো অ্যারে হিসাবে সেগুলিকে আবার মার্জ করব৷

পুনরাবৃত্ত মার্জ সাজানোর জন্য প্রোগ্রাম

/* মার্জ সাজানোর জন্য রিকার্সিভ সি প্রোগ্রাম */

উদাহরণ

#include<stdlib.h>
#include<stdio.h>
void merge(int arr[], int l, int m, int r) {
   int i, j, k;
   int n1 = m - l + 1;
   int n2 = r - m;
   int L[n1], R[n2];
   for (i = 0; i < n1; i++)
      L[i] = arr[l + i];
   for (j = 0; j < n2; j++)
      R[j] = arr[m + 1+ j];
   i = 0, j = 0, k = l;
   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++;
   }
}
void iterativeMergeSort(int arr[], int l, int r) {
   if (l < r){
      int mid = l+(r-l)/2;
      iterativeMergeSort(arr, l, mid);
      iterativeMergeSort(arr, mid+1, r);
      merge(arr, l, mid, r);
   }
}
int main(){
   int arr[] = {12, 11, 13, 5, 6, 7};
   int size = sizeof(arr)/sizeof(arr[0]);
   printf("\t\t ITERATIVE MERGE SORT \n");
   printf("Unsorted Array : \t");
   for (int i=0; i < size; i++)
      printf("%d ",arr[i]);
   iterativeMergeSort(arr, 0, size - 1);
   printf("\nSorted array : \t");
   for (int i=0; i < size; i++)
      printf("%d ", arr[i]);
   printf("\n");
   return 0;
}

আউটপুট

ITERATIVE MERGE SORT
Unsorted Array : 12 11 13 5 6 7
Sorted array : 5 6 7 11 12 13