अनुकूली प्रकार: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
एक [[छँटाई एल्गोरिथ्म|सोर्टिंग एल्गोरिदम]] '''अनुकूली सॉर्ट''' वर्ग में आता है यदि वह अपने इनपुट में वर्तमान क्रम का लाभ उठाता है। अतः यह इनपुट अनुक्रम में पूर्व-क्रमबद्धता से लाभ उठाता है - या | एक [[छँटाई एल्गोरिथ्म|सोर्टिंग एल्गोरिदम]] '''अनुकूली सॉर्ट''' वर्ग में आता है यदि वह अपने इनपुट में वर्तमान क्रम का लाभ उठाता है। अतः यह इनपुट अनुक्रम में पूर्व-क्रमबद्धता से लाभ उठाता है - या अक्रम के उपायों की विभिन्न परिभाषाओं के लिए सीमित मात्रा में यादृच्छिकता - और तीव्रता से क्रमबद्ध होता है। इस प्रकार से अनुकूली सोर्टिंग सामान्यतः वर्तमान सोर्टिंग एल्गोरिदम को संशोधित करके की जाती है। | ||
== प्रेरणा == | == प्रेरणा == | ||
तुलना सॉर्ट एल्गोरिदम पारंपरिक रूप से समय जटिलता से निपटने के समय [[ बिग ओ अंकन |बिग o | तुलना सॉर्ट एल्गोरिदम पारंपरिक रूप से समय जटिलता से निपटने के समय [[ बिग ओ अंकन |बिग o नोटेशन]] (''n'' log ''n'') की इष्टतम सीमा प्राप्त करने से निपटते हैं। अनुकूली सॉर्ट ठीक समय प्राप्त करने का प्रयास करने के लिए इनपुट के वर्तमान क्रम का लाभ उठाता है, ताकि एल्गोरिदम द्वारा सॉर्ट करने में लगने वाला समय अनुक्रम के आकार और अनुक्रम में अव्यवस्था का सुचारू रूप से बढ़ता फलन हो। दूसरे शब्दों में, इनपुट जितना अधिक क्रमबद्ध होगा, उसे उतनी ही तीव्रता से क्रमबद्ध किया जाना चाहिए। | ||
अतः सॉर्टिंग एल्गोरिदम के लिए यह आकर्षक विशेषता है क्योंकि व्यवहार में लगभग सॉर्ट किए गए अनुक्रम सामान्य हैं। इस प्रकार, इनपुट में वर्तमान क्रम को ध्यान में रखकर वर्तमान सॉर्ट एल्गोरिदम के निष्पादन में सुधार किया जा सकता है। | अतः सॉर्टिंग एल्गोरिदम के लिए यह आकर्षक विशेषता है क्योंकि व्यवहार में लगभग सॉर्ट किए गए अनुक्रम सामान्य हैं। इस प्रकार, इनपुट में वर्तमान क्रम को ध्यान में रखकर वर्तमान सॉर्ट एल्गोरिदम के निष्पादन में सुधार किया जा सकता है। | ||
| Line 9: | Line 9: | ||
== उदाहरण == | == उदाहरण == | ||
अतः इस प्रकार से अनुकूली सॉर्टिंग एल्गोरिदम का उत्कृष्ट उदाहरण स्ट्रेट | अतः इस प्रकार से अनुकूली सॉर्टिंग एल्गोरिदम का उत्कृष्ट उदाहरण स्ट्रेट इन्सर्टेशन सॉर्ट है।<ref name="Estivill"/> इस सॉर्टिंग एल्गोरिदम में, हम इनपुट को बाएं से दाएं स्कैन करते हैं, बार-बार वर्तमान आइटम की स्थिति ढूंढते हैं, और इसे पहले से सॉर्ट किए गए आइटमों की सरणी में डालते हैं। | ||
इस प्रकार से [[छद्म कोड]] रूप में, स्ट्रेट | इस प्रकार से [[छद्म कोड|स्यूडो कोड]] रूप में, स्ट्रेट इन्सर्टेशन सॉर्ट एल्गोरिदम कुछ इस प्रकार दिख सकता है (सरणी एक्स शून्य-आधारित है): | ||
'''procedure''' Straight Insertion Sort (X): | '''procedure''' Straight Insertion Sort (X): | ||
| Line 25: | Line 25: | ||
X[i] := t | X[i] := t | ||
'''end''' | '''end''' | ||
अतः इस एल्गोरिदम के निष्पादन को इनपुट में [[उलटा (अलग गणित)|व्युत्क्रमों]] की संख्या के संदर्भ में वर्णित किया जा सकता है, और फिर {{tmath|T(n)}} लगभग {{tmath|I(A) + (n - 1)}} के बराबर होगा, जहां {{tmath|I(A)}} व्युत्क्रमों की संख्या है। पूर्व-क्रमबद्धता के इस माप का उपयोग करते हुए - व्युत्क्रमों की संख्या के सापेक्ष होने के कारण - स्ट्रेट | अतः इस एल्गोरिदम के निष्पादन को इनपुट में [[उलटा (अलग गणित)|व्युत्क्रमों]] की संख्या के संदर्भ में वर्णित किया जा सकता है, और फिर {{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 | इस प्रकार से अनुकूली सॉर्टिंग एल्गोरिदम के अन्य उदाहरण अनुकूली हीप सॉर्ट, मर्ज सॉर्ट या प्राकृतिक मर्ज सॉर्ट, पेसेंस सॉर्ट,<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 | ||
Revision as of 10:02, 5 August 2023
एक सोर्टिंग एल्गोरिदम अनुकूली सॉर्ट वर्ग में आता है यदि वह अपने इनपुट में वर्तमान क्रम का लाभ उठाता है। अतः यह इनपुट अनुक्रम में पूर्व-क्रमबद्धता से लाभ उठाता है - या अक्रम के उपायों की विभिन्न परिभाषाओं के लिए सीमित मात्रा में यादृच्छिकता - और तीव्रता से क्रमबद्ध होता है। इस प्रकार से अनुकूली सोर्टिंग सामान्यतः वर्तमान सोर्टिंग एल्गोरिदम को संशोधित करके की जाती है।
प्रेरणा
तुलना सॉर्ट एल्गोरिदम पारंपरिक रूप से समय जटिलता से निपटने के समय बिग o नोटेशन (n log n) की इष्टतम सीमा प्राप्त करने से निपटते हैं। अनुकूली सॉर्ट ठीक समय प्राप्त करने का प्रयास करने के लिए इनपुट के वर्तमान क्रम का लाभ उठाता है, ताकि एल्गोरिदम द्वारा सॉर्ट करने में लगने वाला समय अनुक्रम के आकार और अनुक्रम में अव्यवस्था का सुचारू रूप से बढ़ता फलन हो। दूसरे शब्दों में, इनपुट जितना अधिक क्रमबद्ध होगा, उसे उतनी ही तीव्रता से क्रमबद्ध किया जाना चाहिए।
अतः सॉर्टिंग एल्गोरिदम के लिए यह आकर्षक विशेषता है क्योंकि व्यवहार में लगभग सॉर्ट किए गए अनुक्रम सामान्य हैं। इस प्रकार, इनपुट में वर्तमान क्रम को ध्यान में रखकर वर्तमान सॉर्ट एल्गोरिदम के निष्पादन में सुधार किया जा सकता है।
इस प्रकार से ध्यान दें कि सबसे निकृष्ट स्थिति वाले सॉर्टिंग एल्गोरिदम जो सबसे निकृष्ट स्थिति में ठीक निष्पादन करते हैं, विशेष रूप से हीप सॉर्ट और मर्ज़ सॉर्ट , अपने इनपुट के भीतर वर्तमान क्रम को ध्यान में नहीं रखते हैं, यद्यपि मर्ज सॉर्ट की स्थिति में इस कमी को सरलता से जांच कर ठीक किया जा सकता है। यदि बाएं हाथ के समूह का अंतिम अवयव दाएं समूह के पहले अवयव से कम (या बराबर) है, तो ऐसी स्थिति में मर्ज ऑपरेशन को सरल संयोजन द्वारा प्रतिस्थापित किया जा सकता है - एक संशोधन जो एल्गोरिदम को अनुकूली बनाने के अंतर्गत है।
उदाहरण
अतः इस प्रकार से अनुकूली सॉर्टिंग एल्गोरिदम का उत्कृष्ट उदाहरण स्ट्रेट इन्सर्टेशन सॉर्ट है।[1] इस सॉर्टिंग एल्गोरिदम में, हम इनपुट को बाएं से दाएं स्कैन करते हैं, बार-बार वर्तमान आइटम की स्थिति ढूंढते हैं, और इसे पहले से सॉर्ट किए गए आइटमों की सरणी में डालते हैं।
इस प्रकार से स्यूडो कोड रूप में, स्ट्रेट इन्सर्टेशन सॉर्ट एल्गोरिदम कुछ इस प्रकार दिख सकता है (सरणी एक्स शून्य-आधारित है):
procedure Straight Insertion Sort (X):
for j := 1 to length(X) - 1 do
t := X[j]
i := j
while i > 0 and X[i - 1] > t do
X[i] := X[i - 1]
i := i - 1
end
X[i] := t
end
अतः इस एल्गोरिदम के निष्पादन को इनपुट में व्युत्क्रमों की संख्या के संदर्भ में वर्णित किया जा सकता है, और फिर लगभग के बराबर होगा, जहां व्युत्क्रमों की संख्या है। पूर्व-क्रमबद्धता के इस माप का उपयोग करते हुए - व्युत्क्रमों की संख्या के सापेक्ष होने के कारण - स्ट्रेट इन्सर्टेशन सॉर्ट को सॉर्ट करने में जितना निकट होता है, कम समय लगता है।
इस प्रकार से अनुकूली सॉर्टिंग एल्गोरिदम के अन्य उदाहरण अनुकूली हीप सॉर्ट, मर्ज सॉर्ट या प्राकृतिक मर्ज सॉर्ट, पेसेंस सॉर्ट,[2] शैलसॉर्ट, स्मूथसॉर्ट, एसपीप्लेसॉर्ट , टिमसॉर्ट, और कार्टेशियन ट्री सॉर्टिंग में अनुप्रयोग हैं।[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.
