আমরা একটি unsorted পূর্ণসংখ্যা অ্যারে দেওয়া হয়. কাজটি হল মাল্টি-থ্রেডিংয়ের মাধ্যমে প্রয়োগ করা মার্জ সর্ট টেকনিক ব্যবহার করে অ্যারে সাজানো
সর্ট মার্জ করুন
মার্জ সর্ট হল একটি সাজানোর কৌশল যা ভাগ করা এবং জয় করার কৌশলের উপর ভিত্তি করে যেখানে আমরা অ্যারেকে সমান অর্ধে ভাগ করি এবং তারপর একটি সাজানো পদ্ধতিতে একত্রিত করি।
একত্রীকরণ সাজানোর জন্য অ্যালগরিদম হল
-
তালিকায় একটি উপাদান আছে কিনা তা পরীক্ষা করুন তারপর উপাদানটি ফেরত দিন।
-
অন্যথায়, ডেটাকে পুনরাবৃত্তভাবে দুটি ভাগে ভাগ করুন যতক্ষণ না এটি আরও ভাগ করা যায়।
-
অবশেষে, ছোট তালিকাগুলিকে সাজানো ক্রমে নতুন তালিকায় মার্জ করুন।
মাল্টি-থ্রেডিং
অপারেটিং সিস্টেমে, থ্রেড লাইটওয়েট প্রক্রিয়া যা একটি কাজের অংশ নির্বাহের জন্য দায়ী। থ্রেডগুলি একই সাথে কাজটি চালানোর জন্য সাধারণ সংস্থানগুলি ভাগ করে৷
মাল্টি-থ্রেডিং মাল্টিটাস্কিং এর একটি বাস্তবায়ন যেখানে আমরা একই সাথে কাজগুলি চালানোর জন্য একক প্রসেসরে একাধিক থ্রেড চালাতে পারি। এটি একটি একক অ্যাপ্লিকেশনের মধ্যে নির্দিষ্ট ক্রিয়াকলাপগুলিকে পৃথক থ্রেডগুলিতে উপবিভক্ত করে। প্রতিটি থ্রেড সমান্তরালভাবে চলতে পারে।
উদাহরণস্বরূপ-:
এ −int arr[] ={3, 2, 1, 10, 8, 5, 7, 9, 4}
আউট −সর্ট করা অ্যারে হল:1, 2, 3, 4, 5, 7, 8, 9, 10
ব্যাখ্যা −আমাদের পূর্ণসংখ্যার মান সহ একটি সাজানো বিন্যাস দেওয়া হয়েছে। এখন আমরা মাল্টিথ্রেডিংয়ের সাথে মার্জ সর্ট ব্যবহার করে অ্যারে সাজাব।
এ −int arr[] ={5, 3, 1, 45, 32, 21, 50}
আউট −সর্ট করা অ্যারে হল:1, 3, 5, 21, 32, 45, 50
ব্যাখ্যা −আমাদের পূর্ণসংখ্যার মান সহ একটি সাজানো বিন্যাস দেওয়া হয়েছে। এখন আমরা মাল্টিথ্রেডিংয়ের সাথে মার্জ সর্ট ব্যবহার করে অ্যারে সাজাব।
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি হল -
-
আমরা C++ STL-এ Rand() পদ্ধতি ব্যবহার করে এলোমেলো সংখ্যা তৈরি করে শুরু করব।
-
pthread_t প্রকারের একটি অ্যারে তৈরি করুন যেমন P_TH[thread_size]।
-
i থেকে 0 পর্যন্ত লুপ শুরু করুন যতক্ষণ না i একটি থ্রেডের আকারের চেয়ে কম হয়। লুপের ভিতরে, প্রদত্ত অ্যারে মান সহ থ্রেড তৈরি করতে pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL) পদ্ধতিতে কল করুন।
-
কম্বিন_অ্যারে (0, (সাইজ / 2 - 1) / 2, সাইজ / 2 - 1), কম্বিন_অ্যারে (সাইজ / 2, সাইজ/2 + (সাইজ-1-সাইজ/2)/2, সাইজ - 1) হিসাবে ফাংশনকে কল করুন এবং একত্রিত_অ্যারে(0, (আকার - 1)/2, আকার - 1)
-
পূর্ণসংখ্যার প্রকারের arr[]-এ সংরক্ষিত সাজানো অ্যারে প্রিন্ট করুন।
-
ফাংশনের ভিতরে void* Sorting_Threading(void* arg)
-
একটি ভেরিয়েবল ঘোষণা করুন set_val থেকে temp_val++, প্রথমে set_val * (size / 4), শেষ থেকে (set_val + 1) * (size / 4) - 1 এবং mid_val to first + (শেষ - প্রথম) / 2
-
প্রথমে যদি শেষের চেয়ে কম হয় তা পরীক্ষা করুন তারপরে কল করুন Sorting_Threading(first, mid_val), Sorting_Threading(mid_val + 1, end) এবং combine_array(first, mid_val, end);
-
-
ফাংশনের ভিতর void Sorting_Threading(int first, int end)
-
ভেরিয়েবলকে mid_val থেকে first + (শেষ - প্রথম) / 2
হিসাবে ঘোষণা করুন -
প্রথমে যদি শেষের চেয়ে কম হয় তা পরীক্ষা করুন তারপরে কল করুন Sorting_Threading(first, mid_val), Sorting_Threading(mid_val + 1, end) এবং combine_array(first, mid_val, end)
-
-
ফাংশনের ভিতরে void combine_array(int first, int mid_val, int end)
-
int* নতুন int[mid_val - first + 1] থেকে শুরু করে, int* শেষ থেকে নতুন int[end - mid_val], temp_1 থেকে mid_val - প্রথম + 1, temp_2 থেকে শেষ - mid_val, i, j, k থেকে প্রথম হিসাবে ভেরিয়েবল ঘোষণা করুন .
-
i থেকে 0 পর্যন্ত FOR লুপ শুরু করুন যতক্ষণ না আমি temp_1-এর থেকে কম হয়। লুপের ভিতরে, arr[i + first] এ start[i] সেট করুন।
-
i থেকে 0 পর্যন্ত FOR লুপ শুরু করুন যতক্ষণ না আমি temp_2-এর থেকে কম হয়। লুপের ভিতরে, শেষ[i] সেট করুন arr[i + mid_val + 1]
-
i j থেকে 0 সেট করুন। লুপ শুরু করুন যখন i temp_1 থেকে কম এবং j temp_2 থেকে কম। কিছুক্ষণের মধ্যে, IF start[i] শেষ[j] থেকে কম চেক করুন তারপর শুরু করার জন্য arr[k++] সেট করুন[i++]। অন্যথায়, arr[k++] =শেষ[j++]
সেট করুন -
শুরু করুন যখন i temp_1 থেকে কম তারপর arr[k++] =start[i++] সেট করুন। temp_2 থেকে j কম থাকাকালীন শুরু করুন তারপরে শেষ [j++]
এ arr[k++] সেট করুন
-
উদাহরণ
#include <iostream>
#include <pthread.h>
#include <time.h>
#define size 20
#define thread_size 4
using namespace std;
int arr[size];
int temp_val = 0;
void combine_array(int first, int mid_val, int end){
int* start = new int[mid_val - first + 1];
int* last = new int[end - mid_val];
int temp_1 = mid_val - first + 1;
int temp_2 = end - mid_val;
int i, j;
int k = first;
for(i = 0; i < temp_1; i++){
start[i] = arr[i + first];
}
for (i = 0; i < temp_2; i++){
last[i] = arr[i + mid_val + 1];
}
i = j = 0;
while(i < temp_1 && j < temp_2){
if(start[i] <= last[j]){
arr[k++] = start[i++];
}
else{
arr[k++] = last[j++];
}
}
while (i < temp_1){
arr[k++] = start[i++];
}
while (j < temp_2){
arr[k++] = last[j++];
}
}
void Sorting_Threading(int first, int end){
int mid_val = first + (end - first) / 2;
if(first < end){
Sorting_Threading(first, mid_val);
Sorting_Threading(mid_val + 1, end);
combine_array(first, mid_val, end);
}
}
void* Sorting_Threading(void* arg){
int set_val = temp_val++;
int first = set_val * (size / 4);
int end = (set_val + 1) * (size / 4) - 1;
int mid_val = first + (end - first) / 2;
if (first < end){
Sorting_Threading(first, mid_val);
Sorting_Threading(mid_val + 1, end);
combine_array(first, mid_val, end);
}
}
int main(){
for(int i = 0; i < size; i++){
arr[i] = rand() % 100;
}
pthread_t P_TH[thread_size];
for(int i = 0; i < thread_size; i++){
pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL);
}
for(int i = 0; i < 4; i++){
pthread_join(P_TH[i], NULL);
}
combine_array(0, (size / 2 - 1) / 2, size / 2 - 1);
combine_array(size / 2, size/2 + (size-1-size/2)/2, size - 1);
combine_array(0, (size - 1)/2, size - 1);
cout<<"Merge Sort using Multi-threading: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে
Merge Sort using Multi-threading: 15 21 26 26 27 35 36 40 49 59 62 63 72 77 83 86 86 90 92 93
