मर्ज एल्गोरिदम
कम्प्यूटर विज्ञान मे उन कलनविधियों को अनुक्रमण कलनविधि कहते हैं जो किसी सूची के मूल क्रम बदलकर किसी अन्य क्रम विशेष सूची मे बदलने के काम आता है। इनमें से प्रसिद्ध अनुक्रमण कलनविधि है विलय अनुक्रमण। यह तुलना पर आधारित अनुक्रमण विधि है। विलय अनुक्रमण विभाजन और जीत की विधि पर आधारित है जिसकी खोज जॉन वाॅन न्यूमन ने सन् १९४५ में की थी [1]। विलय अनुक्रमण एक स्थिर अनुक्रमण कलनविधि भी है, जिसमे बराबर वस्तुओं का क्रम नहीं बदलता। इसका विस्तृत विवरण गोल्डस्टीन और न्यूमन की रिपोर्ट मे सामने आयी जो सन् १९४८ में प्रकाशित हुई।
अल्गोरिथम
संपादित करेंविलय अनुक्रमण की संकल्पना कुछ इस प्रकार से किया जा सकता है :
१) एक अनसुलझी सूची जिसमे n संख्या/वस्तु है।
२) अनसुलझी सूची को n उपसूची मे विभाजित करेंगे, जिसमे हर उपसूची मे एक संख्या होगी।
३) बार-बार उपसूची को विलय/मिलाव करके नई सुलझी हुई उपसूची बनाते रहेंगे जब तक एक उपसूची नहीं बच जाती।
कार्यान्वयन
संपादित करें
एक सामान्य विलय अनुक्रमण विधि नीचे से ऊपर के दृष्टिकोण आधारित है। मान लीजिये की एक अनसुलझी सूची ३८ २७ ४३ ३ ९ ८२ १० दी गयी है। इसे सुलझाने के लिए निम्न प्रक्रिया अपनाएंगे :
१) इन संख्याओं को दो उपसूची मे विभाजित करना है।
२) पुनः दो उपसूची को चार उपसूची मे विभाजित करेंगे।
३) फिर इन चार उपसूची को तोड़ने मे सात उपसूची मिल जाएगी जिनमें हर उपसूची मे सिर्फ एक संख्या होगी ।
४) अब जिस प्रकार से उपसूची तोड़ी उसी प्रकार से उपसूची जोड़ेंगे इस बात को ध्यान रखते हुए की नई उपसूची हमेशा सुलझी हुई हो। अब हमें वापस चार सुलझी हुई उपसूची मिलेगी।
५) अब इन चार उपसूची को जोड़ेंगे जिससे दो सुलझी हुई उपसूची मिल जाएगी।
६) अंत मे इन दो सुलझी हुई उपसूची को मिला के एक नई उपसूची बनेगी जो अनुक्रमित होगी।
उदाहरण
संपादित करेंसूची को हर चरण के बाद कुछ इस तरह से देखा जा सकता :
(३८ २७ ४३ ३ ९ ८२ १०)-> (३८ २७ ४३ ३ ),(९ ८२ १० )-> (३८ २७),(४३ ३ ),(९ ८२ ),(१०)-> (३८),(२७),(४३),(३),(९),(८२),(१०)-> (२७ ३८),(३ ४३),(९ ८२),(१०)-> (३ २७ ३८ ४३),(९ १० ८२)-> (३ ९ १० २७ ३८ ४३ ८२)
इसको समझने के लिए दिए गए चित्र का उपयोग कर सकते है।
विश्लेषण
संपादित करेंविलय अनुक्रमण एक स्थिर अनुक्रमण विधि है जिसमे समान संख्या का क्रम नहीं बदलता है संख्या को सुलझाने मे विलय अनुक्रमण का औसत समय और सबसे ख़राब समय की जटिलता O(nlgn) है। अगर n संख्या को कार्य पूरा करने मे t(n) समय लगता है तो T(n) = 2T(n/2) + n जो विलय अनुक्रमण के परिभाषा से पता चलता है [2]। यहाँ 2T(n/2) यह विधि दोबारा दो हिस्सों मे लगाई जाने से आता है और n उन दो उपसूची को जोड़ने का समय बयान करता है। इस पुनरावृत्ति को मास्टर्स थ्योरम के इस्तमाल से हल किया जा सकता है। मास्टर्स थ्योरम T(n) जो की समय की जटिलता है वो O(nlgn) देता है।
समय के बाद अगर जगह की जटिलता देखे तो वह O(n) है। यह जगह दो उपसूची को जोड़ने के वक़्त इस्तेमाल होती है। अगर हमे इसे नयी जगह देने से रोकना है और O(1) जगह जटिलता में करना है तो विलय अनुक्रमण की समय जटिलता O (n*n) हो जाएगी। हालांकि एक तरीका है जिसमे समय O(nlgn) और जगह O(1) होगी। इसमे सूची के एक स्थान में दो संख्या रखने की जरुरत होगी जो डिवीज़न अल्गोरिथम के मदद से हल किया जा सकता है।[3]
सन्दर्भ
संपादित करें | यह लेख एक आधार है। जानकारी जोड़कर इसे बढ़ाने में विकिपीडिया की मदद करें। |
- ↑ Knuth, Donald (1998). The Art of Computer Programming. 3: Sorting and Searching (2nd संस्करण). Addison-Wesley. पपृ॰ 513–558. आई॰ऍस॰बी॰ऍन॰ 978-0-201-89685-5.
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd संस्करण). Massachusetts Institute of Technology. पपृ॰ 253–280. आई॰ऍस॰बी॰ऍन॰ 978-0-262-03384-8.
- ↑ Skiena, Steven S. (2008). "4.5: Mergesort: Sorting by Divide-and-Conquer". The Algorithm Design Manual (2nd संस्करण). Springer. पपृ॰ 120–125. आई॰ऍस॰बी॰ऍन॰ 978-1-84800-069-8.