मर्ज सॉर्ट एल्गोरिथम का परिचय Introduction

मर्ज सॉर्ट "फूट डालो और जीतो" तकनीक पर आधारित एक छँटाई एल्गोरिथ्म है। यह सबसे कुशल सॉर्टिंग एल्गोरिदम में से एक है।

इस लेख में, आप मर्ज सॉर्ट एल्गोरिथम की कार्यप्रणाली के बारे में जानेंगे, मर्ज सॉर्ट का एल्गोरिथम, इसके समय और स्थान की जटिलता, और विभिन्न प्रोग्रामिंग भाषाओं जैसे C++, Python, और. में इसका कार्यान्वयन जावास्क्रिप्ट।

मर्ज सॉर्ट एल्गोरिथम कैसे काम करता है?

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

इस अवधारणा को एक उदाहरण की सहायता से अधिक कुशलता से समझाया जा सकता है। निम्नलिखित तत्वों के साथ एक क्रमबद्ध सरणी पर विचार करें: {16, 12, 15, 13, 19, 17, 11, 18}।

यहां, मर्ज सॉर्ट एल्गोरिथ्म सरणी को दो हिस्सों में विभाजित करता है, दो हिस्सों के लिए खुद को कॉल करता है, और फिर दो सॉर्ट किए गए हिस्सों को मर्ज करता है।

सॉर्ट एल्गोरिथम मर्ज करें

मर्ज सॉर्ट का एल्गोरिथ्म नीचे है:

मर्जसॉर्ट (गिरफ्तारी [], लेफ्टइंडेक्स, राइटइंडेक्स)
अगर लेफ्टइंडेक्स>= राइटइंडेक्स
वापसी
अन्य
मध्य सूचकांक खोजें जो सरणी को दो हिस्सों में विभाजित करता है: 
मिडिलइंडेक्स = लेफ्टइंडेक्स + (राइटइंडेक्स-लेफ्टइंडेक्स)/2
कॉल मर्जसॉर्ट () पहली छमाही के लिए: 
कॉल मर्जसॉर्ट (गिरफ्तारी, बाएं इंडेक्स, मिडिलइंडेक्स)
दूसरी छमाही के लिए mergeSort() को कॉल करें:
कॉल मर्जसॉर्ट (गिरफ्तारी, मिडिलइंडेक्स + 1, राइटइंडेक्स)
चरण 2 और 3 में छांटे गए दो हिस्सों को मिलाएं:
कॉल मर्ज (गिरफ्तारी, लेफ्टइंडेक्स, मिडिलइंडेक्स, राइटइंडेक्स)

सम्बंधित: रिकर्सन क्या है और आप इसका उपयोग कैसे करते हैं?

मर्ज सॉर्ट एल्गोरिथम का समय और स्थान जटिलता

मर्ज सॉर्ट एल्गोरिथ्म को निम्नलिखित पुनरावृत्ति संबंध के रूप में व्यक्त किया जा सकता है:

टी (एन) = 2 टी (एन/2) + ओ (एन)

मास्टर प्रमेय या पुनरावृत्ति ट्री विधि का उपयोग करके इस पुनरावृत्ति संबंध को हल करने के बाद, आपको समाधान O(n logn) के रूप में मिलेगा। इस प्रकार, मर्ज सॉर्ट एल्गोरिथ्म की समय जटिलता है ओ (एन लॉगन).

मर्ज सॉर्ट की सर्वोत्तम-केस समय जटिलता: ओ (एन लॉगन)

मर्ज सॉर्ट की औसत-केस समय जटिलता: ओ (एन लॉगन)

मर्ज सॉर्ट की सबसे खराब स्थिति समय जटिलता: ओ (एन लॉगन)

सम्बंधित: बिग-ओ नोटेशन क्या है?

सहायक अंतरिक्ष जटिलता मर्ज सॉर्ट एल्गोरिथ्म का है पर) जैसा नहीं मर्ज सॉर्ट कार्यान्वयन में सहायक स्थान की आवश्यकता होती है।

सी ++ मर्ज सॉर्ट एल्गोरिथम का कार्यान्वयन

