मेन्यू

उदाहरणों के साथ C ++ में मर्ज करें

merge sort c with examples

समस्याओं को खत्म करने के लिए हमारे साधन का प्रयास करें

सी ++ मर्ज सॉर्ट तकनीक।

मर्ज सॉर्ट एल्गोरिथ्म 'का उपयोग करता है विभाजन और जीत “रणनीति जिसमें हम समस्या को उप-भागों में विभाजित करते हैं और उन उपप्रकारों को व्यक्तिगत रूप से हल करते हैं।

इन उपप्रकारों को तब संयुक्त किया जाता है या एक साथ मिलकर एक एकीकृत घोल बनाया जाता है।

=> लोकप्रिय सी ++ प्रशिक्षण श्रृंखला के माध्यम से यहां पढ़ें।

मर्ज़ सॉर्ट

आप क्या सीखेंगे:

आपके कंप्यूटर को साफ करने का सबसे अच्छा कार्यक्रम क्या है

अवलोकन

निम्न चरणों का उपयोग करके मर्ज सॉर्ट किया जाता है:

# 1) छांटे जाने वाली सूची को मध्य तत्व पर सूची को विभाजित करके समान लंबाई के दो सरणियों में विभाजित किया गया है। यदि सूची में तत्वों की संख्या 0 या 1 है, तो सूची को क्रमबद्ध माना जाता है।

#दो) प्रत्येक सबलिस्ट को पुनरावर्ती रूप से मर्ज सॉर्ट का उपयोग करके व्यक्तिगत रूप से सॉर्ट किया जाता है।

# 3) फिर सॉर्ट किए गए सब्लिस्ट्स को एक संयुक्त या विलय करके पूरी तरह से सॉर्ट की गई सूची के रूप में जोड़ा जाता है।

सामान्य एल्गोरिथम

मर्ज सॉर्ट तकनीक के लिए सामान्य छद्म कोड नीचे दिया गया है।

लंबाई N की एक सरणी ऐर घोषित करें
यदि N = 1, Arr पहले से ही सॉर्ट किया गया है
यदि एन> 1,
वाम = ०, दाहिने = एन -१
मध्य = (बाएँ + दाएँ) / 2 का पता लगाएं
कॉल merge_sort (Arr, बाएँ, मध्य) => पहले आधे पुनरावर्ती को छाँटें
कॉल मर्ज_सोर्ट (एआरआर, मध्य + 1, दाएं) => दूसरी छमाही पुनरावृत्ति की तरह
उपरोक्त चरणों में सॉर्ट किए गए सरणियों को मर्ज करने के लिए कॉल मर्ज (एआरआर, बाएं, मध्य, दाएं)।
बाहर जाएं

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

मर्ज सॉर्ट के लिए छद्म कोड

निम्नलिखित मर्ज सॉर्ट तकनीक के लिए छद्म कोड है। सबसे पहले, हमारे पास एक प्रक्रिया मर्ज सॉर्ट करने के लिए सरणी को रिवर्सीव में विभाजित करने के लिए है। तब हमारे पास एक मर्ज दिनचर्या होती है जो पूर्ण सॉर्ट किए गए सरणी को प्राप्त करने के लिए क्रमबद्ध छोटे सरणियों का विलय करेगी।

procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a(0) ... a(N/2) var array2 as array = a(N/2+1) ... a(N) array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1(0) > array2(0) ) add array2 (0) to the end of c remove array2 (0) from array2 else add array1 (0) to the end of c remove array1 (0) from array1 end if end while while ( a has elements ) add a(0) to the end of c remove a(0) from a end while while ( b has elements ) add b(0) to the end of c remove b(0) from b end while return c end procedure

आइए अब एक उदाहरण के साथ मर्ज सॉर्ट तकनीक का वर्णन करें।

चित्रण

मर्ज प्रकार चित्रण

उपरोक्त चित्र नीचे एक सारणीबद्ध रूप में दिखाया जा सकता है:

