شلسورت

خوارزمية شل للفرز ، والمعروفة أيضًا باسم فرز شل أو طريقة شل ، هي خوارزمية فرز مقارنة في مكانها . يمكن فهمها إما كتعميم للفرز بالتبادل ( فرز الفقاعات ) أو الفرز بالإدراج ( فرز الإدراج ). ^{[ 3 ]} تبدأ هذه الطريقة بفرز أزواج العناصر المتباعدة، ثم تقلل تدريجيًا المسافة بين العناصر المراد مقارنتها. من خلال البدء بالعناصر المتباعدة، يمكنها نقل بعض العناصر غير الموجودة في مكانها الصحيح إلى الموضع المطلوب بشكل أسرع من عملية تبادل الجوار الأقرب البسيطة. يعتمد وقت تشغيل خوارزمية شل للفرز بشكل كبير على تسلسل الفجوات المستخدم. بالنسبة للعديد من المتغيرات العملية، لا يزال تحديد تعقيدها الزمني مشكلة مفتوحة .

نُشرت الخوارزمية لأول مرة بواسطة دونالد شيل عام 1959، ولا علاقة لها بالأصداف. ^{[ 4 ] [ 5 ]}

خوارزمية شيل هي تحسين لخوارزمية فرز الإدراج ، تسمح بتبادل العناصر المتباعدة. تقوم فكرتها على ترتيب قائمة العناصر بحيث ينتج عن أخذ كل عنصر رقم h ، بدءًا من أي مكان، قائمة مرتبة. تُسمى هذه القائمة بقائمة h- مرتبة. ويمكن اعتبارها أيضًا h قوائم متداخلة، كل منها مرتبة على حدة. ^{[ 6 ]} البدء بقيم كبيرة لـ h يسمح للعناصر بالتحرك لمسافات طويلة في القائمة الأصلية، مما يقلل من الفوضى بشكل كبير وسريع، ويقلل من الجهد المطلوب لخطوات فرز h الأصغر. ^{[ 7 ]} إذا تم فرز القائمة k-مرتبة لعدد صحيح أصغر k ، فإنها تظل قائمة h- مرتبة. يضمن الفرز النهائي بقيمة h  =  1 أن تكون القائمة مرتبة بالكامل في النهاية، ^{[ 6 ]} ولكن اختيار تسلسل تنازلي لقيم h بعناية يقلل من الجهد المطلوب لهذه المرحلة الأخيرة.

ببساطة، هذا يعني أنه إذا كان لدينا مصفوفة من 1024 رقمًا، فإن الفجوة الأولى ( h ) قد تكون 512. ثم نمر على المصفوفة ونقارن كل عنصر في النصف الأول بالعنصر المقابل له في النصف الثاني. الفجوة الثانية ( k ) هي 256، مما يقسم المصفوفة إلى أربعة أقسام (بدءًا من 0، 256، 512، 768)، ونتأكد من ترتيب العناصر الأولى في كل قسم بالنسبة لبعضها البعض، ثم العنصر الثاني في كل قسم، وهكذا. عمليًا، يمكن أن يكون تسلسل الفجوات أي شيء، لكن الفجوة الأخيرة دائمًا ما تكون 1 لإنهاء عملية الفرز (أي إنهاء العملية بفرز إدراج عادي).

يظهر أدناه مثال لتشغيل خوارزمية Shellsort مع الفجوات 5 و 3 و 1.

