Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


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

मर्ज सॉर्ट

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

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

  • जांचें कि क्या सूची में एक तत्व है तो तत्व लौटाएं।

  • अन्यथा, डेटा को पुनरावर्ती रूप से दो हिस्सों में विभाजित करें जब तक कि इसे आगे विभाजित न किया जा सके।

  • अंत में, छोटी सूचियों को सॉर्टेड क्रम में नई सूचियों में मर्ज करें।

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

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

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

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

इनपुट - 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 तक लूप FOR शुरू करें जब तक i थ्रेड के आकार से कम है। लूप के अंदर, दिए गए सरणी मानों के साथ थ्रेड बनाने के लिए 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 को 0 से temp_1 से कम तक लूप FOR शुरू करें। लूप के अंदर, start[i] को arr[i + first] पर सेट करें।

    • i को 0 से temp_2 से कम तक लूप FOR शुरू करें। लूप के अंदर, last[i] को arr[i + mid_val + 1] पर सेट करें

    • i को j को 0 पर सेट करें। लूप While शुरू करें i, temp_1 से कम है AND j, temp_2 से कम है। While के अंदर, जांचें 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++] पर सेट करें

उदाहरण

#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<<"मल्टी-थ्रेडिंग का उपयोग करके मर्ज सॉर्ट: ";     for (int i = 0; i < size; i++){       cout << arr[i] << " ";     }     return 0; }

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा

मल्टी-थ्रेडिंग का उपयोग करके मर्ज सॉर्ट: 15 21 26 26 27 35 36 40 49 59 62 63 72 77 83 86 86 90 92 93

  1. - मर्ज सॉर्ट

    मर्ज सॉर्ट तकनीक डिवाइड एंड कन्कर तकनीक पर आधारित है। हम पूरे डेटासेट को छोटे भागों में विभाजित करते हैं और उन्हें सॉर्टेड ऑर्डर में एक बड़े भाग में मर्ज करते हैं। यह सबसे खराब मामलों के लिए भी बहुत प्रभावी है क्योंकि इस एल्गोरिदम की सबसे खराब स्थिति के लिए भी कम टाइम कॉम्प्लेक्सिटी है। मर्ज सॉर्ट

  1. - मर्ज सॉर्ट का उपयोग करके सरणी को सॉर्ट करने का C प्रोग्राम

    एक सरणी संबंधित डेटा आइटम्स का एक समूह है जो एक सामान्य नाम साझा करता है। एक सरणी में एक विशेष मान को इसके इंडेक्स नंबर की मदद से पहचाना जाता है। सरणी डिक्लेयर करना सरणी डिक्लेयर करने का सिंटैक्स निम्नानुसार है: datatype array_name[size]; उदाहरण के लिए, float marks[50] यह marks को 50 फ्लोट तत्वों व

  1. मर्ज सॉर्ट का उपयोग करके ऐरे में इनवर्जन गिनने के लिए C/C++ प्रोग्राम? मर्ज सॉर्ट का उपयोग करके ऐरे में इनवर्जन गिनने के लिए C/C++ प्रोग्राम?

    दिए गए ऐरे को क्रमबद्ध करने के लिए होने वाले इनवर्जन की संख्या को इनवर्जन काउंट (inversion count) के रूप में जाना जाता है। इनवर्जन समस्या एक शास्त्रीय समस्या है जिसे मर्ज सॉर्ट एल्गोरिदम का उपयोग करके हल किया जा सकता है। इस समस्या में हम इसके बाईं ओर उससे बड़े सभी एलिमेंट्स को गिनेंगे और काउंट को आ