उत्तीर्ण करनाअनारक्षित सूचीविभाजनक्रमबद्ध सूची
1{12, 23,2,43,51,35,19,4}{१२,२३,२,४३}
{51,35,19,4}		{}
दो{१२,२३,२,४३}
{51,35,19,4}		{१२.२३} {२.४३}
{५१.३५} {१ ९ .४}		{}
३{१२.२३} {२.४३}
{५१.३५} {१ ९ .४}		{१२.२३} {२.४३}
{35.51} {4.19}		{१२.२३} {२.४३}
{35.51} {4.19}
४{१२.२३} {२.४३}
{35.51} {4.19}		{2,12,23,43}
{4,19,35,51}		{2,12,23,43}
{4,19,35,51}
५{2,12,23,43}
{4,19,35,51}		{2,4,12,19,23,35,43,51}{2,4,12,19,23,35,43,51}
६{}{}{2,4,12,19,23,35,43,51}

जैसा कि उपरोक्त प्रतिनिधित्व में दिखाया गया है, पहले सरणी को लंबाई के दो उप-सरणियों में विभाजित किया गया है। प्रत्येक उप-सरणी को लंबाई के दो और उप-सरणियों में विभाजित किया गया है। प्रत्येक उप-सरणी को फिर उप-सरणी में विभाजित किया गया है। प्रत्येक तत्व का। यह पूरी प्रक्रिया “डिवाइड” प्रक्रिया है।

एक बार जब हमने सरणी को एकल तत्व के उप-सरणियों में विभाजित किया है, तो अब हमें इन सरणियों को क्रमबद्ध क्रम में मर्ज करना होगा।

जैसा कि ऊपर चित्रण में दिखाया गया है, हम एक तत्व के प्रत्येक उपप्रकार पर विचार करते हैं और पहले दो तत्वों के उप-सरणियों को क्रमबद्ध क्रम में बनाने के लिए तत्वों को मिलाते हैं। इसके बाद, लंबाई दो की क्रमबद्ध उप-प्रकार को क्रमबद्ध किया जाता है और लंबाई चार में से प्रत्येक के दो उप-सरणियों को संयुक्त किया जाता है। फिर हम इन दो उप-सरणियों को एक पूर्ण सॉर्ट किए गए सरणी के रूप में जोड़ते हैं।

Iterative मर्ज सॉर्ट

मर्ज के एल्गोरिथ्म या तकनीक को हमने ऊपर देखा है पुनरावृत्ति का उपयोग करता है। यह 'के रूप में भी जाना जाता है पुनरावर्ती विलय प्रकार ”।

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

इन सभी ओवरहेड्स से छुटकारा पाया जा सकता है अगर हम पुनरावर्ती के बजाय पुनरावृत्त कार्यों का उपयोग करते हैं। उपरोक्त मर्ज सॉर्ट एल्गोरिथ्म को भी छोरों और निर्णय लेने का उपयोग करके आसानी से पुनरावृत्ति चरणों में परिवर्तित किया जा सकता है।

पुनरावर्ती मर्ज सॉर्ट की तरह, पुनरावृत्त मर्ज सॉर्ट में भी O (nlogn) जटिलता है इसलिए प्रदर्शन बुद्धिमान, वे एक-दूसरे के बराबर करते हैं। हम बस ओवरहेड्स को कम करने में सक्षम हैं।

इस ट्यूटोरियल में, हम पुनरावर्ती मर्ज सॉर्ट पर ध्यान केंद्रित कर रहे हैं और इसके बाद, हम C ++ और जावा भाषाओं का उपयोग करके पुनरावर्ती मर्ज सॉर्ट को लागू करेंगे।

नीचे दिए गए C ++ का उपयोग करके मर्ज सॉर्ट तकनीक का कार्यान्वयन है।

#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array '; for (int i = 0; i < num; i++) { cout<

आउटपुट:

सॉर्ट किए जाने वाले तत्वों की संख्या दर्ज करें: 10

सॉर्ट किए जाने वाले 10 तत्वों को दर्ज करें: 101 10 2 43 12 54 34 64 89 76

क्रमबद्ध सरणी

2 10 12 34 43 54 64 76 89 101

इस कार्यक्रम में, हमने दो कार्यों को परिभाषित किया है, मर्ज़ सॉर्ट तथा जाओ । Merge_sort फ़ंक्शन में, हम सरणी को दो समान सरणियों में विभाजित करते हैं और इनमें से प्रत्येक उप सरणियों पर मर्ज फ़ंक्शन को कॉल करते हैं। मर्ज फ़ंक्शन में, हम इन उप सरणियों पर वास्तविक सॉर्टिंग करते हैं और फिर उन्हें एक पूर्ण सॉर्ट किए गए सरणी में मर्ज करते हैं।

