इस ट्यूटोरियल में, आप मर्ज सॉर्ट के बारे में जानेंगे। इसके अलावा, आप मर्ज सॉर्ट C, C ++, जावा और पायथन के काम करने के उदाहरण पाएंगे।
मर्ज सॉर्ट सबसे लोकप्रिय सॉर्टिंग एल्गोरिदम में से एक है जो डिवाइड और कॉन्कर एल्गोरिथ्म के सिद्धांत पर आधारित है।
यहां, एक समस्या को कई उप-समस्याओं में विभाजित किया गया है। प्रत्येक उप-समस्या को व्यक्तिगत रूप से हल किया जाता है। अंत में, उप-समस्याओं को अंतिम समाधान बनाने के लिए संयोजित किया जाता है।
मर्ज सॉर्ट उदाहरण
विभाजन और जीत की रणनीति
डिवाइड और जीत तकनीक का उपयोग करके , हम एक समस्या को सबप्रॉब्लम्स में विभाजित करते हैं। जब प्रत्येक उपप्रकार का समाधान तैयार हो जाता है, तो हम मुख्य समस्या को हल करने के लिए उपप्रोब्लेम्स से परिणामों को जोड़ते हैं।
मान लीजिए कि हमें एक सरणी को क्रमबद्ध करना था। ए। एक उपप्रकार इस सरणी के उप-खंड को अनुक्रमित पी पर शुरू करने और सूचकांक आर पर समाप्त करने के लिए होगा, जिसे ए (पी … आर) के रूप में दर्शाया जाएगा।
डिवाइड करें
यदि q, p और r के बीच का अर्ध-बिंदु है, तो हम subarray A (p… r) को दो सरणियों A (p… q) और A (q + 1, r) में विभाजित कर सकते हैं।
जीतना
जीत कदम में, हम दोनों उपश्रेणी A (p… q) और A (q + 1, r) को क्रमबद्ध करने का प्रयास करते हैं। यदि हम अभी तक आधार के मामले में नहीं पहुंचे हैं, तो हम फिर से इन दोनों उप-विभाजनों को विभाजित करते हैं और उन्हें क्रमबद्ध करने का प्रयास करते हैं।
गठबंधन करें
जब विजेता कदम आधार चरण तक पहुंचता है और हमें सरणी ए (पी … आर) के लिए दो सॉर्ट किए गए उप-अक्षर ए (पी… क्यू) और ए (क्यू + 1, आर) मिलते हैं, हम एक क्रमबद्ध सरणी ए बनाकर परिणाम गठबंधन करते हैं ( p… r) दो छांटे गए उप-अक्षर A (p… q) और A (q + 1, r) से।
मर्जसॉर्ट एल्गोरिथम
MergeSort फ़ंक्शन बार-बार सरणी को दो हिस्सों में विभाजित करता है, जब तक कि हम एक चरण तक नहीं पहुंच जाते हैं जहां हम आकार 1 अर्थात p == r की उप-श्रेणी पर MergeSort प्रदर्शन करने का प्रयास करते हैं।
उसके बाद, मर्ज फ़ंक्शन प्ले में आता है और सॉर्ट किए गए एरे को बड़े एरेज़ में मिलाता है जब तक कि पूरे ऐरे को मर्ज न कर दिया जाए।
MergeSort (A, p, r): यदि p> r वापसी q = (p + r) / 2 मर्जस्टोर्ट (A, p, q) मर्जोसॉर्ट (A, q + 1, r) मर्ज (A, p, q, r) )
संपूर्ण सरणी को सॉर्ट करने के लिए, हमें कॉल करना होगा MergeSort(A, 0, length(A)-1)।
जैसा कि नीचे दी गई छवि में दिखाया गया है, मर्ज सॉर्ट एल्गोरिथ्म सरणी को तब तक आधा में विभाजित करता है जब तक कि हम 1 तत्व के साथ सरणी के आधार मामले तक नहीं पहुंचते। उसके बाद, मर्ज फ़ंक्शन सॉर्ट किए गए उप-सरणियों को उठाता है और उन्हें धीरे-धीरे पूरे सरणी को सॉर्ट करने के लिए मर्ज करता है।
कार्रवाई में मर्ज करें
मर्ज की मर्ज क्रमबद्ध चरण
प्रत्येक पुनरावर्ती एल्गोरिथ्म एक बेस केस और आधार मामलों से परिणाम गठबंधन करने की क्षमता पर निर्भर है। मर्ज सॉर्ट अलग नहीं है। मर्ज सॉर्ट एल्गोरिथ्म का सबसे महत्वपूर्ण हिस्सा है, आपने यह अनुमान लगाया, मर्ज चरण।
मर्ज चरण एक बड़ी सॉर्ट की गई सूची (सरणी) बनाने के लिए दो सॉर्ट किए गए सूचियों (सरणियों) को मर्ज करने की सरल समस्या का समाधान है।
एल्गोरिथ्म तीन बिंदुओं को बनाए रखता है, प्रत्येक दो सरणियों में से एक और अंतिम सॉर्ट किए गए सरणी के वर्तमान सूचकांक को बनाए रखने के लिए।
क्या हम किसी भी ऐरे के अंत तक पहुँच गए हैं? नहीं: दोनों सरणियों के वर्तमान तत्वों की तुलना करें छोटे तत्व को सॉर्ट किए गए सरणी में कॉपी करें। छोटे तत्व वाले तत्व के सूचक को ले जाएं हां: गैर-खाली सरणी के सभी शेष तत्वों को कॉपी करें
कदम बढ़ाना
मर्ज एल्गोरिथ्म के लिए कोड लिखना
ऊपर वर्णित मर्जिंग चरण के बीच एक ध्यान देने योग्य अंतर और जो हम मर्ज सॉर्ट के लिए उपयोग करते हैं वह यह है कि हम केवल लगातार उप-सरणियों पर मर्ज फ़ंक्शन करते हैं।
यही कारण है कि हमें केवल सरणी की आवश्यकता है, पहली स्थिति, पहली उपप्र्रे के अंतिम सूचकांक (हम दूसरी उपश्रेणी के पहले सूचकांक की गणना कर सकते हैं) और दूसरी उपश्रेणी के अंतिम सूचकांक।
हमारा काम दो उपग्रहों A (p… q) और A (q + 1… r) को मिलाना है ताकि एक क्रमबद्ध सरणी A (p… r) बनाई जा सके। तो फ़ंक्शन के इनपुट ए, पी, क्यू और आर हैं
मर्ज फ़ंक्शन निम्नानुसार काम करता है:
- सबरेज़
L ← A(p… q)और M of A (q + 1… r) की प्रतियां बनाएँ । - तीन पॉइंट बनाएं i, j और k
- मैं L का वर्तमान सूचकांक रखता है, जो 1 से शुरू होता है
- j, M का वर्तमान सूचकांक बनाए रखता है, जो 1 से शुरू होता है
- k, P से शुरू होने वाले A (p… q) के वर्तमान सूचकांक को बनाए रखता है।
- जब तक हम एल या एम के अंत तक नहीं पहुंचते, एल और एम से तत्वों के बीच बड़ा चुनें और उन्हें ए (पी… क्यू) में सही स्थिति में रखें।
- जब हम एल या एम में तत्वों से बाहर निकलते हैं, तो शेष तत्वों को उठाते हैं और ए (पी … क्यू) में डालते हैं
कोड में, यह इस तरह दिखेगा:
// Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) )
मर्ज () फ़ंक्शन चरण-दर-चरण समझाया गया
इस फ़ंक्शन में बहुत कुछ हो रहा है, तो आइए एक उदाहरण देखें कि यह कैसे काम करेगा।
हमेशा की तरह, एक तस्वीर एक हजार शब्द बोलती है।
सरणी के दो लगातार उप-खंडों को जोड़ना
सरणी A (0… 5) में दो सॉर्ट किए गए सबरेज़ A (0… 3) और A (4… 5) होते हैं। आइए देखें कि मर्ज फ़ंक्शन दो सरणियों को कैसे मिलाएगा।
void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)
चरण 1: सॉर्ट किए जाने वाले उप-सरणियों की डुप्लिकेट प्रतियां बनाएं
// Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1 = 3 - 0 + 1 = 4; int n2 = r - q = 5 - 3 = 2; int L(4), M(2); for (int i = 0; i < 4; i++) L(i) = arr(p + i); // L(0,1,2,3) = A(0,1,2,3) = (1,5,10,12) for (int j = 0; j < 2; j++) M(j) = arr(q + 1 + j); // M(0,1,2,3) = A(4,5) = (6,9) 
विलय के लिए उप-प्रतियों की प्रतियां बनाएं
चरण 2: उप-सरणियों और मुख्य सरणी के वर्तमान सूचकांक को बनाए रखें
int i, j, k; i = 0; j = 0; k = p; 
उप सरणी और मुख्य सरणी की प्रतियों के सूचकांक बनाए रखें
चरण 3: जब तक हम या तो एल या एम के अंत तक नहीं पहुँचते, एल और एम तत्वों में से बड़ा चुनें और उन्हें सही स्थिति में ए (पी… आर) पर रखें।
while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) 
जब तक हम एक के अंत तक नहीं पहुँचते तब तक छँटे हुए उपग्रहों के व्यक्तिगत तत्वों की तुलना करना
चरण 4: जब हम एल या एम में तत्वों से बाहर निकलते हैं, तो शेष तत्वों को उठाते हैं और ए (पी … आर) में डालते हैं
// We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; ) 
पहले एरे से मुख्य सब्रे में शेष तत्वों को कॉपी करें
// We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) ) 
मुख्य सरणी में दूसरे सरणी के शेष तत्वों को कॉपी करें
यदि M का आकार L से अधिक होता तो इस चरण की आवश्यकता होती।
मर्ज फ़ंक्शन के अंत में, सबर्रे ए (पी… आर) को सॉर्ट किया जाता है।
पायथन, जावा और सी / सी ++ उदाहरण
पायथन जावा सी सी ++ # MergeSort in Python def mergeSort(array): if len(array)> 1: # r is the point where the array is divided into two subarrays r = len(array)//2 L = array(:r) M = array(r:) # Sort the two halves mergeSort(L) mergeSort(M) i = j = k = 0 # Until we reach either end of either L or M, pick larger among # elements L and M and place them in the correct position at A(p… r) while i < len(L) and j < len(M): if L(i) < M(j): array(k) = L(i) i += 1 else: array(k) = M(j) j += 1 k += 1 # When we run out of elements in either L or M, # pick up the remaining elements and put in A(p… r) while i < len(L): array(k) = L(i) i += 1 k += 1 while j < len(M): array(k) = M(j) j += 1 k += 1 # Print the array def printList(array): for i in range(len(array)): print(array(i), end=" ") print() # Driver program if __name__ == '__main__': array = (6, 5, 12, 10, 9, 1) mergeSort(array) print("Sorted array is: ") printList(array)
// Merge sort in Java class MergeSort ( // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L() = new int(n1); int M() = new int(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = (l + r) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver program public static void main(String args()) ( int arr() = ( 6, 5, 12, 10, 9, 1 ); MergeSort ob = new MergeSort(); ob.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); printArray(arr); ) )
// Merge sort in C #include // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) printf("%d ", arr(i)); printf(""); ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); printf("Sorted array: "); printArray(arr, size); )
// Merge sort in C++ #include using namespace std; // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) cout << arr(i) << " "; cout << endl; ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); cout << "Sorted array: "; printArray(arr, size); return 0; )
मर्ज सॉर्ट कॉम्प्लेक्सिटी
समय जटिलता
सर्वश्रेष्ठ मामले की जटिलता: ओ (एन * लॉग एन)
सबसे खराब स्थिति जटिलता: O (n * log n)
औसत केस जटिलता: O (n * log n)
अंतरिक्ष की जटिलता
मर्ज सॉर्ट का स्थान जटिलता O (n) है।
मर्ज सॉर्ट एप्लिकेशन
- उलटी गिनती समस्या
- बाहरी छँटाई
- ई-कॉमर्स अनुप्रयोग
