शैलसॉर्ट

शैलसॉर्ट

कार्रवाई में अंतराल 23, 10, 4, 1 के साथ शेलसॉर्ट
Class	सॉर्टिंग एल्गोरिदम
Data structure	ऐरे
Worst-case performance	O(n2) (worst known worst case gap sequence) O(n log2n) (best known worst case gap sequence)
Best-case performance	O(n log n) (अधिकांश अंतराल अनुक्रम) O(n log2n) (सबसे प्रसिद्ध सबसे खराब स्थिति वाला गैप अनुक्रम)
Average performance	अंतराल अनुक्रम पर निर्भर करता है
Worst-case space complexity	О(n) कुल, O(1) सहायक

शेलसॉर्ट के क्रमिक चरणों में 5, 3, 1 के अंतराल के साथ वस्तुओं के जोड़े की अदला-बदली

शेलसॉर्ट, जिसे शेल सॉर्ट या शेल विधि के रूप में भी जाना जाता है, एक इन-प्लेस एल्गोरिदम या इन-प्लेस तुलना सॉर्ट है। इसे या तो एक्सचेंज (बबल सॉर्ट ) द्वारा सॉर्टिंग या इंसर्शन (सम्मिलन सॉर्ट ) द्वारा सॉर्टिंग के सामान्यीकरण के रूप में देखा जा सकता है। यह विधि एक दूसरे से दूर तत्वों के जोड़े को क्रमबद्ध करने से प्रारंभ होती है, फिर तुलना किए जाने वाले तत्वों के बीच के अंतर को धीरे-धीरे कम करती है। दूर-दूर के तत्वों से प्रारंभ करके, यह एक साधारण निकटतम समीप एक्सचेंज की तुलना में कुछ बाहर के तत्वों को तेजी से स्थिति में ले जा सकता है। डोनाल्ड शैल ने इस प्रकार का पहला संस्करण 1959 में प्रकाशित किया था। शेलसॉर्ट का चलने का समय उसके द्वारा उपयोग किए जाने वाले अंतराल अनुक्रम पर बहुत अधिक निर्भर है। कई व्यावहारिक वेरिएंट के लिए, उनकी समय जटिलता का निर्धारण एक खुली समस्या बनी हुई है।

विवरण

शेलसॉर्ट सम्मिलन सॉर्ट का एक अनुकूलन है जो दूर-दूर स्थित वस्तुओं के आदान-प्रदान की अनुमति देता है। विचार यह है कि तत्वों की सूची को व्यवस्थित किया जाए जिससे, कहीं से भी प्रारंभ करके, प्रत्येक hवें तत्व को लेने से एक क्रमबद्ध सूची तैयार हो सकता है। ऐसी सूची को h-सॉर्टेड कहा जाता है। इसे इंटरलीव्ड सूचियों के रूप में भी सोचा जा सकता है, प्रत्येक को व्यक्तिगत रूप से क्रमबद्ध किया गया है। h के बड़े मूल्यों के साथ प्रारंभ करने से तत्वों को मूल सूची में लंबी दूरी तक जाने की अनुमति मिलती है, जिससे बड़ी मात्रा में अव्यवस्था कम हो जाती है, और छोटे h-सॉर्ट चरणों के लिए कम काम करना पड़ता है। यदि सूची को किसी छोटे पूर्णांक k के लिए k-क्रमबद्ध किया जाता है, तो सूची h-क्रमबद्ध ही रहती है। 1 पर समाप्त होने वाले h मानों के घटते क्रम के लिए इस विचार का पालन करने से अंत में एक क्रमबद्ध सूची निकलने की आश्वासन है।

सरल शब्दों में, इसका अर्थ है कि यदि हमारे पास 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-सॉर्टिंग, पांच अलग-अलग उपसरणी (a₁, a₆, a₁₁), (a₂, a₇, a₁₂), (a₃, a₈), (a₄, a₉), (a₅, a₁₀). पर इंसर्शन सॉर्ट करता है। उदाहरण के लिए, यह उपसरणी (a₁, a₆, a₁₁) को (62, 17, 25) से (17, 25, 62) में बदल देता है। अगला पास, 3-सॉर्टिंग, तीन उपसरणी (a₁, a₄, a₇, a₁₀), (a₂, a₅, a₈, a₁₁), (a₃, a₆, a₉, a₁₂). पर इंसर्शन सॉर्ट करता है। अंतिम पास, 1-सॉर्टिंग, संपूर्ण सरणी (a₁,..., a₁₂).का एक सामान्य सम्मिलन प्रकार है।