अगला, हम जावा भाषा में मर्ज सॉर्ट तकनीक को लागू करते हैं।

class MergeSort { void merge(int arr(), int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr() = new int (left); int Right_arr() = new int (right); for (int i=0; i

आउटपुट:

इनपुट एरियर

101 10 2 43 12 54 34 64 89 76

मर्ज सॉर्ट का उपयोग करके सॉर्ट किया गया

2 10 12 34 43 54 64 76 89 101

जावा कार्यान्वयन में भी, हम उसी तर्क का उपयोग करते हैं जैसा कि हमने C ++ कार्यान्वयन में उपयोग किया था।

मर्ज सॉर्ट सूचियों को सॉर्ट करने का एक प्रभावी तरीका है और अधिकतर लिंक लिस्ट को सॉर्ट करने के लिए उपयोग किया जाता है। जैसा कि यह एक विभाजित और विजेता दृष्टिकोण का उपयोग करता है, मर्ज सॉर्ट तकनीक छोटे और साथ ही बड़े सरणियों के लिए समान रूप से कुशल होती है।

विलय सॉर्ट एल्गोरिथ्म की जटिलता विश्लेषण

हम जानते हैं कि मर्ज सॉर्ट का उपयोग करके सॉर्ट करने के लिए, हम पहले ऐरे को दो बराबर हिस्सों में विभाजित करते हैं। यह 'लॉग एन' द्वारा दर्शाया गया है जो एक लघुगणकीय कार्य है और उठाए गए चरणों की संख्या लॉग (n + 1) सबसे अधिक है।

सरणी के मध्य तत्व को खोजने के लिए अगला हमें एकल चरण की आवश्यकता होती है यानी ओ (1)।

फिर उप-सरणियों को एन तत्वों की एक सरणी में विलय करने के लिए, हम चल रहे समय की ओ (एन) राशि लेंगे।

इस प्रकार मर्ज सॉर्ट करने का कुल समय n (log n + 1) होगा, जो हमें O (n * logn) की समय जटिलता देता है।

सबसे खराब स्थिति समय जटिलताO (n * लॉग एन)
सबसे अच्छा मामला समय जटिलताO (n * लॉग एन)
औसत समय जटिलताO (n * लॉग एन)
अंतरिक्ष की जटिलतापर)

मर्ज सॉर्ट के लिए समय की जटिलता सभी तीन मामलों (सबसे खराब, सर्वोत्तम और औसत) में समान है क्योंकि यह हमेशा सरणी को उप-सरणियों में विभाजित करता है और फिर रैखिक समय लेने वाले उप-सरणियों का विलय करता है।

मर्ज सॉर्ट हमेशा अनसोल्ड एरेज़ के बराबर स्पेस लेता है। इसलिए जब सूची को सॉर्ट किया जाना एक सरणी है, तो मर्ज सॉर्ट का उपयोग बहुत बड़ी सरणियों के लिए नहीं किया जाना चाहिए। हालाँकि, मर्ज सॉर्ट को लिंक की गई सॉर्टिंग के लिए अधिक प्रभावी ढंग से उपयोग किया जा सकता है।

निष्कर्ष

मर्ज सॉर्ट 'विभाजन और जीत' रणनीति का उपयोग करता है जो सरणी या सूची को कई उप सरणियों में विभाजित करता है और उन्हें व्यक्तिगत रूप से सॉर्ट करता है और फिर एक पूर्ण सॉर्ट किए गए सरणी में विलीन हो जाता है।

मर्ज सॉर्ट अन्य छंटाई विधियों की तुलना में तेजी से करता है और इसी तरह छोटे और बड़े सरणियों के लिए भी कुशलता से काम करता है।

हम अपने आगामी ट्यूटोरियल में क्विक सॉर्ट के बारे में अधिक जानकारी प्राप्त करेंगे!

=> यहां शुरुआती सी ++ प्रशिक्षण गाइड देखें।

अनुशंसित पाठ

^