আমাদের কাছে একটি আনসোর্টেড পূর্ণসংখ্যার অ্যারে আছে। কাজটি হলো মাল্টি-থ্রেডিং ব্যবহার করে মার্জ সোর্ট টেকনিক দিয়ে অ্যারেটি সর্ট করা।
মার্জ সোর্ট
মার্জ সোর্ট হলো একটি সর্টিং টেকনিক যা ডিভাইড এন্ড কোঙ্কার (Divide and Conquer) টেকনিকের ওপর ভিত্তি করে তৈরি হয়েছে, যেখানে আমরা অ্যারেকে সমান দুই ভাগে ভাগ করি এবং তারপর সেগুলোকে সর্টেড ভাবে কাম্বাইন করি।
মার্জ সোর্ট ইমপ্লিমেন্ট করার অ্যালগরিদম
চেক করো লিস্টে একই এলিমেন্ট আছে কিনা, থাকলে এলিমেন্টটি রিটার্ন করো।
অন্যথায়, ডেটাকে রিকার্সিভলি দুটি সমান ভাগে ভাগ করো যতক্ষণ না আরও ভাগ করা সম্ভব নয়।
শেষে, ছোট লিস্টগুলোকে সর্টেড ভাবে নতুন লিস্টে মার্জ করো।
মাল্টি-থ্রেডিং
অপারেটিং সিস্টেমে, থ্রেড হলো লাইটওয়েট প্রসেস যা একটি টাস্কের অংশ এক্সিকিউট করার দায়িত্বে থাকে। থ্রেডগুলো কমন রিসোর্স শেয়ার করে টাস্ক কনকারেন্টলি এক্সিকিউট করে।
মাল্টি-থ্রেডিং হলো মাল্টিটাস্কিং এর একটি ইমপ্লিমেন্টেশন যেখানে আমরা একটি সিঙ্গেল প্রসেসরে মাল্টিপল থ্রেড রান করি টাস্কগুলো কনকারেন্টলি এক্সিকিউট করার জন্য। এটি একটি সিঙ্গেল অ্যাপ্লিকেশনের নির্দিষ্ট অপারেশনকে إندিভিজুয়াল থ্রেডে সাবডিভাইড করে। প্রতিটি থ্রেড প্যারালালে রান করতে পারে।
উদাহরণ-:
ইনপুট − 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 থেকে ০ শুরু করে i থ্রেড সাইজের চেয়ে কম থাকা পর্যন্ত FOR লুপ চালাব। লুপের ভিতরে pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)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)
ইন্টিজার টাইপের arr[]-এ সংরক্ষিত সর্টেড অ্যারে প্রিন্ট করব।
void* Sorting_Threading(void* arg) ফাংশনের ভিতরে
একটি ভেরিয়েবল ডিক্লেয়ার করব set_val হিসেবে temp_val++, first হিসেবে set_val * (size / 4), end হিসেবে (set_val + 1) * (size / 4) - 1 এবং 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(int first, int end) ফাংশনের ভিতরে
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 combine_array(int first, int mid_val, int end) ফাংশনের ভিতরে
ভেরিয়েবল ডিক্লেয়ার: int* start = new int[mid_val - first + 1], int* last = new int[end - mid_val], temp_1 = mid_val - first + 1, temp_2 = end - mid_val, i, j, k = first।
i ০ থেকে temp_1-১ পর্যন্ত FOR লুপ চালাব। লুপের ভিতরে start[i] = arr[i + first] সেট করব।
i ০ থেকে temp_2-১ পর্যন্ত FOR লুপ চালাব। লুপের ভিতরে last[i] = arr[i + mid_val + 1] সেট করব।
i, j কে ০ সেট করব। i < temp_1 AND j < temp_2 হলে WHILE লুপ চালাব। লুপের ভিতরে চেক করব IF start[i] <= last[j] তবে arr[k++] = start[i++] সেট করব। ELSE, arr[k++] = last[j++] সেট করব।
i < temp_1 হলে WHILE লুপ চালাব এবং arr[k++] = start[i++] সেট করব। j < temp_2 হলে WHILE লুপ চালাব এবং arr[k++] = last[j++] সেট করব।
উদাহরণ
#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
