مقدمة في خوارزمية فرز شل

Shell Sort هو أسلوب فرز يقسم قائمة معينة إلى قوائم فرعية ثم يفرزها باستخدام فرز الإدراج. تستخدم الخوارزمية فجوة n تختار العناصر التي تفصل بينها فجوة n لتشكيل القوائم الفرعية.

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

يتم استخدام فرز الإدراج مرة أخرى لفرز القائمة أخيرًا.

نظرة فاحصة على Shell Sort

قد لا يكون الوصف أعلاه منطقيًا ، ولكن من المفترض أن يساعد المثال. افترض أن لديك القائمة: [39 ، 6 ، 2 ، 51 ، 30 ، 42 ، 7 ، 4 ، 16] وقيمة فجوة مقدارها ثلاثة.

تحتوي القائمة الفرعية الأولى على العناصر: 39 ، 51 ، 7

القائمة الفرعية الثانية: 6 ، 30 ، 4

القائمة الفرعية الثالثة والأخيرة: 2 ، 42 ، 16

بعد فرز الإدراج ، سيتم ترتيب كل من القوائم الفرعية على النحو التالي:

الأول: 7 ، 39 ، 51

الثاني: 4 ، 6 ، 30

الثالث: 2 ، 16 ، 42

يتم الآن دمج القائمة الفرعية التي تم فرزها بطريقة معينة. يتم وضع كل عنصر قائمة فرعية في الفهرس الذي تم جمع قيمة القائمة الفرعية الأصلية غير المصنفة منه.

ذات صلة: مقدمة إلى خوارزمية فرز الفقاعات

لذلك ستنتهي بالتسلسل أدناه:

[7 ، 4 ، 2 ، 39 ، 6 ، 16 ، 51 ، 30 ، 42]

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

[2 ، 4 ، 6 ، 7 ، 16 ، 30 ، 39 ، 42 ، 51]

تحليل الخوارزمية

درجة تعقيد فرز القشرة بين O (n) و O (n2). حساب هذا الاستنتاج خارج نطاق هذه المقالة.

تنفيذ بايثون:

 def shellSort(my_list):
n = len(my_list)
interval = n // 2 # floor division
while interval > 0:
for val in range(interval, n):
temp = my_list[val]
x = val
while x >= interval and my_list[x - interval] > temp:
my_list[x] = my_list[x - interval]
x = x - interval

my_list[x] = temp
interval = interval // 2

الانتقال إلى دمج الفرز

هناك العديد من خوارزميات الفرز ، ولكل منها عمل فريد. يستخدم فرز الدمج على سبيل المثال استراتيجية فرق تسد وله تعقيد O (nlogn).

نوع الدمج ، في بعض الحالات ، أفضل من نوع الصدف وبالتأكيد يستحق النظر إليه. يجب أن يكون التالي في قائمة قراءة خوارزميات الفرز.