शैलसॉर्ट: Difference between revisions
No edit summary |
No edit summary |
||
Line 21: | Line 21: | ||
|optimal=नहीं | |optimal=नहीं | ||
}} | }} | ||
[[File:Shell sorting algorithm color bars.svg|thumb|alt=The steps of Shellsort.|शेलसॉर्ट के क्रमिक चरणों में 5, 3, 1 के अंतराल के साथ वस्तुओं के जोड़े की अदला-बदली]]'''शेलसॉर्ट''', जिसे शेल सॉर्ट या शेल विधि के रूप में भी जाना जाता है, एक [[इन-प्लेस एल्गोरिदम]] | [[File:Shell sorting algorithm color bars.svg|thumb|alt=The steps of Shellsort.|शेलसॉर्ट के क्रमिक चरणों में 5, 3, 1 के अंतराल के साथ वस्तुओं के जोड़े की अदला-बदली]]'''शेलसॉर्ट''', जिसे शेल सॉर्ट या शेल विधि के रूप में भी जाना जाता है, एक [[इन-प्लेस एल्गोरिदम]] या इन-प्लेस तुलना सॉर्ट है। इसे या तो एक्सचेंज (बबल सॉर्ट ) द्वारा सॉर्टिंग या इंसर्शन ([[ सम्मिलन सॉर्ट ]]) द्वारा सॉर्टिंग के सामान्यीकरण के रूप में देखा जा सकता है।<ref name="Knuth" />यह विधि एक दूसरे से दूर तत्वों के जोड़े को क्रमबद्ध करने से प्रारंभ होती है, फिर तुलना किए जाने वाले तत्वों के बीच के अंतर को धीरे-धीरे कम करती है। दूर-दूर के तत्वों से प्रारंभ करके, यह एक साधारण निकटतम समीप एक्सचेंज की तुलना में कुछ बाहर के तत्वों को तेजी से स्थिति में ले जा सकता है। [[ डोनाल्ड शैल |डोनाल्ड शैल]] ने इस प्रकार का पहला संस्करण 1959 में प्रकाशित किया था।<ref name="Shell">{{Cite journal | ||
|url=http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf | |url=http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf | ||
|last=Shell | |last=Shell | ||
Line 39: | Line 39: | ||
== विवरण == | == विवरण == | ||
शेलसॉर्ट सम्मिलन सॉर्ट का एक अनुकूलन है जो दूर-दूर स्थित वस्तुओं के आदान-प्रदान की अनुमति देता है। विचार यह है कि तत्वों की सूची को व्यवस्थित किया जाए जिससे, कहीं से भी प्रारंभ करके, प्रत्येक hवें | शेलसॉर्ट सम्मिलन सॉर्ट का एक अनुकूलन है जो दूर-दूर स्थित वस्तुओं के आदान-प्रदान की अनुमति देता है। विचार यह है कि तत्वों की सूची को व्यवस्थित किया जाए जिससे, कहीं से भी प्रारंभ करके, प्रत्येक hवें तत्व को लेने से एक क्रमबद्ध सूची तैयार हो सकता है। ऐसी सूची को h-सॉर्टेड कहा जाता है। इसे इंटरलीव्ड सूचियों के रूप में भी सोचा जा सकता है, प्रत्येक को व्यक्तिगत रूप से क्रमबद्ध किया गया है।<ref name="Sedgewick"> | ||
{{Cite book | {{Cite book | ||
|last=Sedgewick | |last=Sedgewick | ||
Line 98: | Line 98: | ||
पहला पास, 5-सॉर्टिंग, पांच अलग-अलग उपसरणी (''a''<sub>1</sub>, ''a''<sub>6</sub>, ''a''<sub>11</sub>), (''a''<sub>2</sub>, ''a''<sub>7</sub>, ''a''<sub>12</sub>), (''a''<sub>3</sub>, ''a''<sub>8</sub>), (''a''<sub>4</sub>, ''a''<sub>9</sub>), (''a''<sub>5</sub>, ''a''<sub>10</sub>). पर इंसर्शन सॉर्ट करता है। उदाहरण के लिए, यह उपसरणी | पहला पास, 5-सॉर्टिंग, पांच अलग-अलग उपसरणी (''a''<sub>1</sub>, ''a''<sub>6</sub>, ''a''<sub>11</sub>), (''a''<sub>2</sub>, ''a''<sub>7</sub>, ''a''<sub>12</sub>), (''a''<sub>3</sub>, ''a''<sub>8</sub>), (''a''<sub>4</sub>, ''a''<sub>9</sub>), (''a''<sub>5</sub>, ''a''<sub>10</sub>). पर इंसर्शन सॉर्ट करता है। उदाहरण के लिए, यह उपसरणी (''a''<sub>1</sub>, ''a''<sub>6</sub>, ''a''<sub>11</sub>) को (62, 17, 25) से (17, 25, 62) में बदल देता है। अगला पास, 3-सॉर्टिंग, तीन उपसरणी (''a''<sub>1</sub>, ''a''<sub>4</sub>, ''a''<sub>7</sub>, ''a''<sub>10</sub>), (''a''<sub>2</sub>, ''a''<sub>5</sub>, ''a''<sub>8</sub>, ''a''<sub>11</sub>), (''a''<sub>3</sub>, ''a''<sub>6</sub>, ''a''<sub>9</sub>, ''a''<sub>12</sub>). पर इंसर्शन सॉर्ट करता है। अंतिम पास, 1-सॉर्टिंग, संपूर्ण सरणी (''a''<sub>1</sub>,..., ''a''<sub>12</sub>).का एक सामान्य सम्मिलन प्रकार है। | ||
जैसा कि उदाहरण से पता चलता है कि शेलसॉर्ट जिस उपसरणी पर काम करता है वह प्रारंभ में छोटी होती है, बाद में लंबी हो जाती है किंतु लगभग क्रमबद्ध हो जाती है। दोनों ही स्थिति में इंसर्शन सॉर्ट कुशलता से काम करता है। | जैसा कि उदाहरण से पता चलता है कि शेलसॉर्ट जिस उपसरणी पर काम करता है वह प्रारंभ में छोटी होती है, बाद में लंबी हो जाती है किंतु लगभग क्रमबद्ध हो जाती है। दोनों ही स्थिति में इंसर्शन सॉर्ट कुशलता से काम करता है। | ||
Line 351: | Line 351: | ||
}}</ref> | }}</ref> | ||
|} | |} | ||
जब N के द्विआधारी प्रतिनिधित्व में कई निरन्तर शून्य होते हैं, तो शेल के मूल अंतराल अनुक्रम का उपयोग करके शेलसॉर्ट Θ(N<sup>2</sup>) बनाता है सबसे खराब स्थिति में तुलना करना उदाहरण के लिए, यह | जब N के द्विआधारी प्रतिनिधित्व में कई निरन्तर शून्य होते हैं, तो शेल के मूल अंतराल अनुक्रम का उपयोग करके शेलसॉर्ट Θ(N<sup>2</sup>) बनाता है सबसे खराब स्थिति में तुलना करना उदाहरण के लिए, यह स्थिति दो की घात के समान एन के लिए होता है जब माध्यिका से बड़े और छोटे तत्व क्रमशः विषम और सम स्थिति में होते हैं, क्योंकि उनकी तुलना केवल अंतिम पास में की जाती है। | ||
चूँकि | चूँकि इसमें ''O''(''N'' log ''N'') की तुलना में अधिक जटिलता है जो तुलनात्मक प्रकारों के लिए इष्टतम है, प्रैट का संस्करण नेटवर्क को सॉर्ट करने के लिए उपयुक्त है और इसमें बैचर के [[बिटोनिक सॉर्टर]] के समान ही एसिम्प्टोटिक गेट जटिलता है। | ||
गोनेट और बेज़ा-येट्स ने देखा कि शेलसॉर्ट औसतन सबसे कम तुलना करता है जब क्रमिक अंतराल का अनुपात लगभग 2.2 के समान होता है।<ref name="Gonnet"/> यही कारण है कि अनुपात 2.2 के साथ उनका अनुक्रम और 2.25 अनुपात के साथ टोकुडा का अनुक्रम कुशल सिद्ध होता है। चूँकि ऐसा क्यों है ये पता नहीं चल पाया है. सेडगेविक उन अंतरालों का उपयोग करने की अनुशंसा करता है जिनमें सबसे बड़े सामान्य भाजक कम होते हैं या जोड़ीवार सहअभाज्य होते हैं।<ref>{{Cite book | गोनेट और बेज़ा-येट्स ने देखा कि शेलसॉर्ट औसतन सबसे कम तुलना करता है जब क्रमिक अंतराल का अनुपात लगभग 2.2 के समान होता है।<ref name="Gonnet"/> यही कारण है कि अनुपात 2.2 के साथ उनका अनुक्रम और 2.25 अनुपात के साथ टोकुडा का अनुक्रम कुशल सिद्ध होता है। चूँकि ऐसा क्यों है ये पता नहीं चल पाया है. सेडगेविक उन अंतरालों का उपयोग करने की अनुशंसा करता है जिनमें सबसे बड़े सामान्य भाजक कम होते हैं या जोड़ीवार सहअभाज्य होते हैं।<ref>{{Cite book | ||
Line 364: | Line 364: | ||
|year=1998 | |year=1998 | ||
|pages=285–292 | |pages=285–292 | ||
|isbn=978-0-201-35088-3}}</ref> | |isbn=978-0-201-35088-3}}</ref> विषम संख्या वाले अंतराल व्यवहार में अच्छा काम करते प्रतीत होते हैं: सम-संख्या वाले अंतराल से बचकर 25% की कमी देखी गई है। 3 और 5 के गुणकों से बचने वाले अंतराल <10% के छोटे लाभ उत्पन्न करते प्रतीत होते हैं। | ||
तुलनाओं की औसत संख्या के संबंध में, सिउरा के अनुक्रम <ref name=":0" /> का सबसे अच्छा ज्ञात प्रदर्शन है; 701 से अंतराल निर्धारित नहीं किए गए थे किंतु अनुक्रम को पुनरावर्ती सूत्र <math>h_k = \lfloor 2.25 h_{k-1} \rfloor</math> के अनुसार आगे बढ़ाया जा सकता है। | तुलनाओं की औसत संख्या के संबंध में, सिउरा के अनुक्रम <ref name=":0" /> का सबसे अच्छा ज्ञात प्रदर्शन है; 701 से अंतराल निर्धारित नहीं किए गए थे किंतु अनुक्रम को पुनरावर्ती सूत्र <math>h_k = \lfloor 2.25 h_{k-1} \rfloor</math> के अनुसार आगे बढ़ाया जा सकता है। | ||
Line 370: | Line 370: | ||
टोकुडा का अनुक्रम, सरल सूत्र द्वारा परिभाषित <math>h_k = \lceil h'_k \rceil</math>, जहाँ <math>h'_k = 2.25 h'_{k-1} + 1</math>, <math>h'_1 = 1</math>, व्यावहारिक अनुप्रयोगों के लिए अनुशंसित किया जा सकता है। | टोकुडा का अनुक्रम, सरल सूत्र द्वारा परिभाषित <math>h_k = \lceil h'_k \rceil</math>, जहाँ <math>h'_k = 2.25 h'_{k-1} + 1</math>, <math>h'_1 = 1</math>, व्यावहारिक अनुप्रयोगों के लिए अनुशंसित किया जा सकता है। | ||
यदि अधिकतम इनपुट आकार छोटा है, जैसा कि तब हो सकता है जब शेलसॉर्ट का उपयोग किसी अन्य पुनरावर्ती सॉर्टिंग एल्गोरिदम जैसे कि [[जल्दी से सुलझाएं|क्विकसॉर्ट]] | यदि अधिकतम इनपुट आकार छोटा है, जैसा कि तब हो सकता है जब शेलसॉर्ट का उपयोग किसी अन्य पुनरावर्ती सॉर्टिंग एल्गोरिदम जैसे कि [[जल्दी से सुलझाएं|क्विकसॉर्ट]] या [[ मर्ज़ सॉर्ट |मर्ज़ सॉर्ट]] द्वारा छोटे उप-सरणी पर किया जाता है, तो प्रत्येक इनपुट आकार के लिए एक इष्टतम अनुक्रम को सारणीबद्ध करना संभव है।<ref>{{cite web | ||
|title=How to choose the lengths of my sub sequences for a shell sort? | |title=How to choose the lengths of my sub sequences for a shell sort? | ||
|first=Olof |last=Forshell | |first=Olof |last=Forshell | ||
Line 394: | Line 394: | ||
|url=https://core.ac.uk/download/pdf/82277625.pdf | |url=https://core.ac.uk/download/pdf/82277625.pdf | ||
|doi-access=free | |doi-access=free | ||
}}</ref> प्रत्येक ''h''<sub>1</sub>-सॉर्टेड और ''h''<sub>2</sub>-सॉर्टेड सरणी भी (''a''<sub>1</sub>''h''<sub>1</sub>+''a''<sub>2</sub>''h''<sub>2</sub>)--सॉर्टेड है, किसी भी गैर-नकारात्मक पूर्णांक ''a''<sub>1</sub> और ''a''<sub>2</sub> के लिए शेलसॉर्ट की सबसे खराब स्थिति वाली जटिलता फ्रोबेनियस समस्या से जुड़ी है: दिए गए पूर्णांक ''h''<sub>1</sub>,..., ''h<sub>n</sub>'' के लिए gcd = 1 के साथ, फ्रोबेनियस संख्या | }}</ref> प्रत्येक ''h''<sub>1</sub>-सॉर्टेड और ''h''<sub>2</sub>-सॉर्टेड सरणी भी (''a''<sub>1</sub>''h''<sub>1</sub>+''a''<sub>2</sub>''h''<sub>2</sub>)--सॉर्टेड है, किसी भी गैर-नकारात्मक पूर्णांक ''a''<sub>1</sub> और ''a''<sub>2</sub> के लिए शेलसॉर्ट की सबसे खराब स्थिति वाली जटिलता फ्रोबेनियस समस्या से जुड़ी है: दिए गए पूर्णांक ''h''<sub>1</sub>,..., ''h<sub>n</sub>'' के लिए gcd = 1 के साथ, फ्रोबेनियस संख्या ''g''(''h''<sub>1</sub>,..., ''h<sub>n</sub>'') सबसे बड़ा पूर्णांक है जिसे नहीं किया जा सकता है गैरऋणात्मक पूर्णांक ''a''<sub>1</sub>,..., ''a<sub>n</sub>''. के साथ ''a''<sub>1</sub>''h''<sub>1</sub>+ ... +''a<sub>n</sub>h<sub>n</sub>'' के रूप में दर्शाया गया है। फ्रोबेनियस संख्याओं के लिए ज्ञात सूत्रों का उपयोग करके, हम अंतराल अनुक्रमों के कई वर्गों के लिए शेलसॉर्ट की सबसे खराब स्थिति की जटिलता निर्धारित कर सकते हैं। सिद्ध परिणाम उपरोक्त तालिका में दिखाए गए हैं।<ref>{{Cite journal | ||
|last=Selmer | |last=Selmer | ||
|first=Ernst S. | |first=Ernst S. | ||
Line 411: | Line 411: | ||
}}</ref> | }}</ref> | ||
मार्क एलन वीस ने सिद्ध किया कि शेलसॉर्ट ''O''(''N'' log ''N'') | मार्क एलन वीस ने सिद्ध किया कि शेलसॉर्ट ''O''(''N'' log ''N'') समय में चलता है जब इनपुट सरणी विपरीत क्रम में होती है।<ref>{{Cite journal | ||
|last=Weiss | |last=Weiss | ||
|first=Mark Allen | |first=Mark Allen | ||
Line 421: | Line 421: | ||
}}</ref> | }}</ref> | ||
संचालन की औसत संख्या के संबंध में, कोई भी सिद्ध परिणाम व्यावहारिक अंतराल अनुक्रम से संबंधित नहीं है। उन अंतरालों के लिए जो दो की घात हैं, एस्पेलिड ने इस औसत की गणना <math>0.5349N\sqrt{N}-0.4387N-0.097\sqrt{N}+O(1)</math> के रूप में की।<ref name="Knuth" /> नुथ ने दो अंतराल (h, 1) | संचालन की औसत संख्या के संबंध में, कोई भी सिद्ध परिणाम व्यावहारिक अंतराल अनुक्रम से संबंधित नहीं है। उन अंतरालों के लिए जो दो की घात हैं, एस्पेलिड ने इस औसत की गणना <math>0.5349N\sqrt{N}-0.4387N-0.097\sqrt{N}+O(1)</math> के रूप में की।<ref name="Knuth" /> नुथ ने दो अंतराल (h, 1) के साथ एन-तत्व सरणी को सॉर्ट करने की औसत जटिलता को <math>\frac{2N^2}{h} + \sqrt{\pi N^3 h}</math> निर्धारित किया।<ref name="Knuth" /> यह इस प्रकार है कि ''h'' = Θ(''N''<sup>1/3</sup>) के साथ दो-पास शेलसॉर्ट औसतन ''O''(''N''<sup>5/3</sup>) तुलना/व्युत्क्रम/चलने का समय बनाता है। याओ ने तीन-पास शेलसॉर्ट की औसत जटिलता पाई।<ref>{{Cite journal | ||
|last=Yao | |last=Yao | ||
|first=Andrew Chi-Chih | |first=Andrew Chi-Chih | ||
Line 453: | Line 453: | ||
|citeseerx=10.1.1.54.9911 | |citeseerx=10.1.1.54.9911 | ||
|url=http://www2.math.uu.se/~svante/papers/sj113.pdf | |url=http://www2.math.uu.se/~svante/papers/sj113.pdf | ||
}}</ref> तीन अंतरालों (सीएच, सीजी, 1) के साथ शेलसॉर्ट के दौरान की गई तुलना/व्युत्क्रम/चलने के समय की औसत संख्या, जहां एच और जी सहअभाज्य हैं, {2} है। पहले पास में,<math>\frac{N^2}{4ch} + O(N)</math> दूसरे पास में और <math>\frac{1}{8g}\sqrt{\frac{\pi}{ch}}(h - 1)N^{3/2} + O(hN)</math> तीसरे पास में। अंतिम सूत्र में ψ(h, g) एक जटिल फलन है जो असममित रूप से {5} के बराबर है। विशेष रूप से, जब h = Θ(N<sup>7/15) | }}</ref> तीन अंतरालों (सीएच, सीजी, 1) के साथ शेलसॉर्ट के दौरान की गई तुलना/व्युत्क्रम/चलने के समय की औसत संख्या, जहां एच और जी सहअभाज्य हैं, {2} है। पहले पास में,<math>\frac{N^2}{4ch} + O(N)</math> दूसरे पास में और <math>\frac{1}{8g}\sqrt{\frac{\pi}{ch}}(h - 1)N^{3/2} + O(hN)</math> तीसरे पास में। अंतिम सूत्र में ψ(h, g) एक जटिल फलन है जो असममित रूप से {5} के बराबर है। विशेष रूप से, जब h = Θ(N<sup>7/15) और g = Θ(N1/5),, छँटाई का औसत समय ''O''(''N''<sup>23/15). है। | ||
प्रयोगों के आधार पर, यह अनुमान लगाया गया है कि हिब्बार्ड के अंतराल अनुक्रम के साथ शेलसॉर्ट ''O''(''N''<sup>5/4</sup>) | प्रयोगों के आधार पर, यह अनुमान लगाया गया है कि हिब्बार्ड के अंतराल अनुक्रम के साथ शेलसॉर्ट ''O''(''N''<sup>5/4</sup>) औसत समय में चलता है,<ref name="Knuth" /> और गोनेट और बेज़ा-येट्स के अनुक्रम को औसतन 0.41N ln N (ln ln N + 1/6) की आवश्यकता होती है ) तत्व चलता है।<ref name="Gonnet" /> जब क्रमबद्ध सरणियों में लाखों तत्व होते हैं तो अन्य अनुक्रमों के लिए पूर्व में रखे गए संचालन की औसत संख्या का अनुमान विफल हो जाता है। | ||
नीचे दिया गया ग्राफ़ शेलसॉर्ट के विभिन्न वेरिएंट में तत्व तुलनाओं की औसत संख्या को सैद्धांतिक निचली सीमा, अथार्त | नीचे दिया गया ग्राफ़ शेलसॉर्ट के विभिन्न वेरिएंट में तत्व तुलनाओं की औसत संख्या को सैद्धांतिक निचली सीमा, अथार्त log<sub>2</sub>''N''! से विभाजित करके दिखाता है! जहां क्रम 1, 4, 10, 23, 57, 132, 301, 701 को सूत्र <math>h_k = \lfloor2.25 h_{k-1}\rfloor</math> के अनुसार बढ़ाया गया है। | ||
[[File:Shell sort average number of comparisons (English).svg|center]] | [[File:Shell sort average number of comparisons (English).svg|center]] | ||
Line 484: | Line 484: | ||
|arxiv=cs/9906008 | |arxiv=cs/9906008 | ||
|s2cid=3265123 | |s2cid=3265123 | ||
}}</ref> ने पी-पास शेलसॉर्ट में संचालन/चलने के समय की औसत संख्या के क्रम के लिए निम्नलिखित निचली सीमा साबित की:Ω(''pN''<sup>1+1/''p''</sup>) जब ''p'' ≤ log<sub>2</sub>''N'' और Ω(''pN'') जब | }}</ref> ने पी-पास शेलसॉर्ट में संचालन/चलने के समय की औसत संख्या के क्रम के लिए निम्नलिखित निचली सीमा साबित की:Ω(''pN''<sup>1+1/''p''</sup>) जब ''p'' ≤ log<sub>2</sub>''N'' और Ω(''pN'') जब ''p'' > log<sub>2</sub>''N''. इसलिए, शेलसॉर्ट के पास औसत समय में चलने की संभावनाएं हैं जो केवल अंतराल अनुक्रमों का उपयोग करते समय एन लॉगएन की तरह बढ़ती है जिनकी अंतराल की संख्या सरणी आकार के लघुगणक के अनुपात में बढ़ती है। हालाँकि, यह अज्ञात है कि क्या शेलसॉर्ट औसत-केस जटिलता के इस स्पर्शोन्मुख क्रम तक पहुँच सकता है, जो तुलनात्मक प्रकारों के लिए इष्टतम है। <math>p</math> से <math> | ||
\Omega ( N\sum_{k=1}^p h_{k-1}/h_k ) | \Omega ( N\sum_{k=1}^p h_{k-1}/h_k ) | ||
</math>तक की प्रत्येक संख्या के लिए निचली सीमा को विटैनी<ref>{{cite journal | </math>तक की प्रत्येक संख्या के लिए निचली सीमा को विटैनी<ref>{{cite journal | ||
Line 548: | Line 548: | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
शेलसॉर्ट अधिक संचालन करता है और इसमें क्विकसॉर्ट की तुलना में अधिक सीपीयू कैश या कैश मिस होता है। चूँकि | शेलसॉर्ट अधिक संचालन करता है और इसमें क्विकसॉर्ट की तुलना में अधिक सीपीयू कैश या कैश मिस होता है। चूँकि इसे छोटे कोड का उपयोग करके कार्यान्वित किया जा सकता है और [[कॉल स्टैक]] का उपयोग नहीं किया जाता है, [[ अंतः स्थापित प्रणालियाँ |अंतः स्थापित प्रणालियाँ]] पर लक्षित सी मानक लाइब्रेरी में [[क्यूसॉर्ट]] फ़ंक्शन के कुछ कार्यान्वयन क्विकॉर्ट के अतिरिक्त इसका उपयोग करते हैं। उदाहरण के लिए, शेलसॉर्ट का उपयोग [[uClibc|यूक्लिब]] लाइब्रेरी में किया जाता है।<ref>{{Cite web | ||
| url=http://git.uclibc.org/uClibc/tree/libc/stdlib/stdlib.c#n700 | | url=http://git.uclibc.org/uClibc/tree/libc/stdlib/stdlib.c#n700 | ||
| title=libc/stdlib/stdlib.c | | title=libc/stdlib/stdlib.c | ||
Line 566: | Line 566: | ||
== यह भी देखें == | == यह भी देखें == | ||
* [[कंघी सॉर्ट करें|कोंब सॉर्ट | * [[कंघी सॉर्ट करें|कोंब सॉर्ट]] | ||
== संदर्भ == | == संदर्भ == |
Revision as of 12:30, 4 July 2023
Class | सॉर्टिंग एल्गोरिदम |
---|---|
Data structure | ऐरे |
Worst-case performance | O(n2) (worst known worst case gap sequence) O(n log2n) (best known worst case gap sequence)[1] |
Best-case performance | O(n log n) (अधिकांश अंतराल अनुक्रम) O(n log2n) (सबसे प्रसिद्ध सबसे खराब स्थिति वाला गैप अनुक्रम)[2] |
Average performance | अंतराल अनुक्रम पर निर्भर करता है |
Worst-case space complexity | О(n) कुल, O(1) सहायक |
शेलसॉर्ट, जिसे शेल सॉर्ट या शेल विधि के रूप में भी जाना जाता है, एक इन-प्लेस एल्गोरिदम या इन-प्लेस तुलना सॉर्ट है। इसे या तो एक्सचेंज (बबल सॉर्ट ) द्वारा सॉर्टिंग या इंसर्शन (सम्मिलन सॉर्ट ) द्वारा सॉर्टिंग के सामान्यीकरण के रूप में देखा जा सकता है।[3]यह विधि एक दूसरे से दूर तत्वों के जोड़े को क्रमबद्ध करने से प्रारंभ होती है, फिर तुलना किए जाने वाले तत्वों के बीच के अंतर को धीरे-धीरे कम करती है। दूर-दूर के तत्वों से प्रारंभ करके, यह एक साधारण निकटतम समीप एक्सचेंज की तुलना में कुछ बाहर के तत्वों को तेजी से स्थिति में ले जा सकता है। डोनाल्ड शैल ने इस प्रकार का पहला संस्करण 1959 में प्रकाशित किया था।[4][5] शेलसॉर्ट का चलने का समय उसके द्वारा उपयोग किए जाने वाले अंतराल अनुक्रम पर बहुत अधिक निर्भर है। कई व्यावहारिक वेरिएंट के लिए, उनकी समय जटिलता का निर्धारण एक खुली समस्या बनी हुई है।
विवरण
शेलसॉर्ट सम्मिलन सॉर्ट का एक अनुकूलन है जो दूर-दूर स्थित वस्तुओं के आदान-प्रदान की अनुमति देता है। विचार यह है कि तत्वों की सूची को व्यवस्थित किया जाए जिससे, कहीं से भी प्रारंभ करके, प्रत्येक hवें तत्व को लेने से एक क्रमबद्ध सूची तैयार हो सकता है। ऐसी सूची को h-सॉर्टेड कहा जाता है। इसे इंटरलीव्ड सूचियों के रूप में भी सोचा जा सकता है, प्रत्येक को व्यक्तिगत रूप से क्रमबद्ध किया गया है।[6] h के बड़े मूल्यों के साथ प्रारंभ करने से तत्वों को मूल सूची में लंबी दूरी तक जाने की अनुमति मिलती है, जिससे बड़ी मात्रा में अव्यवस्था कम हो जाती है, और छोटे h-सॉर्ट चरणों के लिए कम काम करना पड़ता है।[7] यदि सूची को किसी छोटे पूर्णांक k के लिए k-क्रमबद्ध किया जाता है, तो सूची h-क्रमबद्ध ही रहती है। 1 पर समाप्त होने वाले h मानों के घटते क्रम के लिए इस विचार का पालन करने से अंत में एक क्रमबद्ध सूची निकलने की आश्वासन है।[6]
सरल शब्दों में, इसका अर्थ है कि यदि हमारे पास 1024 संख्याओं की एक सरणी है, तो हमारा पहला अंतर (h) 512 हो सकता है। फिर हम पहले भाग में प्रत्येक तत्व की तुलना दूसरे भाग में तत्व से करते हुए सूची में चलते हैं। हमारा दूसरा गैप (k) 256 है, जो सरणी को चार खंडों में तोड़ता है (0, 256, 512, 768 से प्रारंभ ), और हम यह सुनिश्चित करते हैं कि प्रत्येक खंड में पहले आइटम एक दूसरे के सापेक्ष क्रमबद्ध हों, फिर दूसरा आइटम प्रत्येक अनुभाग, इत्यादि। व्यवहार में गैप अनुक्रम कुछ भी हो सकता है, किंतु सॉर्ट को समाप्त करने के लिए अंतिम गैप सदैव 1 होता है (प्रभावी रूप से सामान्य सम्मिलन सॉर्ट के साथ समाप्त होता है)।
अंतराल 5, 3 और 1 के साथ शेलसॉर्ट का एक उदाहरण नीचे दिखाया गया है।
a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | a11 | a12 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
इनपुट डेटा | 62 | 83 | 18 | 53 | 07 | 17 | 95 | 86 | 47 | 69 | 25 | 28 |
5-सॉर्टिंग के बाद | 17 | 28 | 18 | 47 | 07 | 25 | 83 | 86 | 53 | 69 | 62 | 95 |
3-सॉर्टिंग के बाद | 17 | 07 | 18 | 47 | 28 | 25 | 69 | 62 | 53 | 83 | 86 | 95 |
1-सॉर्टिंग के बाद | 07 | 17 | 18 | 25 | 28 | 47 | 53 | 62 | 69 | 83 | 86 | 95 |
पहला पास, 5-सॉर्टिंग, पांच अलग-अलग उपसरणी (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). पर इंसर्शन सॉर्ट करता है। उदाहरण के लिए, यह उपसरणी (a1, a6, a11) को (62, 17, 25) से (17, 25, 62) में बदल देता है। अगला पास, 3-सॉर्टिंग, तीन उपसरणी (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12). पर इंसर्शन सॉर्ट करता है। अंतिम पास, 1-सॉर्टिंग, संपूर्ण सरणी (a1,..., a12).का एक सामान्य सम्मिलन प्रकार है।
जैसा कि उदाहरण से पता चलता है कि शेलसॉर्ट जिस उपसरणी पर काम करता है वह प्रारंभ में छोटी होती है, बाद में लंबी हो जाती है किंतु लगभग क्रमबद्ध हो जाती है। दोनों ही स्थिति में इंसर्शन सॉर्ट कुशलता से काम करता है।
इंसर्शन सॉर्ट के विपरीत, शेलसॉर्ट एक सॉर्टिंग एल्गोरिदम या स्थिरता नहीं है क्योंकि गैप्ड इंसर्शन समान तत्वों को एक दूसरे से आगे ले जाते हैं और इस प्रकार अपना मूल क्रम खो देते हैं। यह एक अनुकूली सॉर्ट है जिसमें इनपुट आंशिक रूप से सॉर्ट होने पर यह तेजी से निष्पादित होता है।
स्यूडोकोड
आंतरिक सम्मिलन प्रकार के साथ, मार्सिन सिउरा के अंतराल अनुक्रम का उपयोग करना है ।
# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1] # Ciura gap sequence
# Start with the largest gap and work down to a gap of 1
# similar to insertion sort but instead of 1, gap is being used in each step
foreach (gap in gaps)
{
# Do a gapped insertion sort for every elements in gaps
# Each loop leaves a[0..gap-1] in gapped order
for (i = gap; i < n; i += 1)
{
# save a[i] in temp and make a hole at position i
temp = a[i]
# shift earlier gap-sorted elements up until the correct location for a[i] is found
for (j = i; (j >= gap) && (a[j - gap] > temp); j -= gap)
{
a[j] = a[j - gap]
}
# put temp (the original a[i]) in its correct location
a[j] = temp
}
}
गैप अनुक्रम
यह तय करने का प्रश्न कठिन है कि किस अंतराल अनुक्रम का उपयोग किया जाए। प्रत्येक गैप अनुक्रम जिसमें 1 होता है, एक सही सॉर्ट उत्पन्न करता है (क्योंकि यह अंतिम पास को एक सामान्य प्रविष्टि सॉर्ट बनाता है); चूँकि, शेलसॉर्ट के इस प्रकार प्राप्त संस्करणों के गुण बहुत भिन्न हो सकते हैं। बहुत कम अंतराल पास को धीमा कर देता है, और बहुत अधिक अंतराल ओवरहेड उत्पन्न करता है।
नीचे दी गई तालिका अब तक प्रकाशित अधिकांश प्रस्तावित अंतराल अनुक्रमों की तुलना करती है। उनमें से कुछ में घटते तत्व हैं जो क्रमबद्ध सरणी (N ) के आकार पर निर्भर करते हैं। अन्य अनंत अनुक्रम बढ़ा रहे हैं, जिनके N से कम तत्वों का उपयोग विपरीत क्रम में किया जाना चाहिए।
ओईआईएस | सामान्य पद (k ≥ 1) | कंक्रीट गैप्स | Worst-case time complexity |
Author and year of publication |
---|---|---|---|---|
[e.g. when N = 2p] | Shell, 1959[4] | |||
Frank & Lazarus, 1960[8] | ||||
A000225 | Hibbard, 1963[9] | |||
A083318 | ,के साथ उपसर्ग 1 | Papernov & Stasevich, 1965[10] | ||
A003586 | प्रपत्र की क्रमिक संख्याएँ (3-सुचारु संख्याएँ) | Pratt, 1971[1] | ||
A003462 | , से अधिक नहीं | Knuth, 1973,[3] based on Pratt, 1971[1] | ||
A036569 | Incerpi & Sedgewick, 1985,[11] Knuth[3] | |||
A036562 | , के साथ उपसर्ग 1 | Sedgewick, 1982[6] | ||
A033622 | Sedgewick, 1986[12] | |||
Unknown | Gonnet & [[Ricardo Baeza-Yates|Baeza-Yates]], 1991[13] | |||
A108870 | Unknown | Tokuda, 1992[14] | ||
A102549 | अज्ञात (प्रयोगात्मक रूप से व्युत्पन्न) | Unknown | Ciura, 2001[15] | |
Unknown | Lee, 2021[16] |
जब N के द्विआधारी प्रतिनिधित्व में कई निरन्तर शून्य होते हैं, तो शेल के मूल अंतराल अनुक्रम का उपयोग करके शेलसॉर्ट Θ(N2) बनाता है सबसे खराब स्थिति में तुलना करना उदाहरण के लिए, यह स्थिति दो की घात के समान एन के लिए होता है जब माध्यिका से बड़े और छोटे तत्व क्रमशः विषम और सम स्थिति में होते हैं, क्योंकि उनकी तुलना केवल अंतिम पास में की जाती है।
चूँकि इसमें O(N log N) की तुलना में अधिक जटिलता है जो तुलनात्मक प्रकारों के लिए इष्टतम है, प्रैट का संस्करण नेटवर्क को सॉर्ट करने के लिए उपयुक्त है और इसमें बैचर के बिटोनिक सॉर्टर के समान ही एसिम्प्टोटिक गेट जटिलता है।
गोनेट और बेज़ा-येट्स ने देखा कि शेलसॉर्ट औसतन सबसे कम तुलना करता है जब क्रमिक अंतराल का अनुपात लगभग 2.2 के समान होता है।[13] यही कारण है कि अनुपात 2.2 के साथ उनका अनुक्रम और 2.25 अनुपात के साथ टोकुडा का अनुक्रम कुशल सिद्ध होता है। चूँकि ऐसा क्यों है ये पता नहीं चल पाया है. सेडगेविक उन अंतरालों का उपयोग करने की अनुशंसा करता है जिनमें सबसे बड़े सामान्य भाजक कम होते हैं या जोड़ीवार सहअभाज्य होते हैं।[17] विषम संख्या वाले अंतराल व्यवहार में अच्छा काम करते प्रतीत होते हैं: सम-संख्या वाले अंतराल से बचकर 25% की कमी देखी गई है। 3 और 5 के गुणकों से बचने वाले अंतराल <10% के छोटे लाभ उत्पन्न करते प्रतीत होते हैं।
तुलनाओं की औसत संख्या के संबंध में, सिउरा के अनुक्रम [15] का सबसे अच्छा ज्ञात प्रदर्शन है; 701 से अंतराल निर्धारित नहीं किए गए थे किंतु अनुक्रम को पुनरावर्ती सूत्र के अनुसार आगे बढ़ाया जा सकता है।
टोकुडा का अनुक्रम, सरल सूत्र द्वारा परिभाषित , जहाँ , , व्यावहारिक अनुप्रयोगों के लिए अनुशंसित किया जा सकता है।
यदि अधिकतम इनपुट आकार छोटा है, जैसा कि तब हो सकता है जब शेलसॉर्ट का उपयोग किसी अन्य पुनरावर्ती सॉर्टिंग एल्गोरिदम जैसे कि क्विकसॉर्ट या मर्ज़ सॉर्ट द्वारा छोटे उप-सरणी पर किया जाता है, तो प्रत्येक इनपुट आकार के लिए एक इष्टतम अनुक्रम को सारणीबद्ध करना संभव है।[18]
कम्प्यूटेशनल जटिलता
निम्नलिखित संपत्ति रखती है: किसी भी h1-सॉर्ट किए गए सरणी के h2-सॉर्टिंग के बाद, सरणी h1-सॉर्टेड बनी रहती है।[19] प्रत्येक h1-सॉर्टेड और h2-सॉर्टेड सरणी भी (a1h1+a2h2)--सॉर्टेड है, किसी भी गैर-नकारात्मक पूर्णांक a1 और a2 के लिए शेलसॉर्ट की सबसे खराब स्थिति वाली जटिलता फ्रोबेनियस समस्या से जुड़ी है: दिए गए पूर्णांक h1,..., hn के लिए gcd = 1 के साथ, फ्रोबेनियस संख्या g(h1,..., hn) सबसे बड़ा पूर्णांक है जिसे नहीं किया जा सकता है गैरऋणात्मक पूर्णांक a1,..., an. के साथ a1h1+ ... +anhn के रूप में दर्शाया गया है। फ्रोबेनियस संख्याओं के लिए ज्ञात सूत्रों का उपयोग करके, हम अंतराल अनुक्रमों के कई वर्गों के लिए शेलसॉर्ट की सबसे खराब स्थिति की जटिलता निर्धारित कर सकते हैं। सिद्ध परिणाम उपरोक्त तालिका में दिखाए गए हैं।[20]
मार्क एलन वीस ने सिद्ध किया कि शेलसॉर्ट O(N log N) समय में चलता है जब इनपुट सरणी विपरीत क्रम में होती है।[21]
संचालन की औसत संख्या के संबंध में, कोई भी सिद्ध परिणाम व्यावहारिक अंतराल अनुक्रम से संबंधित नहीं है। उन अंतरालों के लिए जो दो की घात हैं, एस्पेलिड ने इस औसत की गणना के रूप में की।[3] नुथ ने दो अंतराल (h, 1) के साथ एन-तत्व सरणी को सॉर्ट करने की औसत जटिलता को निर्धारित किया।[3] यह इस प्रकार है कि h = Θ(N1/3) के साथ दो-पास शेलसॉर्ट औसतन O(N5/3) तुलना/व्युत्क्रम/चलने का समय बनाता है। याओ ने तीन-पास शेलसॉर्ट की औसत जटिलता पाई।[22] उनके परिणाम को जानसन और नुथ द्वारा परिष्कृत किया गया था:[23] तीन अंतरालों (सीएच, सीजी, 1) के साथ शेलसॉर्ट के दौरान की गई तुलना/व्युत्क्रम/चलने के समय की औसत संख्या, जहां एच और जी सहअभाज्य हैं, {2} है। पहले पास में, दूसरे पास में और तीसरे पास में। अंतिम सूत्र में ψ(h, g) एक जटिल फलन है जो असममित रूप से {5} के बराबर है। विशेष रूप से, जब h = Θ(N7/15) और g = Θ(N1/5),, छँटाई का औसत समय O(N23/15). है।
प्रयोगों के आधार पर, यह अनुमान लगाया गया है कि हिब्बार्ड के अंतराल अनुक्रम के साथ शेलसॉर्ट O(N5/4) औसत समय में चलता है,[3] और गोनेट और बेज़ा-येट्स के अनुक्रम को औसतन 0.41N ln N (ln ln N + 1/6) की आवश्यकता होती है ) तत्व चलता है।[13] जब क्रमबद्ध सरणियों में लाखों तत्व होते हैं तो अन्य अनुक्रमों के लिए पूर्व में रखे गए संचालन की औसत संख्या का अनुमान विफल हो जाता है।
नीचे दिया गया ग्राफ़ शेलसॉर्ट के विभिन्न वेरिएंट में तत्व तुलनाओं की औसत संख्या को सैद्धांतिक निचली सीमा, अथार्त log2N! से विभाजित करके दिखाता है! जहां क्रम 1, 4, 10, 23, 57, 132, 301, 701 को सूत्र के अनुसार बढ़ाया गया है।
कोलमोगोरोव जटिलता के सिद्धांत को लागू करते हुए, जियांग, ली और विटानी [24] ने पी-पास शेलसॉर्ट में संचालन/चलने के समय की औसत संख्या के क्रम के लिए निम्नलिखित निचली सीमा साबित की:Ω(pN1+1/p) जब p ≤ log2N और Ω(pN) जब p > log2N. इसलिए, शेलसॉर्ट के पास औसत समय में चलने की संभावनाएं हैं जो केवल अंतराल अनुक्रमों का उपयोग करते समय एन लॉगएन की तरह बढ़ती है जिनकी अंतराल की संख्या सरणी आकार के लघुगणक के अनुपात में बढ़ती है। हालाँकि, यह अज्ञात है कि क्या शेलसॉर्ट औसत-केस जटिलता के इस स्पर्शोन्मुख क्रम तक पहुँच सकता है, जो तुलनात्मक प्रकारों के लिए इष्टतम है। से तक की प्रत्येक संख्या के लिए निचली सीमा को विटैनी[25] द्वारा उत्तम बनाया गया था। उदाहरण के लिए, यह परिणाम सभी पी-पास वृद्धि अनुक्रमों के लिए जियांग-ली-विटैनी निचली सीमा को दर्शाता है और विशेष वृद्धि अनुक्रमों के लिए उस निचली सीमा को बेहतर बनाता है। वास्तव में औसत मामले के लिए वर्तमान में ज्ञात सभी सीमाएँ (निचली और ऊपरी) इस निचली सीमा से सटीक रूप से मेल खाती हैं। उदाहरण के लिए, यह नया परिणाम देता है कि जेनसन-नुथ ऊपरी सीमा प्रयुक्त वृद्धि अनुक्रम के लिए परिणामी निचली सीमा से मेल खाती है, यह दर्शाता है कि इस वृद्धि अनुक्रम के लिए तीन पास शेलसॉर्ट तुलना/व्युत्क्रम/चलने के समय का उपयोग करता है। सूत्र हमें वृद्धि अनुक्रमों की खोज करने की अनुमति देता है जो निचली सीमाएं उत्पन्न करते हैं जो अज्ञात हैं; उदाहरण के लिए चार पासों के लिए एक वृद्धि क्रम जिसकी निचली सीमा वृद्धि क्रम के लिए से अधिक है। निचली सीमा हो जाती है
शेलसॉर्ट के किसी भी संस्करण की सबसे खराब स्थिति उच्च क्रम की है: प्लैक्सटन पूनेन और सुएल ने दिखाया कि यह कम से कम जितनी तेजी से बढ़ता है।[26][27] रॉबर्ट साइफर ने एक मजबूत निचली सीमा साबित की: जब सभी के लिए ।[28]
अनुप्रयोग
शेलसॉर्ट अधिक संचालन करता है और इसमें क्विकसॉर्ट की तुलना में अधिक सीपीयू कैश या कैश मिस होता है। चूँकि इसे छोटे कोड का उपयोग करके कार्यान्वित किया जा सकता है और कॉल स्टैक का उपयोग नहीं किया जाता है, अंतः स्थापित प्रणालियाँ पर लक्षित सी मानक लाइब्रेरी में क्यूसॉर्ट फ़ंक्शन के कुछ कार्यान्वयन क्विकॉर्ट के अतिरिक्त इसका उपयोग करते हैं। उदाहरण के लिए, शेलसॉर्ट का उपयोग यूक्लिब लाइब्रेरी में किया जाता है।[29] इसी तरह के कारणों से, अतीत में, शेलसॉर्ट का उपयोग लिनक्स कर्नेल में किया जाता था।[30]
शेलसॉर्ट छोटी उप-सरणी को सॉर्ट करने और जब रिकर्सन गहराई एक निश्चित सीमा से अधिक हो जाती है तो धीरे धीरे को रोकने के लिए, आत्मनिरीक्षण प्रकार के उप-एल्गोरिदम के रूप में भी काम कर सकता है। उदाहरण के लिए, यह सिद्धांत बीज़िप2 कंप्रेसर में नियोजित है।[31]
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 1.2 Pratt, Vaughan Ronald (1979). Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences) (PDF). Garland. ISBN 978-0-8240-4406-0. Archived (PDF) from the original on 7 September 2021.
- ↑ "Shellsort & Comparisons".
- ↑ 3.0 3.1 3.2 3.3 3.4 3.5 Knuth, Donald E. (1997). "Shell's method". The Art of Computer Programming. Volume 3: Sorting and Searching (2nd ed.). Reading, Massachusetts: Addison-Wesley. pp. 83–95. ISBN 978-0-201-89685-5.
- ↑ 4.0 4.1 Shell, D. L. (1959). "A High-Speed Sorting Procedure" (PDF). Communications of the ACM. 2 (7): 30–32. doi:10.1145/368370.368387. S2CID 28572656.
- ↑ Some older textbooks and references call this the "Shell–Metzner" sort after Marlene Metzner Norton, but according to Metzner, "I had nothing to do with the sort, and my name should never have been attached to it." See "Shell sort". National Institute of Standards and Technology. Retrieved 17 July 2007.
- ↑ 6.0 6.1 6.2 Sedgewick, Robert (1998). Algorithms in C. Vol. 1 (3rd ed.). Addison-Wesley. pp. 273–281. ISBN 978-0-201-31452-6.
- ↑ Kernighan, Brian W.; Ritchie, Dennis M. (1996). The C Programming Language (2nd ed.). Prentice Hall. p. 62. ISBN 978-7-302-02412-5.
- ↑ Frank, R. M.; Lazarus, R. B. (1960). "A High-Speed Sorting Procedure". Communications of the ACM. 3 (1): 20–22. doi:10.1145/366947.366957. S2CID 34066017.
- ↑ Hibbard, Thomas N. (1963). "An Empirical Study of Minimal Storage Sorting". Communications of the ACM. 6 (5): 206–213. doi:10.1145/366552.366557. S2CID 12146844.
- ↑ Papernov, A. A.; Stasevich, G. V. (1965). "A Method of Information Sorting in Computer Memories" (PDF). Problems of Information Transmission. 1 (3): 63–75.
- ↑ Incerpi, Janet; Sedgewick, Robert (1985). "Improved Upper Bounds on Shellsort" (PDF). Journal of Computer and System Sciences. 31 (2): 210–224. doi:10.1016/0022-0000(85)90042-x.
- ↑ Sedgewick, Robert (1986). "A New Upper Bound for Shellsort". Journal of Algorithms. 7 (2): 159–173. doi:10.1016/0196-6774(86)90001-5.
- ↑ 13.0 13.1 13.2 Gonnet, Gaston H.; Baeza-Yates, Ricardo (1991). "Shellsort". Handbook of Algorithms and Data Structures: In Pascal and C (2nd ed.). Reading, Massachusetts: Addison-Wesley. pp. 161–163. ISBN 978-0-201-41607-7.
Extensive experiments indicate that the sequence defined by α = 0.45454 < 5/11 performs significantly better than other sequences. The easiest way to compute ⌊0.45454n⌋ is by
(5 * n — 1)/11
using integer arithmetic. - ↑ Tokuda, Naoyuki (1992). "An Improved Shellsort". In van Leeuven, Jan (ed.). Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture. Amsterdam: North-Holland Publishing Co. pp. 449–457. ISBN 978-0-444-89747-3.
- ↑ 15.0 15.1 Ciura, Marcin (2001). "Best Increments for the Average Case of Shellsort" (PDF). In Freiwalds, Rusins (ed.). Proceedings of the 13th International Symposium on Fundamentals of Computation Theory. London: Springer-Verlag. pp. 106–117. ISBN 978-3-540-42487-1. Archived from the original (PDF) on 23 September 2018.
- ↑ Lee, Ying Wai (2021). "Empirically Improved Tokuda Gap Sequence in Shellsort". arXiv:2112.11112 [cs.DS].
- ↑ Sedgewick, Robert (1998). "Shellsort". Algorithms in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching. Reading, Massachusetts: Addison-Wesley. pp. 285–292. ISBN 978-0-201-35088-3.
- ↑ Forshell, Olof (22 May 2018). "How to choose the lengths of my sub sequences for a shell sort?". Stack Overflow. Additional commentary at Fastest gap sequence for shell sort? (23 May 2018).
- ↑ Gale, David; Karp, Richard M. (April 1972). "A Phenomenon in the Theory of Sorting" (PDF). Journal of Computer and System Sciences. 6 (2): 103–115. doi:10.1016/S0022-0000(72)80016-3.
- ↑ Selmer, Ernst S. (March 1989). "On Shellsort and the Frobenius Problem" (PDF). BIT Numerical Mathematics. 29 (1): 37–40. doi:10.1007/BF01932703. hdl:1956/19572. S2CID 32467267.
- ↑ Weiss, Mark Allen (1989). "A good case for Shellsort". Congressus Numerantium. 73: 59–62.
- ↑ Yao, Andrew Chi-Chih (1980). "An Analysis of (h, k, 1)-Shellsort" (PDF). Journal of Algorithms. 1 (1): 14–50. doi:10.1016/0196-6774(80)90003-6. S2CID 3054966. STAN-CS-79-726. Archived from the original (PDF) on 4 March 2019.
- ↑ Janson, Svante; Knuth, Donald E. (1997). "Shellsort with Three Increments" (PDF). Random Structures and Algorithms. 10 (1–2): 125–142. arXiv:cs/9608105. CiteSeerX 10.1.1.54.9911. doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<125::AID-RSA6>3.0.CO;2-X.
- ↑ Jiang, Tao; Li, Ming; Vitányi, Paul (September 2000). "A Lower Bound on the Average-Case Complexity of Shellsort" (PDF). Journal of the ACM. 47 (5): 905–911. arXiv:cs/9906008. CiteSeerX 10.1.1.6.6508. doi:10.1145/355483.355488. S2CID 3265123.
- ↑ Vitányi, Paul (March 2018). "On the average-case complexity of Shellsort" (PDF). Random Structures and Algorithms. 52 (2): 354–363. arXiv:1501.06461. doi:10.1002/rsa.20737. S2CID 6833808.
- ↑ Plaxton, C. Greg; Poonen, Bjorn; Suel, Torsten (24–27 October 1992). "Improved Lower Bounds for Shellsort" (PDF). Annual Symposium on Foundations of Computer Science (FOCS 1992). Pittsburgh, United States. 33: 226–235. CiteSeerX 10.1.1.43.1393. doi:10.1109/SFCS.1992.267769. ISBN 978-0-8186-2900-6.
- ↑ Plaxton, C. Greg; Suel, Torsten (May 1997). "Lower Bounds for Shellsort" (PDF). Journal of Algorithms. 23 (2): 221–240. CiteSeerX 10.1.1.460.2429. doi:10.1006/jagm.1996.0825.
- ↑ Cypher, Robert (1993). "A Lower Bound on the Size of Shellsort Sorting Networks". SIAM Journal on Computing. 22: 62–71. doi:10.1137/0222006.
- ↑ Novoa, Manuel III. "libc/stdlib/stdlib.c". Retrieved 29 October 2014.
- ↑ "kernel/groups.c". GitHub. Retrieved 5 May 2012.
- ↑ Julian Seward. "bzip2/blocksort.c". Retrieved 30 March 2011.
ग्रन्थसूची
- Knuth, Donald E. (1997). "Shell's method". The Art of Computer Programming. Volume 3: Sorting and Searching (2nd ed.). Reading, Massachusetts: Addison-Wesley. pp. 83–95. ISBN 978-0-201-89685-5.
- Analysis of Shellsort and Related Algorithms, Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, September 1996.
बाहरी संबंध
- Animated Sorting Algorithms: Shell Sort at the Wayback Machine (archived 10 March 2015) – graphical demonstration
- Shellsort with gaps 5, 3, 1 as a Hungarian folk dance