जैसा कि उदाहरण से पता चलता है कि शेलसॉर्ट जिस उपसरणी पर काम करता है वह प्रारंभ में छोटी होती है, बाद में लंबी हो जाती है किंतु लगभग क्रमबद्ध हो जाती है। दोनों ही स्थिति में इंसर्शन सॉर्ट कुशलता से काम करता है।

इंसर्शन सॉर्ट के विपरीत, शेलसॉर्ट एक सॉर्टिंग एल्गोरिदम या स्थिरता नहीं है क्योंकि गैप्ड इंसर्शन समान तत्वों को एक दूसरे से आगे ले जाते हैं और इस प्रकार अपना मूल क्रम खो देते हैं। यह एक अनुकूली सॉर्ट है जिसमें इनपुट आंशिक रूप से सॉर्ट होने पर यह तेजी से निष्पादित होता है।

स्यूडोकोड

आंतरिक सम्मिलन प्रकार के साथ, मार्सिन सिउरा के अंतराल अनुक्रम का उपयोग करना है ।

# 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
	$\left\lfloor {\frac {N}{2^{k}}}\right\rfloor$	$1,2,\ldots ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\left\lfloor {\frac {N}{2}}\right\rfloor$	$\Theta \left(N^{2}\right)$ [e.g. when N = 2p]	Shell, 1959
	$2\left\lfloor {\frac {N}{2^{k+1}}}\right\rfloor +1$	$1,3,\ldots ,\;2\left\lfloor {\frac {N}{8}}\right\rfloor +1,\;\;2\left\lfloor {\frac {N}{4}}\right\rfloor +1$	$\Theta \left(N^{\frac {3}{2}}\right)$	Frank & Lazarus, 1960
A000225	$2^{k}-1$	$1,3,7,15,31,63,\ldots$	$\Theta \left(N^{\frac {3}{2}}\right)$	Hibbard, 1963
A083318	$2^{k}+1$,के साथ उपसर्ग 1	$1,3,5,9,17,33,65,\ldots$	$\Theta \left(N^{\frac {3}{2}}\right)$	Papernov & Stasevich, 1965
A003586	प्रपत्र की क्रमिक संख्याएँ $2^{p}3^{q}$ (3-सुचारु संख्याएँ)	$1,2,3,4,6,8,9,12,\ldots$	$\Theta \left(N\log ^{2}N\right)$	Pratt, 1971
A003462	${\frac {3^{k}-1}{2}}$, से अधिक नहीं $\left\lceil {\frac {N}{3}}\right\rceil$	$1,4,13,40,121,\ldots$	$\Theta \left(N^{\frac {3}{2}}\right)$	Knuth, 1973, based on Pratt, 1971
A036569	${\begin{aligned}&\prod \limits _{I}a_{q},{\hbox{where}}\\a_{0}={}&3\\a_{q}={}&\min \left\{n\in \mathbb {N} \colon n\geq \left({\frac {5}{2}}\right)^{q+1},\forall p\colon 0\leq p<q\Rightarrow \gcd(a_{p},n)=1\right\}\\I={}&\left\{0\leq q<r\mid q\neq {\frac {1}{2}}\left(r^{2}+r\right)-k\right\}\\r={}&\left\lfloor {\sqrt {2k+{\sqrt {2k}}}}\right\rfloor \end{aligned}}$	$1,3,7,21,48,112,\ldots$	$O\left(N^{1+{\sqrt {\frac {8\ln \left(5/2\right)}{\ln(N)}}}}\right)$	Incerpi & Sedgewick, 1985, Knuth
A036562	$4^{k}+3\cdot 2^{k-1}+1$, के साथ उपसर्ग 1	$1,8,23,77,281,\ldots$	$O\left(N^{\frac {4}{3}}\right)$	Sedgewick, 1982
A033622	${\begin{cases}9\left(2^{k}-2^{\frac {k}{2}}\right)+1&k{\text{ even}},\\8\cdot 2^{k}-6\cdot 2^{(k+1)/2}+1&k{\text{ odd}}\end{cases}}$	$1,5,19,41,109,\ldots$	$O\left(N^{\frac {4}{3}}\right)$	Sedgewick, 1986
	$h_{k}=\max \left\{\left\lfloor {\frac {5h_{k-1}-1}{11}}\right\rfloor ,1\right\},h_{0}=N$	$1,\ldots ,\left\lfloor {\frac {5}{11}}\left\lfloor {\frac {5N-1}{11}}\right\rfloor -{\frac {1}{11}}\right\rfloor ,\left\lfloor {\frac {5N-1}{11}}\right\rfloor$	Un­known	Gonnet & [[Ricardo Baeza-Yates|Baeza-Yates]], 1991
