فرز الأقزام
فرز جنوم (المعروف أيضًا باسم الفرز الغبي ) هو نوع من خوارزمية فرز الإدراج لا يستخدم الحلقات المتداخلة. عُرف فرز جنوم لفترة طويلة واستُخدم دون تسميته صراحةً. [ 1 ] ثم شاع استخدامه بفضل عالم الحاسوب الإيراني حامد سربازي آزاد (أستاذ علوم وهندسة الحاسوب في جامعة شريف للتكنولوجيا ) [ 2 ] في عام 2000. سُمي الفرز في البداية بالفرز الغبي [ 3 ] (لا يُخلط بينه وبين فرز بوغوس )، ثم وصفه لاحقًا ديك غرون وأطلق عليه اسم فرز جنوم . [ 4 ]
تُجري خوارزمية فرز جنوم عددًا من المقارنات لا يقل عن عدد مقارنات فرز الإدراج ، ولها نفس خصائص زمن التشغيل التقاربي . تعمل خوارزمية فرز جنوم عن طريق بناء قائمة مُرتبة عنصرًا تلو الآخر، ونقل كل عنصر إلى مكانه الصحيح عبر سلسلة من عمليات التبديل. يبلغ متوسط زمن التشغيل O ( n² ) ، ولكنه يميل إلى O ( n ) إذا كانت القائمة مُرتبة تقريبًا في البداية. [ 5 ] [ ملاحظة 1 ]
وصف ديك غرون طريقة الفرز بالقصة التالية: [ 4 ]
تعتمد لعبة فرز الأقزام على أسلوب قزم الحديقة الهولندي التقليدي (بالهولندية: tuinkabouter ). إليكم كيف يفرز قزم الحديقة صفًا من أصص الزهور . ببساطة، ينظر إلى أصيص الزهور المجاور له والأصيص السابق؛ إذا كانا بالترتيب الصحيح، يتقدم خطوة واحدة للأمام، وإلا، يبدل بينهما ويتراجع خطوة واحدة للخلف. شروط الحدود: إذا لم يكن هناك أصيص سابق، يتقدم للأمام؛ إذا لم يكن هناك أصيص مجاور له، ينتهي دوره.
— "خوارزمية فرز الأقزام - أبسط خوارزمية فرز". Dickgrune.com
الشفرة الزائفة
إليك الشفرة الزائفة لخوارزمية فرز جنوم باستخدام مصفوفة تبدأ من الصفر :
الإجراء gnomeSort(a[]): pos := 1 بينما pos < طول(a): إذا (pos == 0 أو a[pos] >= a[pos-1]): pos := pos + 1 وإلا : قم بتبديل a[pos] و a[pos-1] pos := pos - 1
مثال
بافتراض وجود مصفوفة غير مرتبة، a = [5, 3, 2, 4]، فإن خوارزمية فرز جنوم تتخذ الخطوات التالية خلال حلقة while. يتم تمييز الموضع الحالي بخط غامق ويُشار إليه كقيمة للمتغير pos.
| المصفوفة الحالية | pos | الشرط ساري المفعول | الإجراء المطلوب اتخاذه |
|---|---|---|---|
| [ 5 , 3, 2, 4] | 0 | pos == 0 | زيادة الموضع |
| [5, 3 , 2, 4] | 1 | a[pos] < a[pos-1] | تبديل، إنقاص الموضع |
| [ 3 , 5, 2, 4] | 0 | pos == 0 | زيادة الموضع |
| [3، 5 ، 2، 4] | 1 | a[pos] ≥ a[pos-1] | زيادة الموضع |
| [3، 5، 2 ، 4] | 2 | a[pos] < a[pos-1] | تبديل، إنقاص الموضع |
| [3، 2 ، 5، 4] | 1 | a[pos] < a[pos-1] | تبديل، إنقاص الموضع |
| [ 2 , 3, 5, 4] | 0 | pos == 0 | زيادة الموضع |
| [2، 3 ، 5، 4] | 1 | a[pos] ≥ a[pos-1] | زيادة الموضع |
| [2، 3، 5 ، 4] | 2 | a[pos] ≥ a[pos-1] | زيادة الموضع: |
| [2، 3، 5، 4 ] | 3 | a[pos] < a[pos-1] | تبديل، إنقاص الموضع |
| [2، 3، 4 ، 5] | 2 | a[pos] ≥ a[pos-1] | زيادة الموضع |
| [2، 3، 4، 5 ] | 3 | a[pos] ≥ a[pos-1] | زيادة الموضع |
| [2، 3، 4، 5] | 4 | pos == length(a) | انتهى |
ملحوظات
- ↑ تعني كلمة "مرتب تقريبًا" أن كل عنصر في القائمة ليس بعيدًا عن موضعه الصحيح (ليس أبعد من مسافة ثابتة صغيرة).
مراجع
- ↑ سينغر، مايكل (1980). "برمجة لغة التجميع PDP-11 وتنظيم الآلة" . نيويورك، الولايات المتحدة الأمريكية: جون وايلي وأولاده . ص 47.
- ↑ حامد سربازي آزاد. "صفحة تعريف حامد سربازي آزاد" . مؤرشفة من الأصل بتاريخ 16 أكتوبر 2018. تم الاطلاع عليها بتاريخ 16 أكتوبر 2018 .
- ↑ سربازي آزاد، حامد (2 أكتوبر 2000). "الفرز الغبي: خوارزمية فرز جديدة" (ملف PDF) . النشرة الإخبارية (599). قسم علوم الحاسوب، جامعة غلاسكو: 4. مؤرشف (ملف PDF) من الأصل في 7 مارس 2012. تم الاطلاع عليه في 25 نوفمبر 2014 .
- ١ ٢ "خوارزمية فرز جنوم - أبسط خوارزمية فرز" . Dickgrune.com . ٢٠٠٠-١٠-٠٢. مؤرشف من الأصل في ٢٠١٧-٠٨-٣١ . تم الاطلاع عليه في ٢٠١٧-٠٧-٢٠ .
- ↑ بول إي. بلاك. "فرز الأقزام" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني الأمريكي للمعايير والتكنولوجيا. مؤرشف من الأصل بتاريخ 11 أغسطس 2011. تم الاطلاع عليه بتاريخ 20 أغسطس 2011 .
روابط خارجية
- أنواع المقارنة
- أنواع مستقرة