تُجري المرحلة الأولى، وهي الفرز الخماسي، فرز الإدراج على خمس مصفوفات فرعية منفصلة ( a1، a6، a11 )، (a2، a7، a12 ) _، ( _a3 ، a8 ) ، ₍ a4 _، a9 ) ، ( _{a5 ،} a10 ₎ . على سبيل المثال _{، تُغير} هذه المرحلة المصفوفة الفرعية ( a1، a6 _، a11 ) من ( _{62 ، 17} ، _{25 ) إلى (17، 25، 62 ) . أما} المرحلة التالية ، وهي الفرز الثلاثي، فتُجري فرز الإدراج _{على المصفوفات} الفرعية الثلاث ₍ a1 _، a4 _، a7 _، a10 ) ، ( a2 _، a5 ، _a8 ، a11 _{) ،} ( a3 _، a6 ، a9 ، a12 ₎ . المرحلة الأخيرة، الفرز 1، هي فرز إدراج عادي للمصفوفة بأكملها ( a ₁ ، ...، a ₁₂ ).

كما يوضح المثال، فإن المصفوفات الفرعية التي تعمل عليها خوارزمية فرز شيل تكون قصيرة في البداية؛ ثم تصبح أطول لاحقًا ولكنها مرتبة تقريبًا. وفي كلتا الحالتين، تعمل خوارزمية فرز الإدراج بكفاءة.

على عكس فرز الإدراج ، فإن فرز شيل ليس فرزًا مستقرًا، إذ أن عمليات الإدراج المتقطعة تنقل العناصر المتساوية متجاوزةً بعضها البعض، وبالتالي تفقد ترتيبها الأصلي. وهو خوارزمية فرز تكيفية، حيث يتم تنفيذها بشكل أسرع عندما يكون المدخل مُرتبًا جزئيًا.

هذا مثال بلغة C# يستخدم تسلسل الفجوة الخاص بمارسين سيورا، مع فرز الإدراج الداخلي.

باستخدام System.Collections.Generic ؛// فرز مصفوفة a[0...n-1]. List <int> gaps = [ 701 , 301 , 132 , 57 , 23 , 10 , 4 , 1 ] ; // تسلسل الفجوات Ciura// ابدأ بأكبر فجوة وتدرج نزولاً حتى تصل إلى فجوة تساوي 1 // على غرار فرز الإدراج، ولكن بدلاً من 1، يتم استخدام الفجوة في كل خطوة foreach ( int gap in gaps ) { // قم بإجراء فرز إدراج مع فجوات لكل عنصر في gaps // كل حلقة تترك a[0..gap-1] مرتبة مع فجوات for ( int i = gap ; i < n ; ++ i ) { // احفظ a[i] في temp وأنشئ فجوة في الموضع i int temp = a [ i ]; // انقل العناصر التي تم فرزها سابقًا مع الفجوات لأعلى حتى يتم العثور على الموقع الصحيح لـ a[i] for ( int j = i ; ( j >= gap ) && ( a [ j - gap ] > temp ); j ​​-= gap ) { a [ j ] = a [ j - gap ]; } // ضع temp (a[i] الأصلي) في موقعه الصحيح a [ j ] = temp ; } }

يُعدّ اختيار تسلسل الفجوات المناسب أمرًا معقدًا. فكل تسلسل فجوات يحتوي على الرقم 1 يُنتج فرزًا صحيحًا (إذ يجعل هذا المرحلة الأخيرة فرز إدراج عاديًا)؛ ومع ذلك، قد تختلف خصائص النسخ الناتجة من خوارزمية Shellsort اختلافًا كبيرًا. فقلة الفجوات تُبطئ عملية الفرز، وكثرتها تُضيف عبئًا إضافيًا.

يقارن الجدول أدناه معظم متواليات الفجوات المقترحة والمنشورة حتى الآن. بعضها يحتوي على عناصر متناقصة تعتمد على حجم المصفوفة المرتبة ( N ). بينما البعض الآخر عبارة عن متواليات لانهائية متزايدة، حيث يجب استخدام العناصر الأقل من N بترتيب عكسي.

OEIS	المصطلح العام ( k ≥ 1)	فجوات خرسانية	تعقيد الوقت في أسوأ الحالات	المؤلف وسنة النشر
	${\displaystyle \left\lfloor {\frac {N}{2^{k}}}\right\rfloor }$	${\displaystyle 1,2,\ldots ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\left\lfloor {\frac {N}{2}}\right\rfloor }$	${\displaystyle \Theta \left(N^{2}\right)}$[مثال: عندما N = 2p ]	شل ، 1959 [ 4 ]
	${\displaystyle 2\left\lfloor {\frac {N}{2^{k+1}}}\right\rfloor +1}$	${\displaystyle 1,3,\ldots ,\;2\left\lfloor {\frac {N}{8}}\right\rfloor +1,\;\;2\left\lfloor {\frac {N}{4}}\right\rfloor +1}$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	فرانك ولازاروس، 1960 [ 8 ]
A000225	${\displaystyle 2^{k}-1}$	${\displaystyle 1,3,7,15,31,63,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	هيبارد ، 1963 [ 9 ]
A083318	${\displaystyle 2^{k}+1}$، مسبوقة بـ 1	${\displaystyle 1,3,5,9,17,33,65,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	بابيرنوف وستاسيفيتش، 1965 [ 10 ]
A003586	الأعداد المتتالية من الشكل${\displaystyle 2^{p}3^{q}}$( 3- أعداد سلسة)	${\displaystyle 1,2,3,4,6,8,9,12,\ldots }$	${\displaystyle \Theta \left(N\log ^{2}N\right)}$	برات ، 1971 [ 1 ]
A003462	${\displaystyle {\frac {3^{k}-1}{2}}}$، لا يزيد عن${\displaystyle \left\lceil {\frac {N}{3}}\right\rceil }$	${\displaystyle 1,4,13,40,121,\ldots }$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	كنوت ، 1973، [ 3 ] استنادًا إلى برات ، 1971 [ 1 ]
A036569	${\displaystyle {\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}}}$	${\displaystyle 1,3,7,21,48,112,\ldots }$	${\displaystyle O\left(N^{1+{\sqrt {\frac {8\ln \left(5/2\right)}{\ln(N)}}}}\right)}$	إنسيربي وسيدجويك ، 1985، [ 11 ] كنوت [ 3 ]
A036562	${\displaystyle 4^{k}+3\cdot 2^{k-1}+1}$، مسبوقة بـ 1	${\displaystyle 1,8,23,77,281,\ldots }$	${\displaystyle O\left(N^{\frac {4}{3}}\right)}$	سيدجويك، 1982 [ 6 ]
A033622	${\displaystyle {\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}}}$	${\displaystyle 1,5,19,41,109,\ldots }$	${\displaystyle O\left(N^{\frac {4}{3}}\right)}$	سيدجويك، 1986 [ 12 ]
	${\displaystyle h_{k}=\max \left\{\left\lfloor {\frac {5h_{k-1}-1}{11}}\right\rfloor ,1\right\},h_{0}=N}$	${\displaystyle 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 }$	${\displaystyle \Theta \left(N^{2}\right)}$[لقيم معينة من N ]	جونيت وبايزا ييتس , 1991 [ 13 ]
A108870	${\displaystyle \left\lceil {\frac {1}{5}}\left(9\cdot \left({\frac {9}{4}}\right)^{k-1}-4\right)\right\rceil }$(أو ما يعادل ذلك،${\displaystyle \left\lceil {\frac {\left(9/4\right)^{k}-1}{\left(9/4\right)-1}}\right\rceil }$)	${\displaystyle 1,4,9,20,46,103,\ldots }$	${\displaystyle O\left(N^{\frac {4}{3}}\right)}$	توكودا، 1992 [ 14 ] (خطأ في الاقتباس لكل OEIS)
A102549	تقريبًا${\displaystyle 0.839531\cdot 2.31842^{k}}$	${\displaystyle 1,4,10,23,57,132,301,701}$	${\displaystyle O\left(N^{\frac {4}{3}}\right)}$	سيورا، 2001 [ 15 ]
A366726	${\displaystyle \left\lceil {\frac {\gamma ^{k}-1}{\gamma -1}}\right\rceil ,\gamma =2.243609061420001\ldots }$	${\displaystyle 1,4,9,20,45,102,230,516,\ldots }$	${\displaystyle O\left(N^{\frac {3}{2}}\right)}$	لي، 2021 [ 16 ]
	${\displaystyle \left\lfloor 4.0816\cdot 8.5714^{\frac {k}{2.2449}}\right\rfloor }$	${\displaystyle 1,4,10,27,72,187,488,\ldots }$	${\displaystyle O\left(N^{\frac {3}{2}}\right)}$	سكين، إرينبورغ، يارومشيك، 2023 [ 17 ]

عندما يحتوي التمثيل الثنائي للعدد N على العديد من الأصفار المتتالية، فإن خوارزمية Shellsort باستخدام تسلسل الفجوات الأصلي لـ Shell تُجري Θ( N² ) مقارنة في أسوأ الحالات. على سبيل المثال، تحدث هذه الحالة عندما يكون N مساويًا لقوة من قوى العدد اثنين ^، حيث تشغل العناصر الأكبر والأصغر من الوسيط مواقع فردية وزوجية على التوالي، نظرًا لمقارنتها فقط في المرور الأخير.

تستخدم خوارزمية Gonnet وBaeza-Yates لفرز Shell (GBY91) فجوات تبدأ بالعدد N ، وتتفوق في أدائها على العديد من الخوارزميات الأخرى في المتوسط ^{​​[ 13 ]} ، ولكنها أيضًا عرضة لحالة أسوأ من Θ( N² ): لنفترض أن X فجوة في المتتالية. تسمح النسبة المشتركة لفجوات GBY91، وهي 2.2 ^، بأن يكون عددان صحيحان متتاليان Y وY+1 على الأقل مساويين لـ X من خلال القسمة الصحيحة على 2.2. اختر Y أو Y+1، أيهما زوجي، لتكرار العملية، وستحصل بالاستقراء على سلسلة لا نهائية من الفجوات الزوجية الأكبر من X. عند X = 1، يتم توليد عدد لا نهائي من الخيارات لـ N حيث تكون جميع فجوات GBY91 الأكبر من 1 زوجية ^، وبالتالي تكون Θ( N² ) على نفس مدخلات الحالة الأسوأ المذكورة سابقًا لفجوات Shell الأصلية.

على الرغم من أن تعقيدها أعلى من O ( N  log N ) الأمثل لفرز المقارنة، إلا أن نسخة برات تناسب فرز الشبكات ولها نفس تعقيد البوابة التقاربي مثل فرز باتشر الثنائي . 

لاحظ غونيت وبايزا-ياتس أن خوارزمية Shellsort تُجري أقل عدد من المقارنات في المتوسط ​​عندما تكون نسب الفجوات المتتالية مساوية تقريبًا لـ 2.2. ^{[ 13 ]} ولهذا السبب، أثبتت متتاليتهما بنسبة 2.2 ومتتالية توكودا بنسبة 2.25 كفاءتهما. مع ذلك، لا يُعرف سبب ذلك. يوصي سيدجويك باستخدام فجوات ذات قواسم مشتركة كبرى صغيرة أو فجوات أولية فيما بينها . ^{[ 18 ]} يبدو أن استخدام فجوات من الأعداد الفردية يُحسّن الأداء، حيث لوحظت زيادة في السرعة بنسبة 25% تقريبًا مقارنةً بشفرة Shell الأصلية. كما يبدو أن استخدام فجوات ليست من مضاعفات 2 أو 3 أو 5 يُقلل أوقات التشغيل بشكل أكبر، إذ يبدو أن زيادة السرعة بنسبة 35% تقريبًا مقارنةً بشفرة Shell الأصلية ممكنة. أما استخدام فجوات من الأعداد الأولية فقط (التي تنتهي بـ 1)، فيبدو أنه يُحسّن السرعة بنسبة 40% تقريبًا مقارنةً بالشفرة الأصلية.

فيما يتعلق بمتوسط ​​عدد المقارنات، فإن متتالية سيورا ^{[ 15 ]} تتمتع بأفضل أداء معروف؛ لم يتم تحديد الفجوات التي تزيد عن 701، ولكن يمكن توسيع المتتالية بشكل أكبر وفقًا للصيغة التكرارية.${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$.

متتالية توكودا، المحددة بالصيغة البسيطة${\displaystyle h_{k}=\lceil h'_{k}\rceil }$، أين${\displaystyle h'_{k}=2.25h'_{k-1}+1}$،${\displaystyle h'_{1}=1}$يمكن التوصية به للتطبيقات العملية.

إذا كان الحد الأقصى لحجم المدخلات صغيرًا، كما قد يحدث عند استخدام خوارزمية فرز شل على مصفوفات فرعية صغيرة بواسطة خوارزمية فرز تكرارية أخرى مثل الفرز السريع أو فرز الدمج ، فمن الممكن جدولة تسلسل أمثل لكل حجم مدخلات. ^{[ 19 ] [ 20 ]} بالنسبة لـ N = 128 و N = 1000، وجد سيورا تجريبيًا أن التسلسلين (1، 4، 9، 24، 85) و (1، 4، 10، 23، 57، 156، 409، 995) يُجريان أقل عدد من المقارنات في المتوسط ​​على التوالي. ^{[ 15 ]}

تتحقق الخاصية التالية: بعد فرز أي مصفوفة مرتبة _وفقًا لـ h1 _{باستخدام h2} ، تظل المصفوفة مرتبة وفقًا _لـ h1 . ^{[ 21 ]} كل مصفوفة مرتبة وفقًا _لـ h1 و h2 هي أيضًا مرتبة وفقًا لـ ( _a1h1 + a2h2 ) ، لأي عددين صحيحين غير سالبين _{a1 و} a2 . وبالتالي _، يرتبط تعقيد الحالة الأسوأ لخوارزمية Shellsort بمسألة فروبينيوس : بالنسبة للأعداد الصحيحة المعطاة _h1 ، _{... ،} hn التي يكون قاسمها المشترك الأكبر 1، فإن عدد فروبينيوس g ( h1 _، ...، hn ) _هو أكبر عدد صحيح لا يمكن تمثيله على الصورة _a1h1 + ... + anhn حيث _{a1 ،} ...، _{an أعداد} صحيحة غير سالبة . _{باستخدام الصيغ المعروفة لأعداد فروبينيوس، يمكننا تحديد تعقيد الحالة الأسوأ لخوارزمية Shellsort لعدة فئات من} متواليات الفجوات. ^{[ 22 ]} تظهر النتائج المثبتة في الجدول أعلاه.

أثبت مارك ألين وايس أن خوارزمية Shellsort تعمل في زمن O ( N log N ) عندما تكون مصفوفة الإدخال بترتيب عكسي. ^{[ 23 ]}

فيما يتعلق بمتوسط ​​عدد العمليات، لا تتناول أي من النتائج المثبتة تسلسل فجوات عملي. بالنسبة للفجوات التي تمثل قوى العدد اثنين، قام إسبيليد بحساب هذا المتوسط ​​على النحو التالي:${\displaystyle 0.5349N{\sqrt {N}}-0.4387N-0.097{\sqrt {N}}+O(1)}$[ ^{24 ]} حدد كنوت متوسط ​​تعقيد فرز مصفوفة مكونة ^من N عنصرًا مع وجود فجوتين ( h ، 1) على النحو التالي:${\displaystyle {\frac {2N^{2}}{h}}+{\sqrt {\pi N^{3}h}}}$[ ^{3 ]} يترتب على ذلك أن خوارزمية فرز شيل ثنائية المرور مع h = Θ( N ^1/3 ) تتطلب في المتوسط ​​O ( N ^5/3 ) من المقارنات/الانعكاسات/وقت التشغيل. وجد ياو متوسط ​​تعقيد خوارزمية فرز شيل ثلاثية المرور. ^{[ 25 ]} وقد حسّن جانسون وكنوث نتيجته : ^{[ 26 ]} متوسط ​​عدد المقارنات/الانعكاسات/وقت التشغيل الذي يتم إجراؤه أثناء خوارزمية فرز شيل بثلاث فجوات ( ch , cg , 1)، حيث h و ^g عددان أوليان فيما بينهما، هو${\displaystyle {\frac {N^{2}}{4ch}}+O(N)}$في المحاولة الأولى،${\displaystyle {\frac {1}{8g}}{\sqrt {\frac {\pi }{ch}}}(h-1)N^{3/2}+O(hN)}$في المرور الثاني و${\displaystyle \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 ) في الصيغة الأخيرة هي دالة معقدة تساوي تقريبًا${\displaystyle {\sqrt {\frac {\pi h}{128}}}g+O\left(g^{-1/2}h^{1/2}\right)+O\left(gh^{-1/2}\right)}$. على وجه الخصوص، عندما يكون h = Θ( N ^7/15 ) و g = Θ( N ^1/5 )، فإن متوسط ​​وقت الفرز هو O ( N ^23/15 ).

استنادًا إلى التجارب، يُفترض أن خوارزمية Shellsort مع تسلسل فجوات هيبارد تعمل في متوسط ​​زمن قدره O ( N ^{5/4 ) [ 3 ]} ، وأن تسلسل جونيت وبايزا-ياتس يتطلب في المتوسط ​​0.41 N  ln N (ln ln N + 1/6) من عمليات نقل العناصر. ^{[ 13 ]} وتفشل التقريبات لمتوسط ​​عدد العمليات التي طُرحت سابقًا لتسلسلات أخرى عندما تحتوي المصفوفات المُرتبة على ملايين العناصر.      

يُظهر الرسم البياني أدناه متوسط ​​عدد مقارنات العناصر المستخدمة في متواليات الفجوات المختلفة، مقسومًا على الحد الأدنى النظري ، أي log₂N _!. تم توسيع متوالية سيوريا 1، 4، 10، 23، 57، 132، 301، 701 (المُسماة Ci01) وفقًا للصيغة التالية :${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$.

بتطبيق نظرية تعقيد كولموغوروف ، أثبت جيانغ ولي وفيتاني ^{[ 27 ]} الحد الأدنى التالي لرتبة متوسط ​​عدد العمليات/زمن التشغيل في خوارزمية فرز شيل ذات p تمريرة: Ω( pN ^{1+1/ p} ) عندما p ≤ log₂N و Ω( pN ) عندما p > _{log₂N . وبالتالي،} فإن خوارزمية فرز شيل لديها إمكانية التشغيل في متوسط ​​زمن ينمو تقاربياً مثل N log N فقط عند استخدام متواليات فجوات ينمو عدد فجواتها بما يتناسب مع لوغاريتم حجم المصفوفة. ومع ذلك، فإنه _من غير المعروف ما إذا كانت خوارزمية فرز شيل قادرة على الوصول إلى هذه الرتبة التقاربية لتعقيد الحالة المتوسطة، وهي الرتبة المثلى لفرز المقارنة. وقد حسّن فيتاني ^{[ 28 ]} الحد الأدنى لكل عدد من التمريرات    ${\displaystyle p}$ل ${\displaystyle \Omega (N\sum _{k=1}^{p}h_{k-1}/h_{k})}$ أين${\displaystyle h_{0}=N}$تشير هذه النتيجة، على سبيل المثال، إلى الحد الأدنى لجيانغ-لي-فيتاني لجميع${\displaystyle p}$يُحسّن هذا الأسلوب الحد الأدنى لتسلسلات الزيادة المُستخدمة. في الواقع، تتطابق جميع الحدود (الدنيا والعليا) المعروفة حاليًا للحالة المتوسطة بدقة مع هذا الحد الأدنى. على سبيل المثال، يُعطي هذا نتيجة جديدة مفادها أن الحد الأعلى لـ Janson-Knuth يتطابق مع الحد الأدنى الناتج لتسلسل الزيادة المُستخدم، مما يُظهر أن استخدام Shellsort بثلاث تمريرات لهذا التسلسل يُحسّن من دقة النتائج.${\displaystyle \Theta (N^{23/15})}$المقارنات/الانعكاسات/وقت التشغيل. تسمح لنا الصيغة بالبحث عن متواليات الزيادة التي تُعطي حدودًا دنيا غير معروفة؛ على سبيل المثال، متوالية زيادة لأربع دورات لها حد أدنى أكبر من ${\displaystyle \Omega (pn^{1+1/p})=\Omega (n^{5/4})}$بالنسبة لتسلسل الزيادة ${\displaystyle h_{1}=n^{11/16},}$${\displaystyle h_{2}=n^{7/16},}$${\displaystyle h_{3}=n^{3/16},}$${\displaystyle h_{4}=1}$يصبح الحد الأدنى ${\displaystyle 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}).}$

إن تعقيد أسوأ حالة لأي نسخة من خوارزمية Shellsort هو من رتبة أعلى: فقد أظهر بلاكستون وبونين وسويل أنه ينمو على الأقل بنفس سرعة${\displaystyle \Omega \left(N\left({\log N \over \log \log N}\right)^{2}\right)}$[ ^{29 ] [ 30 ]} أثبت روبرت سايفر حدًا أدنى أقوى ^:${\displaystyle \Omega \left(N{{(\log N)^{2}} \over {\log \log N}}\right)}$متى${\displaystyle h_{s+1}>h_{s}}$للجميع${\displaystyle s}$[ ^{31 ]​}

تُجري خوارزمية Shellsort عمليات أكثر، لكن نسبة أخطاء ذاكرة التخزين المؤقت فيها أعلى من خوارزمية quicksort . مع ذلك، ولأنها تُنفَّذ باستخدام كود قليل ولا تعتمد على مكدس الاستدعاءات ، فإن بعض تطبيقات دالة qsort في مكتبة C القياسية، المُخصصة للأنظمة المُدمجة ، تستخدمها بدلاً من quicksort. على سبيل المثال، تُستخدم Shellsort في مكتبة uClibc . ^{[ 32 ]} ولأسباب مماثلة، استُخدمت Shellsort في نواة لينكس سابقًا . ^{[ 33 ]}

يمكن أن تُستخدم خوارزمية Shellsort أيضًا كخوارزمية فرعية لخوارزمية الفرز الاستبطاني ، لفرز المصفوفات الفرعية القصيرة ومنع التباطؤ عندما يتجاوز عمق الاستدعاء حدًا معينًا. يُستخدم هذا المبدأ، على سبيل المثال، في ضاغط bzip2 . ^{[ 34 ]}

• فرز المشط

• كنوت، دونالد إي. (1997). "طريقة شل". فن برمجة الحاسوب. المجلد 3: الفرز والبحث (  الطبعة الثانية). ريدينغ، ماساتشوستس: أديسون-ويسلي. الصفحات 83-95 . ISBN  978-0-201-89685-5.
• تحليل خوارزمية Shellsort والخوارزميات ذات الصلة ، روبرت سيدجويك، الندوة الأوروبية الرابعة حول الخوارزميات، برشلونة، سبتمبر 1996.

• خوارزميات الفرز المتحركة: فرز شل على موقع Wayback Machine (مؤرشف في 10 مارس 2015) - عرض توضيحي رسومي
• رقصة "شلسورت" ذات الفجوات 5، 3، 1 كرقصة شعبية مجرية