मर्ज सॉर्ट एल्गोरिथ्म का C++ कार्यान्वयन नीचे दिया गया है:

// सी ++ का कार्यान्वयन
// मर्ज सॉर्ट एल्गोरिथ्म
#शामिल 
नेमस्पेस एसटीडी का उपयोग करना;
// यह फ़ंक्शन गिरफ्तारी के दो उप-सरणी विलय करता है []
// लेफ्ट सबअरे: एआर [लेफ्टइंडेक्स..मिडिलइंडेक्स]
// राइट सबअरे: एआर [मिडिलइंडेक्स+1..राइटइंडेक्स]
शून्य मर्ज (int arr[], int leftIndex, int MiddleIndex, int rightIndex)
{
int leftSubarraySize = MiddleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - MiddleIndex;
// अस्थायी सरणियाँ बनाएँ
इंट एल [बाएं सुबरे आकार], आर [दायां सुबरे आकार];
// अस्थायी सरणियों में डेटा की प्रतिलिपि बनाना एल [] और आर []
के लिए (इंट आई = 0; मैं एल [i] = एआर [बाएं इंडेक्स + आई];
के लिए (इंट जे = 0; जे आर [जे] = एआर [मिडिलइंडेक्स + 1 + जे];
// अस्थायी सरणियों को वापस गिरफ्तार में मिलाएं [बाएं इंडेक्स..राइटइंडेक्स]
// लेफ्ट सबअरे का प्रारंभिक सूचकांक
इंट मैं = 0;
// राइट सबरे का प्रारंभिक सूचकांक index
इंट जे = 0;
// मर्ज किए गए सबरे का प्रारंभिक सूचकांक index
इंट के = लेफ्टइंडेक्स;
जबकि (मैं {
अगर (एल [i] <= आर [जे])
{
एआर [के] = एल [i];
मैं++;
}
अन्य
{
एआर [के] = आर [जे];
जे++;
}
के++;
}
// यदि एल में कुछ शेष तत्व हैं []
// गिरफ्तारी के लिए कॉपी करें []
जबकि (मैं {
एआर [के] = एल [i];
मैं++;
के++;
}
// यदि R में कुछ शेष तत्व हैं []
// गिरफ्तारी के लिए कॉपी करें []
जबकि (जे {
एआर [के] = आर [जे];
जे++;
के++;
}
}
शून्य मर्ज सॉर्ट (int arr[], int leftIndex, int rightIndex)
{
अगर (बाएं इंडेक्स> = राइटइंडेक्स)
{
वापसी;
}
इंट मिडिलइंडेक्स = लेफ्टइंडेक्स + (राइटइंडेक्स - लेफ्टइंडेक्स) / 2;
मर्जसॉर्ट (गिरफ्तारी, बाएं इंडेक्स, मिडिलइंडेक्स);
मर्जसॉर्ट (गिरफ्तारी, मिडिलइंडेक्स + 1, राइटइंडेक्स);
मर्ज (गिरफ्तारी, लेफ्टइंडेक्स, मिडिलइंडेक्स, राइटइंडेक्स);
}
// तत्वों को प्रिंट करने का कार्य
// सरणी का
शून्य प्रिंटअरे (int arr[], int size)
{
के लिए (इंट आई = 0; मैं {
cout << गिरफ्तार [i] << "";
}
कोउट << एंडल;
}
// ड्राइवर कोड
मुख्य प्रवेश बिंदु()
{
int arr[] = {16, 12, 15, 13, 19, 17, 11, 18};
int आकार = आकार (गिरफ्तारी) / आकार (गिरफ्तारी [0]);
cout << "बिना क्रमबद्ध सरणी:" << endl;
प्रिंटअरे (गिरफ्तारी, आकार);
मर्जसॉर्ट (गिरफ्तारी, 0, आकार - 1);
cout << "क्रमबद्ध सरणी:" << endl;
प्रिंटअरे (गिरफ्तारी, आकार);
वापसी 0;
}

आउटपुट:

क्रमबद्ध सरणी:
16 12 15 13 19 17 11 18 
क्रमबद्ध सरणी:
11 12 13 15 16 17 18 19

मर्ज सॉर्ट एल्गोरिथम का जावास्क्रिप्ट कार्यान्वयन

मर्ज सॉर्ट एल्गोरिथम का जावास्क्रिप्ट कार्यान्वयन नीचे दिया गया है:

// जावास्क्रिप्ट का कार्यान्वयन
// मर्ज सॉर्ट एल्गोरिथ्म
// यह फ़ंक्शन गिरफ्तारी के दो उप-सरणी विलय करता है []
// लेफ्ट सबअरे: एआर [लेफ्टइंडेक्स..मिडिलइंडेक्स]
// राइट सबअरे: एआर [मिडिलइंडेक्स+1..राइटइंडेक्स]
फ़ंक्शन मर्ज (गिरफ्तारी, लेफ्टइंडेक्स, मिडिलइंडेक्स, राइटइंडेक्स) {
लेफ्टसबर्रे साइज = मिडिलइंडेक्स - लेफ्टइंडेक्स + 1;
चलो सही सुबरे आकार = दायां इंडेक्स - मिडिलइंडेक्स;
// अस्थायी सरणियाँ बनाएँ
वर एल = नया ऐरे (बाएंसुबरे आकार);
वर आर = नया ऐरे (दाएंसुबरे आकार);
// अस्थायी सरणियों में डेटा की प्रतिलिपि बनाना एल [] और आर []
के लिए (चलो मैं = 0; मैंएल [i] = एआर [बाएं इंडेक्स + आई];
}
के लिए (चलो j = 0; जेआर [जे] = एआर [मिडिलइंडेक्स + 1 + जे];
}
// अस्थायी सरणियों को वापस गिरफ्तार में मिलाएं [बाएं इंडेक्स..राइटइंडेक्स]
// लेफ्ट सबअरे का प्रारंभिक सूचकांक
वर मैं = 0;
// राइट सबरे का प्रारंभिक सूचकांक index
वर जे = 0;
// मर्ज किए गए सबरे का प्रारंभिक सूचकांक index
वर के = लेफ्टइंडेक्स;
जबकि (मैं {
अगर (एल [i] <= आर [जे])
{
एआर [के] = एल [i];
मैं++;
}
अन्य
{
एआर [के] = आर [जे];
जे++;
}
के++;
}
// यदि एल में कुछ शेष तत्व हैं []
// गिरफ्तारी के लिए कॉपी करें []
जबकि (मैं {
एआर [के] = एल [i];
मैं++;
के++;
}
// यदि R में कुछ शेष तत्व हैं []
// गिरफ्तारी के लिए कॉपी करें []
जबकि (जे {
एआर [के] = आर [जे];
जे++;
के++;
}
}
फ़ंक्शन मर्जसॉर्ट (गिरफ्तारी, बाएं इंडेक्स, दाएं इंडेक्स) {
अगर (बाएं इंडेक्स> = राइटइंडेक्स) {
वापसी
}
वर मिडिलइंडेक्स = लेफ्टइंडेक्स + पार्सइंट ((राइटइंडेक्स - लेफ्टइंडेक्स) / 2);
मर्जसॉर्ट (गिरफ्तारी, बाएं इंडेक्स, मिडिलइंडेक्स);
मर्जसॉर्ट (गिरफ्तारी, मिडिलइंडेक्स + 1, राइटइंडेक्स);
मर्ज (गिरफ्तारी, लेफ्टइंडेक्स, मिडिलइंडेक्स, राइटइंडेक्स);
}
// तत्वों को प्रिंट करने का कार्य
// सरणी का
फ़ंक्शन प्रिंटअरे (गिरफ्तारी, आकार) {
के लिए (चलो मैं = 0; मैंदस्तावेज़.लिखें (गिरफ्तारी [i] + "");
}
दस्तावेज़.लिखें ("
");
}
// ड्राइवर कोड:
वर गिरफ्तारी = [१६, १२, १५, १३, १९, १७, ११, १८];
वर आकार = गिरफ्तारी लंबाई;
दस्तावेज़.लिखें ("बिना क्रमबद्ध सरणी:
");
प्रिंटअरे (गिरफ्तारी, आकार);
मर्जसॉर्ट (गिरफ्तारी, 0, आकार - 1);
document.write ("क्रमबद्ध सरणी:
");
प्रिंटअरे (गिरफ्तारी, आकार);

आउटपुट:

क्रमबद्ध सरणी:
16 12 15 13 19 17 11 18
क्रमबद्ध सरणी:
11 12 13 15 16 17 18 19

सम्बंधित: गतिशील प्रोग्रामिंग: उदाहरण, सामान्य समस्याएं और समाधान

मर्ज सॉर्ट एल्गोरिथम का पायथन कार्यान्वयन

नीचे मर्ज सॉर्ट एल्गोरिथ्म का पायथन कार्यान्वयन है:

# पायथन का कार्यान्वयन implementation
# मर्ज सॉर्ट एल्गोरिथ्म
डीईएफ़ मर्जसॉर्ट (गिरफ्तारी):
अगर लेन (गिरफ्तारी)> 1:
# सरणी के मध्य सूचकांक का पता लगाना
मिडिलइंडेक्स = लेन (गिरफ्तारी)//2
# सरणी का बायां आधा
एल = एआर [: मिडिलइंडेक्स]
# सरणी का दायां आधा
आर = एआर [मिडिलइंडेक्स:]
# सरणी के पहले भाग को छाँटें
मर्जसॉर्ट (एल)
# सरणी के दूसरे भाग को छाँटें
मर्जसॉर्ट (आर)
# लेफ्ट सबरे का प्रारंभिक सूचकांक index
मैं = 0
# राइट सबरे का प्रारंभिक सूचकांक index
जे = 0
# मर्ज किए गए सबरे का प्रारंभिक सूचकांक index
कश्मीर = 0
# डेटा को अस्थायी सरणियों L[] और R[] में कॉपी करें
जबकि मैं अगर एल [i] गिरफ्तारी [के] = एल [मैं]
मैं = मैं + 1
अन्य:
गिरफ्तारी [के] = आर [जे]
जे = जे + 1
के = के + 1
# जाँच करें कि क्या कुछ तत्व शेष हैं
जबकि मैं गिरफ्तारी [के] = एल [मैं]
मैं = मैं + 1
के = के + 1
जबकि जे गिरफ्तारी [के] = आर [जे]
जे = जे + 1
के = के + 1
# तत्वों को प्रिंट करने का कार्य
#सरणी का
डीईएफ़ प्रिंटअरे (गिरफ्तारी, आकार):
मैं सीमा में (आकार) के लिए:
प्रिंट (गिरफ्तारी [i], अंत = "")
प्रिंट ()
# ड्राइवर कोड
गिरफ्तारी = [१६, १२, १५, १३, १९, १७, ११, १८]
आकार = लेन (गिरफ्तारी)
प्रिंट ("बिना क्रमबद्ध सरणी:")
प्रिंटअरे (गिरफ्तारी, आकार)
मर्जसॉर्ट (गिरफ्तारी)
प्रिंट ("क्रमबद्ध सरणी:")
प्रिंटअरे (गिरफ्तारी, आकार)

आउटपुट:

क्रमबद्ध सरणी:
16 12 15 13 19 17 11 18
क्रमबद्ध सरणी:
11 12 13 15 16 17 18 19

अन्य सॉर्टिंग एल्गोरिदम को समझें

प्रोग्रामिंग में सॉर्टिंग सबसे अधिक उपयोग किए जाने वाले एल्गोरिदम में से एक है। आप विभिन्न प्रोग्रामिंग भाषाओं में तत्वों को त्वरित सॉर्ट, बबल सॉर्ट, मर्ज सॉर्ट, इंसर्शन सॉर्ट इत्यादि जैसे विभिन्न सॉर्टिंग एल्गोरिदम का उपयोग करके सॉर्ट कर सकते हैं।

यदि आप सरलतम छँटाई एल्गोरिथ्म के बारे में सीखना चाहते हैं तो बबल सॉर्ट सबसे अच्छा विकल्प है।

बबल सॉर्ट एल्गोरिथम का परिचय Introduction

बबल सॉर्ट एल्गोरिथ्म: सरणियों को छांटने के लिए एक उत्कृष्ट परिचय।

आगे पढ़िए

लेखक के बारे में