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

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

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





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



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





نظرة فاحصة على 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

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

متعلق ب: مقدمة في خوارزمية فرز الفقاعات

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

لماذا القرص عند 100٪

[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).

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

يشارك يشارك سقسقة بريد الالكتروني مقدمة لخوارزمية دمج الفرز

دراسة هياكل البيانات والخوارزميات؟ تعرف على طريقة جديدة تمامًا لفرز المصفوفة الخاصة بك باستخدام Merge Sort.

اقرأ التالي مواضيع ذات صلة
  • برمجة
  • برمجة
  • بايثون
نبذة عن الكاتب جيروم ديفيدسون(تم نشر 22 مقالة)

جيروم كاتب في MakeUseOf. يغطي مقالات عن البرمجة و Linux. إنه أيضًا متحمس للعملات المشفرة ويحتفظ دائمًا بعلامات تبويب في صناعة التشفير.

المزيد من Jerome Davidson

اشترك في نشرتنا الإخبارية

انضم إلى النشرة الإخبارية لدينا للحصول على نصائح تقنية ومراجعات وكتب إلكترونية مجانية وصفقات حصرية!

انقر هنا للاشتراك