A108870	$\left\lceil {\frac {1}{5}}\left(9\cdot \left({\frac {9}{4}}\right)^{k-1}-4\right)\right\rceil$	$1,4,9,20,46,103,\ldots$	Un­known	Tokuda, 1992
A102549	अज्ञात (प्रयोगात्मक रूप से व्युत्पन्न)	$1,4,10,23,57,132,301,701$	Un­known	Ciura, 2001
	$\left\lceil {\frac {\gamma ^{k}-1}{\gamma -1}}\right\rceil ,\gamma =2.243609061420001\ldots$	$1,4,9,20,45,102,\ldots$	Un­known	Lee, 2021

जब N के द्विआधारी प्रतिनिधित्व में कई निरन्तर शून्य होते हैं, तो शेल के मूल अंतराल अनुक्रम का उपयोग करके शेलसॉर्ट Θ(N²) बनाता है सबसे खराब स्थिति में तुलना करना उदाहरण के लिए, यह स्थिति दो की घात के समान एन के लिए होता है जब माध्यिका से बड़े और छोटे तत्व क्रमशः विषम और सम स्थिति में होते हैं, क्योंकि उनकी तुलना केवल अंतिम पास में की जाती है।

चूँकि इसमें O(N log N) की तुलना में अधिक जटिलता है जो तुलनात्मक प्रकारों के लिए इष्टतम है, प्रैट का संस्करण नेटवर्क को सॉर्ट करने के लिए उपयुक्त है और इसमें बैचर के बिटोनिक सॉर्टर के समान ही एसिम्प्टोटिक गेट जटिलता है।

गोनेट और बेज़ा-येट्स ने देखा कि शेलसॉर्ट औसतन सबसे कम तुलना करता है जब क्रमिक अंतराल का अनुपात लगभग 2.2 के समान होता है। यही कारण है कि अनुपात 2.2 के साथ उनका अनुक्रम और 2.25 अनुपात के साथ टोकुडा का अनुक्रम कुशल सिद्ध होता है। चूँकि ऐसा क्यों है ये पता नहीं चल पाया है. सेडगेविक उन अंतरालों का उपयोग करने की अनुशंसा करता है जिनमें सबसे बड़े सामान्य भाजक कम होते हैं या जोड़ीवार सहअभाज्य होते हैं। विषम संख्या वाले अंतराल व्यवहार में अच्छा काम करते प्रतीत होते हैं: सम-संख्या वाले अंतराल से बचकर 25% की कमी देखी गई है। 3 और 5 के गुणकों से बचने वाले अंतराल <10% के छोटे लाभ उत्पन्न करते प्रतीत होते हैं।

तुलनाओं की औसत संख्या के संबंध में, सिउरा के अनुक्रम का सबसे अच्छा ज्ञात प्रदर्शन है; 701 से अंतराल निर्धारित नहीं किए गए थे किंतु अनुक्रम को पुनरावर्ती सूत्र $h_{k}=\lfloor 2.25h_{k-1}\rfloor$ के अनुसार आगे बढ़ाया जा सकता है।

टोकुडा का अनुक्रम, सरल सूत्र द्वारा परिभाषित $h_{k}=\lceil h'_{k}\rceil$, जहाँ $h'_{k}=2.25h'_{k-1}+1$, $h'_{1}=1$, व्यावहारिक अनुप्रयोगों के लिए अनुशंसित किया जा सकता है।

यदि अधिकतम इनपुट आकार छोटा है, जैसा कि तब हो सकता है जब शेलसॉर्ट का उपयोग किसी अन्य पुनरावर्ती सॉर्टिंग एल्गोरिदम जैसे कि क्विकसॉर्ट या मर्ज़ सॉर्ट द्वारा छोटे उप-सरणी पर किया जाता है, तो प्रत्येक इनपुट आकार के लिए एक इष्टतम अनुक्रम को सारणीबद्ध करना संभव है।

कम्प्यूटेशनल जटिलता

