अनुकूली प्रकार
एक छँटाई एल्गोरिथ्म अनुकूली सॉर्ट परिवार में आता है यदि वह अपने इनपुट में मौजूदा ऑर्डर का लाभ उठाता है। यह इनपुट अनुक्रम में पूर्व-क्रमबद्धता से लाभ उठाता है - या विकार के उपायों की विभिन्न परिभाषाओं के लिए सीमित मात्रा में यादृच्छिकता - और तेजी से क्रमबद्ध होता है। अनुकूली छँटाई आमतौर पर मौजूदा छँटाई एल्गोरिदम को संशोधित करके की जाती है।
प्रेरणा
तुलना सॉर्ट|तुलना-आधारित सॉर्टिंग एल्गोरिदम पारंपरिक रूप से समय जटिलता से निपटने के दौरान बिग ओ अंकन (एन लॉग एन) की एक इष्टतम सीमा प्राप्त करने से निपटते हैं। अनुकूली सॉर्ट बेहतर समय प्राप्त करने का प्रयास करने के लिए इनपुट के मौजूदा क्रम का लाभ उठाता है, ताकि एल्गोरिदम द्वारा सॉर्ट करने में लगने वाला समय अनुक्रम के आकार और अनुक्रम में अव्यवस्था का सुचारू रूप से बढ़ता कार्य हो। दूसरे शब्दों में, इनपुट जितना अधिक क्रमबद्ध होगा, उसे उतनी ही तेजी से क्रमबद्ध किया जाना चाहिए।
सॉर्टिंग एल्गोरिदम के लिए यह एक आकर्षक विशेषता है क्योंकि व्यवहार में लगभग सॉर्ट किए गए अनुक्रम आम हैं। इस प्रकार, इनपुट में मौजूदा ऑर्डर को ध्यान में रखकर मौजूदा सॉर्ट एल्गोरिदम के प्रदर्शन में सुधार किया जा सकता है।
ध्यान दें कि सबसे खराब स्थिति वाले सॉर्टिंग एल्गोरिदम जो सबसे खराब स्थिति में बेहतर प्रदर्शन करते हैं, विशेष रूप से ढेर सॉर्ट और मर्ज़ सॉर्ट , अपने इनपुट के भीतर मौजूदा ऑर्डर को ध्यान में नहीं रखते हैं, हालांकि मर्ज सॉर्ट के मामले में इस कमी को आसानी से जांच कर ठीक किया जा सकता है। यदि बाएं हाथ के समूह का अंतिम तत्व दाएं समूह के पहले तत्व से कम (या बराबर) है, तो उस स्थिति में मर्ज ऑपरेशन को सरल संयोजन द्वारा प्रतिस्थापित किया जा सकता है - एक संशोधन जो एल्गोरिदम को अनुकूली बनाने के दायरे में है .
उदाहरण
अनुकूली सॉर्टिंग एल्गोरिदम का एक उत्कृष्ट उदाहरण स्ट्रेट इंसर्शन सॉर्ट है।[1] इस सॉर्टिंग एल्गोरिदम में, हम इनपुट को बाएं से दाएं स्कैन करते हैं, बार-बार वर्तमान आइटम की स्थिति ढूंढते हैं, और इसे पहले से सॉर्ट किए गए आइटमों की एक सरणी में डालते हैं।
छद्म कोड रूप में, स्ट्रेट इंसर्शन सॉर्ट एल्गोरिदम कुछ इस तरह दिख सकता है (सरणी एक्स शून्य-आधारित है):
'प्रक्रिया' सीधे सम्मिलन सॉर्ट (एक्स):
'for' j := 1 'to' length(X) - 1 'do'
टी := एक्स[जे]
मैं := जे
'जबकि' i > 0 'और' X[i - 1] > t 'करें'
एक्स[आई] := एक्स[आई - 1]
मैं := मैं - 1
'अंत'
एक्स[आई] := टी
'अंत'
इस एल्गोरिदम के प्रदर्शन को इनपुट में उलटा (अलग गणित) की संख्या के संदर्भ में वर्णित किया जा सकता है, और फिर लगभग बराबर होगा , कहाँ व्युत्क्रमणों की संख्या है. पूर्व-क्रमबद्धता के इस माप का उपयोग करते हुए - व्युत्क्रमों की संख्या के सापेक्ष होने के कारण - स्ट्रेट इंसर्शन सॉर्ट को सॉर्ट करने में जितना करीब होता है, कम समय लगता है।
अनुकूली सॉर्टिंग एल्गोरिदम के अन्य उदाहरण हैं अनुकूली ढेर सॉर्ट, मर्ज सॉर्ट#प्राकृतिक मर्ज सॉर्ट, धैर्य सॉर्ट,[2] शैलसॉर्ट, स्मूथसॉर्ट, spplaysort , टिमसॉर्ट, और कार्टेशियन ट्री#सॉर्टिंग में अनुप्रयोग।[3]
यह भी देखें
- छँटाई एल्गोरिदम
- स्मूथसॉर्ट
संदर्भ
- Hagerup, Torben; Jyrki Katjainen (2004). Algorithm Theory – SWAT 2004. Berlin Heidelberg: Springer-Verlag. pp. 221–222. ISBN 3-540-22339-8.
- Mehta, Dinesh P.; Sartaj Sahni (2005). Data Structures and Applications. USA: Chapman & Hall/CRC. pp. 11‑8–11‑9. ISBN 1-58488-435-5.
- Petersson, Ola; Alistair Moffat (1992). A framework for adaptive sorting. Lecture Notes in Computer Science. Vol. 621. Berlin: Springer Berlin / Heidelberg. pp. 422–433. doi:10.1007/3-540-55706-7_38. ISBN 978-3-540-55706-7. ISSN 1611-3349.
- ↑ Estivill-Castro, Vladmir; Wood, Derick (December 1992). "A survey of adaptive sorting algorithms". ACM. New York, NY, USA. 24 (4): 441–476. CiteSeerX 10.1.1.45.8017. doi:10.1145/146370.146381. ISSN 0360-0300. S2CID 1540978.
- ↑ Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors (PDF). SIGMOD/PODS.
- ↑ Levcopoulos, Christos; Petersson, Ola (1989). "Heapsort - Adapted for Presorted Files". WADS '89: Proceedings of the Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science. Vol. 382. London, UK: Springer-Verlag. pp. 499–509. doi:10.1007/3-540-51542-9_41.
