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

C++ प्रोग्राम: मर्ज सॉर्ट लागू करना


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

मर्ज सॉर्ट तकनीक की जटिलता

  • समय जटिलता: सभी मामलों के लिए O(n log n)

  • स्पेस जटिलता: O(n)

इनपुट − असॉर्टेड सूची: 14 20 78 98 20 45 आउटपुट − सॉर्टिंग के बाद सरणी: 14 20 20 45 78 98

एल्गोरिदम

merge(array, left, middle, right)

इनपुट: डेटा सेट सरणी, बाएं, मध्य और दाएं सूचकांक

आउटपुट: मर्ज की गई सूची

शुरुआत    nLeft := m - left+1    nRight := right – m    आकार nLeft और nRight की सरणी leftArr और rightArr परिभाषित करें    i := 0 से nLeft तक करें       leftArr[i] := array[left +1]    हो गया    j := 0 से nRight तक करें       rightArr[j] := array[middle + j +1]    हो गया    i := 0, j := 0, k := left    जब तक i < nLeft AND j < nRight करें       यदि leftArr[i] <= rightArr[j] तो          array[k] = leftArr[i]          i := i+1       अन्यथा          array[k] = rightArr[j]          j := j+1          k := k+1    हो गया जब तक i < nLeft करें array[k] := leftArr[i] i := i+1 k := k+1 हो गया जब तक j < nRight करें array[k] := rightArr[j] j := j+1 k := k+1 हो गया अंत

mergeSort(array, left, right)

इनपुट: डेटा की एक सरणी, और सरणी की निचली और ऊपरी सीमा

आउटपुट: क्रमबद्ध सरणी

शुरुआत यदि lower < right तो mid := left + (right - left) /2 mergeSort(array, left, mid) mergeSort (array, mid+1, right) merge(array, left, mid, right) अंत

उदाहरण कोड

#include<iostream> using namespace std; void swapping(int &a, int &b) {     //a और b की सामग्री स्वैप करें    int temp;    temp = a;    a = b;    b = temp; } void display(int *array, int size) {    for(int i = 0; i<size; i++)       cout << array[i] << " ";    cout << endl; } void merge(int *array, int l, int m, int r) {    int i, j, k, nl, nr;    //बाएं और दाएं उप-सरणियों का आकार    nl = m-l+1; nr = r-m;    int larr[nl], rarr[nr];    //बाएं और दाएं उप-सरणियों को भरें    for(i = 0; i<nl; i++)       larr[i] = array[l+i];    for(j = 0; j<nr; j++)       rarr[j] = array[m+1+j];    i = 0; j = 0; k = l;    //अस्थायी सरणियों को वास्तविक सरणी में मर्ज करें    while(i < nl && j<nr) {       if(larr[i] <= rarr[j]) {          array[k] = larr[i];          i++;       }else{          array[k] = rarr[j];          j++;       }       k++;    } while(i<nl) { //बाएं सरणी में अतिरिक्त तत्व array[k] = larr[i]; i++; k++; } while(j<nr) { //दाएं सरणी में अतिरिक्त तत्व array[k] = rarr[j]; j++; k++; } } void mergeSort(int *array, int l, int r) { int m; if(l < r) { int m = l+(r-l)/2; // पहली और दूसरी सरणियों को सॉर्ट करें mergeSort(array, l, m); mergeSort(array, m+1, r); merge(array, l, m, r); } } int main() { int n; cout << "तत्वों की संख्या दर्ज करें: "; cin >> n; int arr[n]; //दिए गए तत्वों की संख्या के साथ एक सरणी बनाएं cout << "तत्व दर्ज करें:" << endl; for(int i = 0; i<n; i++) { cin >> arr[i]; } cout << "सॉर्टिंग से पहले सरणी: "; display(arr, n); mergeSort(arr, 0, n-1); //(n-1) अंतिम सूचकांक के लिए cout << "सॉर्टिंग के बाद सरणी: "; display(arr, n); }

आउटपुट

तत्वों की संख्या दर्ज करें: 6 तत्व दर्ज करें: 14 20 78 98 20 45 सॉर्टिंग से पहले सरणी: 14 20 78 98 20 45 सॉर्टिंग के बाद सरणी: 14 20 20 45 78 98

  1. - C++ प्रोग्राम: ऐरे का उपयोग करके क्यू कार्यान्वयन

    ऐरे आधारित क्यू क्यू FIFO सिद्धांत का पालन करती है। ऐरे कार्यान्वयन में निश्चित आकार की सरणी और front/rear सूचकांक का उपयोग किया जाता है। C++ प्रोग्राम उदाहरण rear) { cout << Queue Underflow << endl; return; } else { cout << Element deleted: <<

  1. - C++ प्रोग्राम: ऐरे का उपयोग करके स्टैक कार्यान्वयन

    ऐरे आधारित स्टैक निश्चित आकार की सरणी और top सूचकांक का उपयोग करके स्टैक कार्यान्वयन। LIFO सिद्धांत का पालन करता है। C++ प्रोग्राम उदाहरण = MAX - 1) cout << Stack Overflow << endl; else { top++; stack[top] = val; } } void pop() { if (top = 0; i--)

  1. - C++ प्रोग्राम: सॉर्टेड ऐरे कार्यान्वयन (सिलेक्शन सॉर्ट)

    सॉर्टेड ऐरे ऐरे जिसमें तत्व क्रमबद्ध क्रम में हों (संख्यात्मक, वर्णानुक्रमिक, आदि)। कई सॉर्टिंग एल्गोरिदम: बबल सॉर्ट, इन्सर्शन सॉर्ट, सिलेक्शन सॉर्ट, मर्ज सॉर्ट, क्विक सॉर्ट, हीप सॉर्ट। सिलेक्शन सॉर्ट अनसॉर्टेड भाग में सबसे छोटा तत्व ढूंढकर उसे शुरुआत से स्वैप करता है। O(n²) समय जटिलता। C++ प्रोग