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