शैलसॉर्ट

शैलसॉर्ट

Shellsort with gaps 23, 10, 4, 1 in action
Class	Sorting algorithm
Data structure	Array
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) (most gap sequences) O(n log2n) (best known worst-case gap sequence)
Average performance	depends on gap sequence
Worst-case space complexity	О(n) total, O(1) auxiliary

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

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

विवरण

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

सरल शब्दों में, इसका मतलब है कि यदि हमारे पास 1024 संख्याओं की एक सरणी है, तो हमारा पहला अंतर (एच) 512 हो सकता है। फिर हम पहले भाग में प्रत्येक तत्व की तुलना दूसरे भाग में तत्व से करते हुए सूची में चलते हैं। हमारा दूसरा गैप (k) 256 है, जो सरणी को चार खंडों में तोड़ता है (0, 256, 512, 768 से शुरू), और हम यह सुनिश्चित करते हैं कि प्रत्येक खंड में पहले आइटम एक दूसरे के सापेक्ष क्रमबद्ध हों, फिर दूसरा आइटम प्रत्येक अनुभाग, इत्यादि। व्यवहार में गैप अनुक्रम कुछ भी हो सकता है, लेकिन सॉर्ट को समाप्त करने के लिए अंतिम गैप हमेशा 1 होता है (प्रभावी रूप से सामान्य सम्मिलन सॉर्ट के साथ समाप्त होता है)।

अंतराल 5, 3 और 1 के साथ शेलसॉर्ट का एक उदाहरण नीचे दिखाया गया है।

	a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12
Input data	62	83	18	53	07	17	95	86	47	69	25	28
After 5-sorting	17	28	18	47	07	25	83	86	53	69	62	95
After 3-sorting	17	07	18	47	28	25	69	62	53	83	86	95
After 1-sorting	07	17	18	25	28	47	53	62	69	83	86	95

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

नीचे दी गई तालिका अब तक प्रकाशित अधिकांश प्रस्तावित अंतराल अनुक्रमों की तुलना करती है। उनमें से कुछ में घटते तत्व हैं जो क्रमबद्ध सरणी (एन) के आकार पर निर्भर करते हैं। अन्य अनंत अनुक्रम बढ़ा रहे हैं, जिनके एन से कम तत्वों का उपयोग विपरीत क्रम में किया जाना चाहिए।

OEIS	General term (k ≥ 1)	Concrete gaps	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$, prefixed with 1	$1,3,5,9,17,33,65,\ldots$	$\Theta \left(N^{\frac {3}{2}}\right)$	Papernov & Stasevich, 1965
A003586	Successive numbers of the form $2^{p}3^{q}$ (3-smooth numbers)	$1,2,3,4,6,8,9,12,\ldots$	$\Theta \left(N\log ^{2}N\right)$	Pratt, 1971
A003462	${\frac {3^{k}-1}{2}}$, not greater than $\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$, prefixed with 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	Unknown (experimentally derived)	$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 लॉग 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 बनी हुई है₁-क्रमबद्ध। प्रत्येक एच₁-सॉर्टेड और एच₂-सॉर्टेड सरणी भी है (a₁h₁+ए₂h₂)-किसी भी गैर-नकारात्मक पूर्णांक के लिए क्रमबद्ध₁ और ए₂. शेलसॉर्ट की सबसे खराब स्थिति इसलिए सिक्के की समस्या से जुड़ी है: दिए गए पूर्णांकों के लिए एच₁,..., एच_nजीसीडी = 1 के साथ, फ्रोबेनियस संख्या जी(एच)।₁,..., एच_n) सबसे बड़ा पूर्णांक है जिसे a के रूप में प्रदर्शित नहीं किया जा सकता₁h₁+ ... +ए_nh_nअऋणात्मक पूर्णांक a के साथ₁,..., ए_n. फ्रोबेनियस संख्याओं के लिए ज्ञात सूत्रों का उपयोग करके, हम अंतराल अनुक्रमों के कई वर्गों के लिए शेलसॉर्ट की सबसे खराब स्थिति की जटिलता निर्धारित कर सकते हैं। सिद्ध परिणाम उपरोक्त तालिका में दिखाए गए हैं।

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

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

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

कोलमोगोरोव जटिलता के सिद्धांत को लागू करते हुए, जियांग, मिंग एल आई , और पॉल विटैनी|विटैनी

 पी-पास शेलसॉर्ट में संचालन/चलने के समय की औसत संख्या के क्रम के लिए निम्नलिखित निचली सीमा साबित हुई: Ω(pN1+1/पी) जब पी ≤ लॉग करें2एन और Ω(पीएन) जब पी > लॉग करें2एन।

इसलिए, शेलसॉर्ट के पास औसत समय में चलने की संभावनाएं हैं जो केवल अंतराल अनुक्रमों का उपयोग करते समय एन लॉगएन की तरह बढ़ती है जिनकी अंतराल की संख्या सरणी आकार के लघुगणक के अनुपात में बढ़ती है। हालाँकि, यह अज्ञात है कि क्या शेलसॉर्ट औसत-केस जटिलता के इस स्पर्शोन्मुख क्रम तक पहुँच सकता है, जो तुलनात्मक प्रकारों के लिए इष्टतम है। निचली सीमा में पॉल विटैनी|विटैनी द्वारा सुधार किया गया था प्रत्येक पास की संख्या के लिए $p$ को

 $\Omega (N\sum _{k=1}^{p}h_{k-1}/h_{k})$

कहाँ $h_{0}=N$. उदाहरण के लिए, यह परिणाम सभी के लिए जियांग-ली-विटैनी की निचली सीमा को दर्शाता है $p$-वृद्धि अनुक्रमों को पारित करें और विशेष वृद्धि अनुक्रमों के लिए उस निचली सीमा में सुधार करें। वास्तव में औसत मामले के लिए वर्तमान में ज्ञात सभी सीमाएँ (निचली और ऊपरी) इस निचली सीमा से सटीक रूप से मेल खाती हैं। उदाहरण के लिए, यह नया परिणाम देता है कि जेनसन-नुथ ऊपरी सीमा प्रयुक्त वेतन वृद्धि अनुक्रम के लिए परिणामी निचली सीमा से मेल खाती है, यह दर्शाता है कि इस वृद्धि अनुक्रम के लिए तीन पास शेलसॉर्ट का उपयोग किया जाता है $\Theta (N^{23/15})$ तुलना/विपरीतता/चलने का समय। सूत्र हमें वृद्धि अनुक्रमों की खोज करने की अनुमति देता है जो निचली सीमाएं उत्पन्न करते हैं जो अज्ञात हैं; उदाहरण के लिए चार पासों के लिए एक वृद्धि क्रम जिसकी निचली सीमा इससे अधिक है $\Omega (pn^{1+1/p})=\Omega (n^{5/4})$ वृद्धि क्रम के लिए $h_{1}=n^{11/16},$ $h_{2}=n^{7/16},$ $h_{3}=n^{3/16},$ $h_{4}=1$. निचली सीमा बन जाती है $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)$ कब $h_{s+1}>h_{s}$ सभी के लिए $s$.

अनुप्रयोग

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

यह भी देखें

• कंघी सॉर्ट करें

ग्रन्थसूची

• 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