সুচিপত্র
- ভূমিকা
- C++ এ মার্জ সর্ট কি?
- ডিভাইড অ্যান্ড কঙ্কারের অ্যাপ্রোচ
- সাজানোর অ্যালগরিদম মার্জ করুন
- C++ এ মার্জ সাজানোর বাস্তবায়ন
- উপসংহার
1। পরিচিতি
কম্পিউটার বিজ্ঞানে বাছাই করার অ্যালগরিদমগুলি ঊর্ধ্বমুখী বা অবরোহী ক্রমে ডেটা সাজানোর জন্য ব্যবহৃত হয়। উপলব্ধ স্বতন্ত্র বৈশিষ্ট্য সহ একাধিক বাছাই অ্যালগরিদম আছে. মার্জ সর্ট হল C++ এর একটি পদ্ধতি যা অ্যারে সাজাতে পারে।
2. C++ এ মার্জ সর্ট কি?
মার্জ সর্ট ডিভাইড-এন্ড-কনকার কৌশল ব্যবহার করে যা একটি অ্যারের উপাদানগুলিকে সাজাতে পারে। এটি C++ এ উপাদানের তালিকাও সাজাতে পারে। এটি ইনপুটটিকে দুটি অর্ধে বিভক্ত করে, প্রতিটি অর্ধেক স্বাধীনভাবে সাজায় এবং তারপর সঠিক ক্রমে তাদের একত্রিত করে।
3. বিভক্ত এবং জয় করার পদ্ধতি
বাছাই করার অ্যালগরিদমটি একটি ভাগ-এন্ড-কনকার কৌশল প্রয়োগ করে, যা ইনপুট অ্যারেকে ছোট সাবয়ারেতে বিভাজন করে, আলাদাভাবে সমাধান করে এবং তারপরে একটি সাজানো আউটপুট তৈরি করতে ফলাফলগুলিকে একত্রিত করে। মার্জ সর্টের ক্ষেত্রে, অ্যারেটিকে পুনরাবৃত্তিমূলকভাবে দুটি অর্ধে ভাগ করা হয় যতক্ষণ না প্রতিটি অর্ধে শুধুমাত্র একটি উপাদান অবশিষ্ট থাকে।
4. মার্জ সর্ট অ্যালগরিদম
মার্জ সাজানোর অ্যালগরিদম দুটি প্রধান ধাপ নিয়ে গঠিত: ভাগ এবং একত্রীকরণ। নিম্নরূপ পদক্ষেপ:
4.1 ভাগ করুন
মার্জ সর্ট অ্যালগরিদম একটি অ্যারেতে উপাদানগুলিকে সাজানোর জন্য একটি ভাগ-এন্ড-জয় কৌশল অনুসরণ করে।
- অ্যালগরিদমের প্রথম ধাপটি অ্যারের উপাদানগুলি পরীক্ষা করবে। যদি এটিতে একটি উপাদান থাকে, তাহলে এটি ইতিমধ্যেই সাজানো বলে বিবেচিত হয় এবং অ্যালগরিদম কোনো পরিবর্তন ছাড়াই একই অ্যারে ফিরিয়ে দেবে।
- যদি অ্যারেতে একাধিক উপাদান থাকে, তাহলে অ্যালগরিদম এটিকে দুটি অর্ধে ভাগ করে: বাম অর্ধেক এবং ডান অর্ধেক।
- মার্জ সাজানোর অ্যালগরিদম তারপর অ্যারের বাম এবং ডান অংশে পুনরাবৃত্তিমূলকভাবে প্রয়োগ করা হয়, কার্যকরভাবে তাদের ছোট সাব্যারেতে বিভক্ত করে এবং পৃথকভাবে সাজায়।
- এই পুনরাবৃত্ত প্রক্রিয়াটি চলতে থাকে যতক্ষণ না সাবয়ারের প্রতিটিতে শুধুমাত্র একটি উপাদান থাকে (পদক্ষেপ 1 অনুসারে), এই সময়ে তারা একটি চূড়ান্ত, সাজানো আউটপুট অ্যারে তৈরি করতে একত্রিত হতে পারে।
4.2 একত্রিত করুন
এখন আমরা অ্যারেগুলিকে একত্রিত করার পদক্ষেপগুলি দেখতে পাব:
- মার্জ সাজানোর অ্যালগরিদমের প্রথম ধাপে একটি খালি অ্যারে তৈরি করা জড়িত।
- অ্যালগরিদম তারপর ইনপুট অ্যারের বাম এবং ডান অর্ধাংশের প্রথম উপাদানগুলির তুলনা করতে এগিয়ে যায়।
- দুটি উপাদানের মধ্যে ছোটটি নতুন অ্যারেতে যোগ করা হয় এবং তারপরে ইনপুট অ্যারের নিজ নিজ অর্ধেক থেকে সরানো হয়।
- ধাপ 2-3 তারপর পুনরাবৃত্তি করা হয় যতক্ষণ না একটি অর্ধেক খালি হয়।
- অ-খালি অর্ধেক অবশিষ্ট যে কোনো উপাদান তারপর নতুন অ্যারে যোগ করা হয়.
- ফলস্বরূপ অ্যারে এখন সম্পূর্ণভাবে সাজানো হয়েছে এবং মার্জ সাজানোর অ্যালগরিদমের চূড়ান্ত আউটপুটকে উপস্থাপন করে।
5. C++ এ মার্জ সাজানোর বাস্তবায়ন
C++ এ মার্জ সাজানোর জন্য দুটি ভিন্ন পদ্ধতি অনুসরণ করা হয়। উভয় পদ্ধতির সময় জটিলতা সমতুল্য, কিন্তু অস্থায়ী সাব্যারেগুলির ব্যবহার ভিন্ন।
C++-এ মার্জ সাজানোর প্রথম পদ্ধতি দুটি অস্থায়ী সাবারে ব্যবহার করে, যখন দ্বিতীয়টি শুধুমাত্র একটি ব্যবহার করে। এটি লক্ষণীয় যে প্রথম পদ্ধতিতে দুটি অস্থায়ী সাবয়ারের মোট আকার দ্বিতীয় পদ্ধতিতে মূল অ্যারের আকারের সমান, তাই স্থান জটিলতা স্থির থাকে।
পদ্ধতি 1 - দুটি টেম্প সাবারে ব্যবহার করা
পদ্ধতি 1 ব্যবহার করে C++ এ মার্জ সাজানোর জন্য এখানে একটি উদাহরণ প্রোগ্রাম রয়েছে, যা দুটি অস্থায়ী সাব্যারে ব্যবহার করে:
# অন্তর্ভুক্ত করুননামস্থান std ব্যবহার করে ;
অকার্যকর একত্রিত করা ( int arr [ ] , int l , int মি , int r )
{
int n1 = মি - l + 1 ;
int n2 = r - মি ;
int এল [ n1 ] , আর [ n2 ] ;
জন্য ( int i = 0 ; i < n1 ; i ++ )
এল [ i ] = arr [ l + i ] ;
জন্য ( int j = 0 ; j < n2 ; j ++ )
আর [ j ] = arr [ মি + 1 + j ] ;
int i = 0 , j = 0 , k = l ;
যখন ( i < n1 && j < n2 ) {
যদি ( এল [ i ] <= আর [ j ] ) {
arr [ k ] = এল [ i ] ;
i ++;
}
অন্য {
arr [ k ] = আর [ j ] ;
j ++;
}
k ++;
}
যখন ( i < n1 ) {
arr [ k ] = এল [ i ] ;
i ++;
k ++;
}
যখন ( j < n2 ) {
arr [ k ] = আর [ j ] ;
j ++;
k ++;
}
}
অকার্যকর একত্রিত করুন ( int arr [ ] , int l , int r )
{
যদি ( l < r ) {
int মি = l + ( r - l ) / 2 ;
একত্রিত করুন ( arr , l , মি ) ;
একত্রিত করুন ( arr , মি + 1 , r ) ;
একত্রিত করা ( arr , l , মি , r ) ;
}
}
int প্রধান ( )
{
int arr [ ] = { 12 , এগারো , 13 , 5 , 6 , 7 } ;
int arr_size = আকার ( arr ) / আকার ( arr [ 0 ] ) ;
cout << 'প্রদত্ত অ্যারে হল \n ' ;
জন্য ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
একত্রিত করুন ( arr , 0 , arr_size - 1 ) ;
cout << ' \n সাজানো অ্যারে হল \n ' ;
জন্য ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
ফিরে 0 ;
}
এই প্রোগ্রামে, মার্জ ফাংশনটি arr, l, এবং r তিনটি আর্গুমেন্ট নেয়, যা সাজানোর জন্য অ্যারের প্রতিনিধিত্ব করে এবং সাব্যারেটির সূচকগুলি দেখায় যা মার্জ করা দরকার। ফাংশনটি প্রথমে একত্রিত হওয়ার জন্য দুটি সাবয়ারের আকার খুঁজে পায়, তারপর এই সাব্যারেগুলির উপাদানগুলিকে সংরক্ষণ করার জন্য দুটি অস্থায়ী সাবাররে L এবং R তৈরি করে। এটি তারপর L এবং R-এর উপাদানগুলির তুলনা করে এবং তাদের নামের মূল অ্যারেতে মার্জ করে arr আরোহী ক্রমে।
ডিভাইড-এন্ড-কনকার কৌশলটি মার্জসোর্ট ফাংশন দ্বারা নিযুক্ত করা হয় যাতে সাব্যারেতে শুধুমাত্র একটি উপাদান বাকি না থাকা পর্যন্ত অ্যারেটিকে পুনরাবৃত্তিমূলকভাবে দুটি অর্ধে বিভক্ত করা হয়। এটি তারপর একটি সাজানো সাবরেতে দুটি সাবরেকে একত্রিত করে। ফাংশনটি সাব্যারেগুলিকে একত্রিত করতে থাকে যদি না এটি সম্পূর্ণ অ্যারে সাজায়।
প্রধান ফাংশনে, আমরা 6টি উপাদান সহ একটি অ্যারে অ্যারের সংজ্ঞায়িত করি এবং এটিকে সাজানোর জন্য মার্জসোর্ট ফাংশনকে কল করি। কোডের শেষে, সাজানো অ্যারে প্রিন্ট করা হয়।
পদ্ধতি 2 – এক টেম্প সাবারে ব্যবহার করা
পদ্ধতি 2 ব্যবহার করে সি++-এ মার্জ সাজানোর জন্য এখানে একটি উদাহরণ প্রোগ্রাম রয়েছে, যা একটি একক অস্থায়ী সাবারে ব্যবহার করে:
# অন্তর্ভুক্ত করুননামস্থান std ব্যবহার করে ;
অকার্যকর একত্রিত করা ( int arr [ ] , int l , int মি , int r )
{
int i , j , k ;
int n1 = মি - l + 1 ;
int n2 = r - মি ;
// অস্থায়ী সাবাররে তৈরি করুন
int এল [ n1 ] , আর [ n2 ] ;
// সাব্যারেতে ডেটা কপি করুন
জন্য ( i = 0 ; i < n1 ; i ++ )
এল [ i ] = arr [ l + i ] ;
জন্য ( j = 0 ; j < n2 ; j ++ )
আর [ j ] = arr [ মি + 1 + j ] ;
// অস্থায়ী সাব্যারেগুলিকে মূল অ্যারেতে মার্জ করুন
i = 0 ;
j = 0 ;
k = l ;
যখন ( i < n1 && j < n2 ) {
যদি ( এল [ i ] <= আর [ j ] ) {
arr [ k ] = এল [ i ] ;
i ++;
}
অন্য {
arr [ k ] = আর [ j ] ;
j ++;
}
k ++;
}
// L[] এর অবশিষ্ট উপাদানগুলি অনুলিপি করুন
যখন ( i < n1 ) {
arr [ k ] = এল [ i ] ;
i ++;
k ++;
}
// R[] এর অবশিষ্ট উপাদানগুলি অনুলিপি করুন
যখন ( j < n2 ) {
arr [ k ] = আর [ j ] ;
j ++;
k ++;
}
}
অকার্যকর একত্রিত করুন ( int arr [ ] , int l , int r )
{
যদি ( l < r ) {
int মি = l + ( r - l ) / 2 ;
// বাম এবং ডান অর্ধেক বারবার সাজান
একত্রিত করুন ( arr , l , মি ) ;
একত্রিত করুন ( arr , মি + 1 , r ) ;
// দুটি সাজানো অর্ধেক একত্রিত করুন
একত্রিত করা ( arr , l , মি , r ) ;
}
}
int প্রধান ( )
{
int arr [ ] = { 12 , এগারো , 13 , 5 , 6 , 7 } ;
int arr_size = আকার ( arr ) / আকার ( arr [ 0 ] ) ;
cout << 'প্রদত্ত অ্যারে হল \n ' ;
জন্য ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
একত্রিত করুন ( arr , 0 , arr_size - 1 ) ;
cout << ' \n সাজানো অ্যারে হল \n ' ;
জন্য ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
ফিরে 0 ;
}
এই প্রোগ্রামটি আগেরটির মতোই, তবে দুটি অস্থায়ী সাবয়ারে L এবং R ব্যবহার করার পরিবর্তে, এটি একটি একক অস্থায়ী সাবারে টেম্প ব্যবহার করে। মার্জ ফাংশনটি আগের মতই কাজ করে, কিন্তু ডেটাকে L এবং R-এ কপি করার পরিবর্তে, এটি temp-এ কপি করে। এটি তারপরে টেম্প অ্যারে উপাদানগুলিকে আবার তে মার্জ করে arr যা মূল অ্যারে।
mergeSort ফাংশন আগের মতই, তা ছাড়া এটি অস্থায়ী সাবাররে সংরক্ষণ করতে L এবং R এর পরিবর্তে temp ব্যবহার করে।
প্রধান ফাংশনে, আমরা 6টি উপাদান সহ একটি অ্যারে অ্যারের সংজ্ঞায়িত করি এবং এটিকে সাজানোর জন্য মার্জসোর্ট ফাংশনকে কল করি। স্ক্রীনে সাজানো অ্যারে প্রিন্ট করে কোড এক্সিকিউশন শেষ হয়।
উপসংহার
মার্জ সর্ট হল একটি অ্যালগরিদম যা অ্যারে উপাদানগুলিকে সাজায় এবং এটি ডিভাইড-এন্ড-কনকার কৌশল ব্যবহার করে এবং উপাদানগুলির মধ্যে তুলনা করে। C++ এ মার্জ সর্টে O(n log n) এর সময় জটিলতা রয়েছে এবং এটি বড় অ্যারে সাজানোর জন্য বিশেষভাবে কার্যকর। যদিও মার্জ করা সাব্যারেগুলি সংরক্ষণ করার জন্য এটির অতিরিক্ত মেমরির প্রয়োজন, তবে এর স্থায়িত্ব এটিকে সাজানোর জন্য একটি জনপ্রিয় পছন্দ করে তোলে।