C-তে মার্জ সর্টের ওর্স্ট কেসের জন্য পারমিউটেশন জেনারেট করা

একটি সর্টেড অ্যারে দেওয়া আছে। এই উপাদানগুলোর কোন পারমিউটেশন মার্জ সর্টের ওর্স্ট কেস (সর্বোচ্চ তুলনা) তৈরি করবে তা খুঁজে বের করতে হবে। মার্জ সর্ট অ্যাসিম্পটোটিক্যালি O(n log n) কিন্তু প্র্যাক্টিসে তুলনার সংখ্যা বড় হলে সময় বেশি লাগে।

উদাহরণ

সর্টেড অ্যারে: 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

ওর্স্ট কেস ইনপুট: 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26

পদ্ধতি (বটম-আপ)

• সর্টেড অ্যারেতে বাম ও ডান সাবঅ্যারেতে বáriকৃত উপাদান রাখা হয় (যেমন {11,13,15,17} এবং {12,14,16,18}) যাতে মার্জের সময় প্রতিটি উপাদান তুলনা হয়।
• এই লজিক রিকারসিভলি বাম ও ডান সাবঅ্যারেতেও প্রয়োগ করা হয়।
• generateWorstCase() ফাংশনটি split() দিয়ে বাম-ডান বাঁটে, রিকারসিভ কল করে, join() দিয়ে জড়ায়।

C প্রোগ্রাম উদাহরণ

#include <stdlib.h>
#include <stdio.h>

void printArray(int A[], int size) {
    for (int i = 0; i < size; i++) printf("%d ", A[i]);
    printf("\n");
}

int join(int arr[], int left[], int right[], int l, int m, int r) {
    int i;
    for (i = 0; i <= m - l; i++) arr[i] = left[i];
    for (int j = 0; j < r - m; j++) arr[i + j] = right[j];
    return 0;
}

int split(int arr[], int left[], int right[], int l, int m, int r) {
    for (int i = 0; i <= m - l; i++) left[i] = arr[i * 2];
    for (int i = 0; i < r - m; i++) right[i] = arr[i * 2 + 1];
    return 0;
}

int generateWorstCase(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        int left[m - l + 1], right[r - m];
        split(arr, left, right, l, m, r);
        generateWorstCase(left, l, m);
        generateWorstCase(right, m + 1, r);
        join(arr, left, right, l, m, r);
    }
    return 0;
}

int main() {
    int arr[] = {11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("সর্টেড অ্যারে:\n"); printArray(arr, n);
    generateWorstCase(arr, 0, n-1);
    printf("\nওর্স্ট কেস ইনপুট:\n"); printArray(arr, n);
    return 0;
}

আউটপুট

সর্টেড অ্যারে:
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
ওর্স্ট কেস ইনপুট:
11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26