একটি উপাদান সেট দেওয়া আছে। আমাদের বের করতে হবে কোন পারমুটেশন (permutation) মার্জ সর্টের ওৰ্স্ট কেস তৈরি করবে। আসিম্পটটিক্যালি মার্জ সর্ট সবসময় O(n log n) টাইম নেয়, কিন্তু কিছু কেসে অধিক তুলনা (comparison) দরকার হয় এবং বেশি সময় নেয়। এখানে এমন একটি পারমুটেশন বের করতে হবে যা সাধারণ মার্জ সর্ট অ্যালগরিদমে অধিক তুলনা দাবি করবে।
ইনপুট যদি [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]。
সমাধান পদ্ধতি
merge()ফাংশন ডিফাইন করা হয়: arr, left, right, l_index, m_index, r_index নেয়। left এবং right অ্যারে থেকে arr-এ মার্জ করে।divide()ফাংশন ডিফাইন করা হয়: arr, left, right, l_index, m_index, r_index নেয়। arr-কে অল্টারনেট করে left এবং right-এ ভাগ করে (left[i]=arr[i*2], right[i]=arr[i*2+1])।gen_worst_seq()ফাংশন ডিফাইন করা হয়: arr[], l_index, r_index নেয়। l_index < r_index হলে m_index বের করে left এবং right অ্যারে বানায়। divide() কল করে, বাম ও ডান পার্টের জন্য রিকার্সিভলি gen_worst_seq() কল করে, শেষে merge() কল করে।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
void display(int A[], int size) {
for (int i = 0; i < size; i++)
cout << A[i] << " ";
cout << endl;
}
void merge(int arr[], int left[], int right[], int l_index, int m_index, int r_index) {
int i;
for (i = 0; i <= m_index - l_index; i++)
arr[i] = left[i];
for (int j = 0; j < r_index - m_index; j++)
arr[i + j] = right[j];
}
void divide(int arr[], int left[], int right[], int l_index, int m_index, int r_index) {
for (int i = 0; i <= m_index - l_index; i++)
left[i] = arr[i * 2];
for (int i = 0; i < r_index - m_index; i++)
right[i] = arr[i * 2 + 1];
}
void gen_worst_seq(int arr[], int l_index, int r_index) {
if (l_index < r_index) {
int m_index = l_index + (r_index - l_index) / 2;
int left[m_index - l_index + 1];
int right[r_index - m_index];
divide(arr, left, right, l_index, m_index, r_index);
gen_worst_seq(left, l_index, m_index);
gen_worst_seq(right, m_index + 1, r_index);
merge(arr, left, right, l_index, m_index, r_index);
}
}
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]);
gen_worst_seq(arr, 0, n - 1);
display(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