निम्नलिखित संपत्ति रखती है: किसी भी h₁-सॉर्ट किए गए सरणी के h₂-सॉर्टिंग के बाद, सरणी h₁-सॉर्टेड बनी रहती है। प्रत्येक h₁-सॉर्टेड और h₂-सॉर्टेड सरणी भी (a₁h₁+a₂h₂)--सॉर्टेड है, किसी भी गैर-नकारात्मक पूर्णांक a₁ और a₂ के लिए शेलसॉर्ट की सबसे खराब स्थिति वाली जटिलता फ्रोबेनियस समस्या से जुड़ी है: दिए गए पूर्णांक h₁,..., h_n के लिए gcd = 1 के साथ, फ्रोबेनियस संख्या g(h₁,..., h_n) सबसे बड़ा पूर्णांक है जिसे नहीं किया जा सकता है गैरऋणात्मक पूर्णांक a₁,..., a_n. के साथ a₁h₁+ ... +a_nh_n के रूप में दर्शाया गया है। फ्रोबेनियस संख्याओं के लिए ज्ञात सूत्रों का उपयोग करके, हम अंतराल अनुक्रमों के कई वर्गों के लिए शेलसॉर्ट की सबसे खराब स्थिति की जटिलता निर्धारित कर सकते हैं। सिद्ध परिणाम उपरोक्त तालिका में दिखाए गए हैं।

मार्क एलन वीस ने सिद्ध किया कि शेलसॉर्ट O(N log N) समय में चलता है जब इनपुट सरणी विपरीत क्रम में होती है।

संचालन की औसत संख्या के संबंध में, कोई भी सिद्ध परिणाम व्यावहारिक अंतराल अनुक्रम से संबंधित नहीं है। उन अंतरालों के लिए जो दो की घात हैं, एस्पेलिड ने इस औसत की गणना $0.5349N{\sqrt {N}}-0.4387N-0.097{\sqrt {N}}+O(1)$ के रूप में की। नुथ ने दो अंतराल (h, 1) के साथ एन-तत्व सरणी को सॉर्ट करने की औसत जटिलता को ${\frac {2N^{2}}{h}}+{\sqrt {\pi N^{3}h}}$ निर्धारित किया। यह इस प्रकार है कि h = Θ(N^1/3) के साथ दो-पास शेलसॉर्ट औसतन O(N^5/3) तुलना/व्युत्क्रम/चलने का समय बनाता है। याओ ने तीन-पास शेलसॉर्ट की औसत जटिलता पाई। उनके परिणाम को जानसन और नुथ द्वारा परिष्कृत किया गया था: तीन अंतरालों (सीएच, सीजी, 1) के साथ शेलसॉर्ट के दौरान की गई तुलना/व्युत्क्रम/चलने के समय की औसत संख्या, जहां एच और जी सहअभाज्य हैं, {2} है। पहले पास में,${\frac {N^{2}}{4ch}}+O(N)$ दूसरे पास में और ${\frac {1}{8g}}{\sqrt {\frac {\pi }{ch}}}(h-1)N^{3/2}+O(hN)$ तीसरे पास में। अंतिम सूत्र में ψ(h, g) एक जटिल फलन है जो असममित रूप से {5} के बराबर है। विशेष रूप से, जब h = Θ(N^{7/15) और g = Θ(N1/5),, छँटाई का औसत समय O(N23/15). है।}

प्रयोगों के आधार पर, यह अनुमान लगाया गया है कि हिब्बार्ड के अंतराल अनुक्रम के साथ शेलसॉर्ट O(N^5/4) औसत समय में चलता है, और गोनेट और बेज़ा-येट्स के अनुक्रम को औसतन 0.41N ln N (ln ln N + 1/6) की आवश्यकता होती है ) तत्व चलता है। जब क्रमबद्ध सरणियों में लाखों तत्व होते हैं तो अन्य अनुक्रमों के लिए पूर्व में रखे गए संचालन की औसत संख्या का अनुमान विफल हो जाता है।

नीचे दिया गया ग्राफ़ शेलसॉर्ट के विभिन्न वेरिएंट में तत्व तुलनाओं की औसत संख्या को सैद्धांतिक निचली सीमा, अथार्त log₂N! से विभाजित करके दिखाता है! जहां क्रम 1, 4, 10, 23, 57, 132, 301, 701 को सूत्र $h_{k}=\lfloor 2.25h_{k-1}\rfloor$ के अनुसार बढ़ाया गया है।

