अनुकूली प्रकार: Difference between revisions
(Created page with "एक छँटाई एल्गोरिथ्म अनुकूली सॉर्ट परिवार में आता है यदि वह अपने इ...") |
No edit summary |
||
| Line 1: | Line 1: | ||
एक [[छँटाई एल्गोरिथ्म]] अनुकूली सॉर्ट | एक [[छँटाई एल्गोरिथ्म|सोर्टिंग एल्गोरिदम]] अनुकूली सॉर्ट वर्ग में आता है यदि वह अपने इनपुट में वर्तमान क्रम का लाभ उठाता है। यह इनपुट अनुक्रम में पूर्व-क्रमबद्धता से लाभ उठाता है - या विकार के उपायों की विभिन्न परिभाषाओं के लिए सीमित मात्रा में यादृच्छिकता - और तीव्रता से क्रमबद्ध होता है। अनुकूली सोर्टिंग सामान्यतः वर्तमान सोर्टिंग एल्गोरिदम को संशोधित करके की जाती है। | ||
== प्रेरणा == | == प्रेरणा == | ||
तुलना सॉर्ट | तुलना सॉर्ट एल्गोरिदम पारंपरिक रूप से समय जटिलता से निपटने के समय [[ बिग ओ अंकन | बिग o अंकन]] (''n'' log ''n'') की एक इष्टतम सीमा प्राप्त करने से निपटते हैं। अनुकूली सॉर्ट ठीक समय प्राप्त करने का प्रयास करने के लिए इनपुट के वर्तमान क्रम का लाभ उठाता है, ताकि एल्गोरिदम द्वारा सॉर्ट करने में लगने वाला समय अनुक्रम के आकार और अनुक्रम में अव्यवस्था का सुचारू रूप से बढ़ता फलन हो। दूसरे शब्दों में, इनपुट जितना अधिक क्रमबद्ध होगा, उसे उतनी ही तीव्रता से क्रमबद्ध किया जाना चाहिए। | ||
सॉर्टिंग एल्गोरिदम के लिए यह एक आकर्षक विशेषता है क्योंकि व्यवहार में लगभग सॉर्ट किए गए अनुक्रम | सॉर्टिंग एल्गोरिदम के लिए यह एक आकर्षक विशेषता है क्योंकि व्यवहार में लगभग सॉर्ट किए गए अनुक्रम सामान्य हैं। इस प्रकार, इनपुट में वर्तमान क्रम को ध्यान में रखकर वर्तमान सॉर्ट एल्गोरिदम के निष्पादन में सुधार किया जा सकता है। | ||
ध्यान दें कि सबसे | ध्यान दें कि सबसे निकृष्ट स्थिति वाले सॉर्टिंग एल्गोरिदम जो सबसे निकृष्ट स्थिति में ठीक निष्पादन करते हैं, विशेष रूप से हीप सॉर्ट और [[ मर्ज़ सॉर्ट ]], अपने इनपुट के भीतर वर्तमान क्रम को ध्यान में नहीं रखते हैं, यद्यपि मर्ज सॉर्ट की स्थिति में इस कमी को सरलता से जांच कर ठीक किया जा सकता है। यदि बाएं हाथ के समूह का अंतिम अवयव दाएं समूह के पहले अवयव से कम (या बराबर) है, तो उस स्थिति में मर्ज ऑपरेशन को सरल संयोजन द्वारा प्रतिस्थापित किया जा सकता है - एक संशोधन जो एल्गोरिदम को अनुकूली बनाने के दायरे में है . | ||
== उदाहरण == | == उदाहरण == | ||
| Line 24: | Line 24: | ||
'अंत' | 'अंत' | ||
इस एल्गोरिदम के | इस एल्गोरिदम के निष्पादन को इनपुट में [[उलटा (अलग गणित)]] की संख्या के संदर्भ में वर्णित किया जा सकता है, और फिर {{tmath|T(n)}} लगभग बराबर होगा {{tmath|I(A) + (n - 1)}}, कहाँ {{tmath|I(A)}} व्युत्क्रमणों की संख्या है. पूर्व-क्रमबद्धता के इस माप का उपयोग करते हुए - व्युत्क्रमों की संख्या के सापेक्ष होने के कारण - स्ट्रेट इंसर्शन सॉर्ट को सॉर्ट करने में जितना करीब होता है, कम समय लगता है। | ||
अनुकूली सॉर्टिंग एल्गोरिदम के अन्य उदाहरण हैं अनुकूली | अनुकूली सॉर्टिंग एल्गोरिदम के अन्य उदाहरण हैं अनुकूली हीप सॉर्ट, मर्ज सॉर्ट#प्राकृतिक मर्ज सॉर्ट, धैर्य सॉर्ट,<ref name="Chandramouli">{{Cite conference |last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014|url=https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/patsort-sigmod14.pdf}}</ref> [[शैलसॉर्ट]], [[स्मूथसॉर्ट]], [[ spplaysort ]], [[टिमसॉर्ट]], और कार्टेशियन ट्री#सॉर्टिंग में अनुप्रयोग।<ref>{{cite conference | ||
| last1 = Levcopoulos | first1 = Christos | | last1 = Levcopoulos | first1 = Christos | ||
| last2 = Petersson | first2 = Ola | | last2 = Petersson | first2 = Ola | ||
| Line 41: | Line 41: | ||
== यह भी देखें == | == यह भी देखें == | ||
* [[छँटाई एल्गोरिदम]] | * [[छँटाई एल्गोरिदम|सोर्टिंग एल्गोरिदम]] | ||
* स्मूथसॉर्ट | * स्मूथसॉर्ट | ||
Revision as of 18:23, 1 August 2023
एक सोर्टिंग एल्गोरिदम अनुकूली सॉर्ट वर्ग में आता है यदि वह अपने इनपुट में वर्तमान क्रम का लाभ उठाता है। यह इनपुट अनुक्रम में पूर्व-क्रमबद्धता से लाभ उठाता है - या विकार के उपायों की विभिन्न परिभाषाओं के लिए सीमित मात्रा में यादृच्छिकता - और तीव्रता से क्रमबद्ध होता है। अनुकूली सोर्टिंग सामान्यतः वर्तमान सोर्टिंग एल्गोरिदम को संशोधित करके की जाती है।
प्रेरणा
तुलना सॉर्ट एल्गोरिदम पारंपरिक रूप से समय जटिलता से निपटने के समय बिग o अंकन (n log n) की एक इष्टतम सीमा प्राप्त करने से निपटते हैं। अनुकूली सॉर्ट ठीक समय प्राप्त करने का प्रयास करने के लिए इनपुट के वर्तमान क्रम का लाभ उठाता है, ताकि एल्गोरिदम द्वारा सॉर्ट करने में लगने वाला समय अनुक्रम के आकार और अनुक्रम में अव्यवस्था का सुचारू रूप से बढ़ता फलन हो। दूसरे शब्दों में, इनपुट जितना अधिक क्रमबद्ध होगा, उसे उतनी ही तीव्रता से क्रमबद्ध किया जाना चाहिए।
सॉर्टिंग एल्गोरिदम के लिए यह एक आकर्षक विशेषता है क्योंकि व्यवहार में लगभग सॉर्ट किए गए अनुक्रम सामान्य हैं। इस प्रकार, इनपुट में वर्तमान क्रम को ध्यान में रखकर वर्तमान सॉर्ट एल्गोरिदम के निष्पादन में सुधार किया जा सकता है।
ध्यान दें कि सबसे निकृष्ट स्थिति वाले सॉर्टिंग एल्गोरिदम जो सबसे निकृष्ट स्थिति में ठीक निष्पादन करते हैं, विशेष रूप से हीप सॉर्ट और मर्ज़ सॉर्ट , अपने इनपुट के भीतर वर्तमान क्रम को ध्यान में नहीं रखते हैं, यद्यपि मर्ज सॉर्ट की स्थिति में इस कमी को सरलता से जांच कर ठीक किया जा सकता है। यदि बाएं हाथ के समूह का अंतिम अवयव दाएं समूह के पहले अवयव से कम (या बराबर) है, तो उस स्थिति में मर्ज ऑपरेशन को सरल संयोजन द्वारा प्रतिस्थापित किया जा सकता है - एक संशोधन जो एल्गोरिदम को अनुकूली बनाने के दायरे में है .
उदाहरण
अनुकूली सॉर्टिंग एल्गोरिदम का एक उत्कृष्ट उदाहरण स्ट्रेट इंसर्शन सॉर्ट है।[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.
