نوع Shell هو خوارزمية فرز "سحرية" للغاية. يقال إنه "سحري" لأنه لا يمكن لأحد أن يشرح بوضوح ما يمكن أن يحققه أدائه. فرز التل لأن DL. تم تسمية شل بعد اقتراحها في عام 1959. نظرًا لأن Car Hoare اقترحت فرزًا سريعًا في عام 1962 ، يتم استخدامه بشكل عام في الفرز السريع لأنه أبسط. ومع ذلك ، لا يزال العديد من علماء الرياضيات يبحثون بلا كلل عن أفضل تعقيد لفرز التل. كمبرمجين عاديين ، يمكننا أن نتعلم أفكار هيل.
بالمناسبة ، قبل ظهور فرز التل ، كان هناك وجهة نظر عامة في عالم الكمبيوتر "لا يمكن لفرز الخوارزميات اختراق O (N2)". كسر ظهور فرز التل هذه اللعنة ، وقريباً ، تم إصدار خوارزميات مثل الفرز السريع واحدًا تلو الآخر. في هذا المعنى ، يقودنا فرز التل إلى حقبة جديدة.
نظرة عامة على الخوارزمية
يعتمد اقتراح فرز التل بشكل أساسي على النقطتين التاليتين:
1. يمكن أن تحقق خوارزمية فرز الإدراج تقريبًا التعقيد O (n) وفعالة للغاية عندما يتم طلب الصفيف بشكل أساسي.
2. ومع ذلك ، يمكن أن يؤدي فرز الإدراج إلى نقل البيانات بتكلفة واحدة فقط في وقت واحد ، وسوف يتدهور الأداء بسرعة عندما يكون الصفيف كبيرًا ومضطرًا بشكل أساسي.
بناءً على ذلك ، يمكننا استخدام طريقة فرز الإدراج المجمعة ، وهي الطريقة المحددة: (خذ مجموعة من 16 عنصرًا كمثال)
1. حدد دلتا الزيادة ، والتي تزيد عن 1 ، وحدد المسجل الفرعي من الصفيف بواسطة هذه الزيادة لفرز الإدراج المباشر. على سبيل المثال ، إذا تم تحديد الزيادة 5 ، يتم فرز العناصر ذات المشتركين 0 ، 5 ، 10 ، 15.
2. احتفظ بزيادة دلتا وحرك العنصر الأول بدوره للإدراج والفرز حتى يتم الانتهاء من الجولة. على سبيل المثال أعلاه ، يتم فرز المصفوفات [1 ، 6 ، 11] ، [2 ، 7 ، 12] ، [3 ، 8 ، 13] ، [4 ، 9 ، 14] بدورها.
3. قلل الزيادة وكرر العملية أعلاه بشكل مستمر حتى تنخفض الزيادة إلى 1. من الواضح أن آخر مرة تكون فيها الإدراج المباشر.
4. يتم الانتهاء من الفرز.
كما يتضح من ما سبق ، تتناقص الزيادة باستمرار ، لذلك يسمى فرز التل مرة أخرى "فرز الزيادة المنخفض".
تنفيذ الكود
فرز الحزمة الطبقة العامة shellsorttest {public static int count = 0 ؛ Main Static Void Main (String [] args) {int [] data = new int [] {5 ، 3 ، 6 ، 2 ، 1 ، 9 ، 4 ، 8 ، 7} ؛ طباعة (بيانات) ؛ Shellsort (البيانات) ؛ طباعة (بيانات) ؛ } public static void shellsort (int [] data) {// حساب الحد الأقصى لقيمة h int h = 1 ؛ بينما (h <= data.length / 3) {h = h * 3 + 1 ؛ } بينما (h> 0) {for (int i = h ؛ i <data.length ؛ i += h) {if (data [i] <data [i - h]) {int tmp = data [i] ؛ int j = i - h ؛ بينما (j> = 0 && data [j]> tmp) {data [j + h] = data [j] ؛ J -= H ؛ } البيانات [j + h] = tmp ؛ طباعة (بيانات) ؛ }} // حساب القيمة h التالية H = (H - 1) / 3 ؛ }} Public Static void print (int [] data) {for (int i = 0 ؛ i <data.length ؛ i ++) {system.out.print (data [i]+"/t") ؛ } system.out.println () ؛ }} نتائج التشغيل:
5 3 6 2 1 9 4 8 7 1 3 6 2 5 9 4 8 7 1 2 3 6 5 9 4 8 7 1 2 3 5 6 9 4 8 7 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
أداء الخوارزمية/التعقيد
يمكن أن تؤخذ التسلسلات الإضافية التي يتم فرزها بواسطة Hill في أي وقت ، والشرط الوحيد هو أن آخر ما يجب أن يكون 1 (لأنه من الضروري التأكد من طلبه بواسطة 1). ومع ذلك ، سيكون اختيار التسلسل المختلفة تأثير كبير على أداء الخوارزمية. الرمز أعلاه يوضح اثنين من الزيادات.
تذكر: من الأفضل ألا يكون لديك عوامل شائعة بخلاف 1 لكل عنصرين في التسلسل الإضافي! (من الواضح أن الفرز بمقدار 2 في التسلسل ليس ذا معنى كبير).
فيما يلي بعض التسلسلات الإضافية الشائعة.
الزيادة الأولى هي في البداية المقترحة من قبل دونالد شل ، أي أن الطية تقل إلى 1. وفقًا للبحث ، باستخدام زيادات التل ، لا يزال التعقيد الزمني O (N2).
الزيادة الثانية hibbard: {1 ، 3 ، ... ، 2^k-1}. التعقيد الزمني لهذا التسلسل الإضافي هو حوالي o (n^1.5).
الزيادة الثالثة Sedgewick: (1 ، 5 ، 19 ، 41 ، 109 ، ...) ، الذي يولد تسلسل إما 9*4^i - 9*2^i + 1 أو 4^i - 3*2^i + 1.
خوارزمية الاستقرار
نعلم جميعًا أن فرز الإدراج هو خوارزمية مستقرة. ومع ذلك ، فإن فرز shell هو عملية إدراج متعددة. في أحد الإدراج ، يمكننا التأكد من عدم نقل ترتيب العناصر نفسها ، ولكن في إدخالات متعددة ، من الممكن تمامًا أن يتم نقل العناصر نفسها في جولات إدخال مختلفة ، ويتم تدمير الاستقرار أخيرًا. لذلك ، فرز الصدفة ليس خوارزمية مستقرة.
خوارزمية سيناريوهات قابلة للتطبيق
على الرغم من أن فرز الصدفة سريع ، إلا أنه يتم إدخال فرز بعد كل شيء ، وترتيب الحجم ليس جيدًا مثل النجم الصاعد - الفرز السريع O (NN) سريع. فرز Shell ليس خوارزمية جيدة في مواجهة كمية كبيرة من البيانات. ومع ذلك ، من الممكن تمامًا استخدام بيانات صغيرة ومتوسطة الحجم.