कोलमोगोरोव जटिलता के सिद्धांत को लागू करते हुए, जियांग, ली और विटानी ने पी-पास शेलसॉर्ट में संचालन/चलने के समय की औसत संख्या के क्रम के लिए निम्नलिखित निचली सीमा साबित की:Ω(pN^1+1/p) जब p ≤ log₂N और Ω(pN) जब p > log₂N. इसलिए, शेलसॉर्ट के पास औसत समय में चलने की संभावनाएं हैं जो केवल अंतराल अनुक्रमों का उपयोग करते समय एन लॉगएन की तरह बढ़ती है जिनकी अंतराल की संख्या सरणी आकार के लघुगणक के अनुपात में बढ़ती है। हालाँकि, यह अज्ञात है कि क्या शेलसॉर्ट औसत-केस जटिलता के इस स्पर्शोन्मुख क्रम तक पहुँच सकता है, जो तुलनात्मक प्रकारों के लिए इष्टतम है। $p$ से $\Omega (N\sum _{k=1}^{p}h_{k-1}/h_{k})$तक की प्रत्येक संख्या के लिए निचली सीमा को विटैनी द्वारा उत्तम बनाया गया था। उदाहरण के लिए, यह परिणाम सभी पी-पास वृद्धि अनुक्रमों के लिए जियांग-ली-विटैनी निचली सीमा को दर्शाता है और विशेष वृद्धि अनुक्रमों के लिए उस निचली सीमा को बेहतर बनाता है। वास्तव में औसत मामले के लिए वर्तमान में ज्ञात सभी सीमाएँ (निचली और ऊपरी) इस निचली सीमा से सटीक रूप से मेल खाती हैं। उदाहरण के लिए, यह नया परिणाम देता है कि जेनसन-नुथ ऊपरी सीमा प्रयुक्त वृद्धि अनुक्रम के लिए परिणामी निचली सीमा से मेल खाती है, यह दर्शाता है कि इस वृद्धि अनुक्रम के लिए तीन पास शेलसॉर्ट $\Theta (N^{23/15})$तुलना/व्युत्क्रम/चलने के समय का उपयोग करता है। सूत्र हमें वृद्धि अनुक्रमों की खोज करने की अनुमति देता है जो निचली सीमाएं उत्पन्न करते हैं जो अज्ञात हैं; उदाहरण के लिए चार पासों के लिए एक वृद्धि क्रम जिसकी निचली सीमा वृद्धि क्रम $h_{1}=n^{11/16},$ $h_{2}=n^{7/16},$ $h_{3}=n^{3/16},$ $h_{4}=1$ के लिए $\Omega (pn^{1+1/p})=\Omega (n^{5/4})$ से अधिक है। निचली सीमा $T=\Omega (n\cdot (n^{1-11/16}+n^{11/16-7/16}+n^{7/16-3/16}+n^{3/16})=\Omega (n^{1+5/16})=\Omega (n^{21/16}).$ हो जाती है

शेलसॉर्ट के किसी भी संस्करण की सबसे खराब स्थिति उच्च क्रम की है: प्लैक्सटन पूनेन और सुएल ने दिखाया कि यह कम से कम $\Omega \left(N\left({\log N \over \log \log N}\right)^{2}\right)$जितनी तेजी से बढ़ता है। रॉबर्ट साइफर ने एक मजबूत निचली सीमा साबित की: $\Omega \left(N{{(\log N)^{2}} \over {\log \log N}}\right)$ जब सभी $s$ के लिए $h_{s+1}>h_{s}$।

अनुप्रयोग

शेलसॉर्ट अधिक संचालन करता है और इसमें क्विकसॉर्ट की तुलना में अधिक सीपीयू कैश या कैश मिस होता है। चूँकि इसे छोटे कोड का उपयोग करके कार्यान्वित किया जा सकता है और कॉल स्टैक का उपयोग नहीं किया जाता है, अंतः स्थापित प्रणालियाँ पर लक्षित सी मानक लाइब्रेरी में क्यूसॉर्ट फ़ंक्शन के कुछ कार्यान्वयन क्विकॉर्ट के अतिरिक्त इसका उपयोग करते हैं। उदाहरण के लिए, शेलसॉर्ट का उपयोग यूक्लिब लाइब्रेरी में किया जाता है। इसी तरह के कारणों से, अतीत में, शेलसॉर्ट का उपयोग लिनक्स कर्नेल में किया जाता था।

शेलसॉर्ट छोटी उप-सरणी को सॉर्ट करने और जब रिकर्सन गहराई एक निश्चित सीमा से अधिक हो जाती है तो धीरे धीरे को रोकने के लिए, आत्मनिरीक्षण प्रकार के उप-एल्गोरिदम के रूप में भी काम कर सकता है। उदाहरण के लिए, यह सिद्धांत बीज़िप2 कंप्रेसर में नियोजित है।

यह भी देखें

• कोंब सॉर्ट

ग्रन्थसूची

• 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