सी ++ में मल्टीथ्रेडिंग का उपयोग करके सॉर्ट करें मर्ज करें

हमें एक क्रमबद्ध पूर्णांक सरणी दी गई है। कार्य मल्टी-थ्रेडिंग के माध्यम से कार्यान्वित मर्ज सॉर्ट तकनीक का उपयोग करके सरणी को सॉर्ट करना है

मर्ज सॉर्ट करें

मर्ज सॉर्ट एक सॉर्टिंग तकनीक है जो डिवाइड एंड कॉनकॉट तकनीक पर आधारित है जहां हम एरे को बराबर हिस्सों में विभाजित करते हैं और फिर उन्हें क्रमबद्ध तरीके से जोड़ते हैं।

मर्ज सॉर्ट को लागू करने के लिए एल्गोरिथम है

जांचें कि सूची में एक तत्व है या नहीं, तो तत्व वापस कर दें।
अन्यथा, डेटा को पुनरावर्ती रूप से दो हिस्सों में विभाजित करें जब तक कि इसे और विभाजित न किया जा सके।
अंत में, छोटी सूचियों को क्रमबद्ध क्रम में नई सूचियों में मिला दें।

मल्टी-थ्रेडिंग

ऑपरेटिंग सिस्टम में, थ्रेड्स हल्की प्रक्रिया है जो किसी कार्य के भाग को क्रियान्वित करने के लिए जिम्मेदार है। कार्य को समवर्ती रूप से निष्पादित करने के लिए थ्रेड सामान्य संसाधन साझा करते हैं।

मल्टी-थ्रेडिंग मल्टीटास्किंग का एक कार्यान्वयन है जहां हम कार्यों को समवर्ती रूप से निष्पादित करने के लिए एक ही प्रोसेसर पर एकाधिक थ्रेड चला सकते हैं। यह एक ही एप्लिकेशन के भीतर विशिष्ट कार्यों को अलग-अलग थ्रेड्स में उप-विभाजित करता है। प्रत्येक थ्रेड समानांतर में चल सकता है।

उदाहरण के लिए-:

में −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 में रैंड () पद्धति का उपयोग करके यादृच्छिक संख्याएँ उत्पन्न करके शुरू करेंगे।
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) के रूप में कॉल फ़ंक्शन और Comb_array(0, (आकार -1)/2, आकार -1)
पूर्णांक प्रकार के arr[] में संग्रहीत सॉर्ट किए गए सरणी को प्रिंट करें।
समारोह के अंदर शून्य* Sorting_Threading(void* arg)
- एक चर को set_val से temp_val++, पहले set_val * (आकार / 4), अंत (set_val + 1) * (आकार / 4) - 1 और mid_val से पहले + (अंत - पहले) / 2
  के रूप में घोषित करें
- जाँच करें कि IF पहले अंत से कम है, फिर Sorting_Threading(first, mid_val), Sorting_Threading(mid_val + 1, end) और Comb_array(first, mid_val, end) को कॉल करें;
समारोह के अंदर शून्य Sorting_Threading(int first, int end)
- वेरिएबल को mid_val से first + (end - first) / 2
  . के रूप में घोषित करें
- जाँच करें कि IF पहले अंत से कम है, फिर Sorting_Threading(first, mid_val), Sorting_Threading(mid_val + 1, end) और Comb_array(first, mid_val, end)
  को कॉल करें।
फंक्शन के अंदर void Comb_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 to first ।
- i से 0 तक के लिए लूप प्रारंभ करें जब तक कि i temp_1 से कम न हो जाए। लूप के अंदर, start[i] को arr[i + first] पर सेट करें।
- I से 0 तक के लिए लूप प्रारंभ करें जब तक कि मैं temp_2 से कम नहीं हो जाता। लूप के अंदर, last[i] को arr[i + mid_val + 1]
  . पर सेट करें
- i को j से 0 पर सेट करें। लूप प्रारंभ करें जबकि i temp_1 से कम है और j temp_2 से कम है। थोड़ी देर के अंदर, IF start[i] पिछले [j] से कम की जाँच करें, फिर arr[k++] को start[i++] पर सेट करें। ELSE, एरर सेट करें [k++] =last[j++]
- प्रारंभ करें जबकि मैं temp_1 से कम हूं, फिर arr [k++] =start [i++] सेट करें। प्रारंभ करें जबकि j temp_2 से कम है फिर 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