نور عبدو
إنّ الغاية من خوارزميات الفرز (الترتيب) هي ترتيب أو فهرسة العناصر تصاعديًا أو تنازليًا، يمكن أن تكون هذه العناصر مجموعات من الأعداد، أو المحارف، أو أي بنية تحوي أحد هذه الأنماط. وقد تحدّثنا في مقالات سابقة عن عدّة أنواع لخوارزميات الفرز، الآن سنكمل في سلسلتنا ونبدأ بالحديث عن خوارزمية الفرز بالدمج (Merge Sort).
ماهي خوارزمية الفرز بالدمج؟
هي خوارزمية من نوع فرّق- تَسُد تعتمد على فكرة تقسيم قائمة الدخل إلى قوائم فرعية تحوي كل منها عنصر وحيد ومن ثمّ دمج هذه القوائم الفرعية بطريقة تُنتِج قائمة مرتبّة.
الفكرة الأساسية:
- تقسيم القائمة المُدخلة إلى N قائمة فرعية، تحوي كل منها عنصر وحيد.
- أخذ كل قائمتين متجاورتين ودمجهما إلى قائمة واحدة تحوي عنصرين، وبالتالي تتحول الـ N قائمة فرعية وحيدة العنصر إلى N/2 قائمة تحوي كل منها عنصرين.
- تكرار عملية الدمج هذه حتى نصل إلى قائمة وحيدة عناصرها مرتبة.
عند مقارنة محتوى كل قائمتين فرعيتين لدمجهما، يؤخذ العنصر الأول من كل منهما بعين الاعتبار. في حالة الترتيب التصاعدي للعناصر، يبدأ إدخال العناصر إلى القائمة الناتجة عن الدمج من العنصر الأصغر، وتتكرر العملية حتى تفرغ كل من القائمتين الفرعيتين الصغيرتين.
ماهي آلية عمل الخوارزمية؟
كما تلاحظ من الصورة أدناه، يتم تقسيم قائمة بحجم M إلى قائمتين فرعيتين بحجمM/2 في كل خطوة، وتتكرر العملية حتى يصبح التقسيم غير ممكن. لن تتضّح الفكرة إلّا بمثال؛ فلتكن لدينا المصفوفة {9 , 7 , 8 , 3 , 2 , 1}.
لاحظ المصفوفة الأصغر A ذات الحجم 3، والتي تحوي العناصر (9 , 7 , 8). في الخطوة الأولى، تقسم A إلى قائمتين فرعيتين؛ تحوي الأولى عنصرين (9 , 7) أما الثانية تكون وحيدة العنصر (8). الآن، تقسم القائمة ذات العنصرين إلى قائمتين أيضًا (7) و(9). وطالما أنّه لا يمكن إجراء أي تقسيمات على القوائم الفرعية الحالية؛ نظرًا لكون كل منها وحيدة العنصر، سنبدأ بدمجها.
تُدمج القائمتان الناتجان عن آخر مرحلة بتطبيق الإجراء الآنف الذكر لتنتج القائمة (7 , 9)، ومن ثمّ ندمج الأخيرة مع القائمة الثالثة (8)، لتنتج لدينا القائمة المرتبة (7 , 8 , 9).
مثال برمجي لتوضيح آلية العمل من خلال التابعين التاليين :
https://gist.github.com/NourAbdo/20eb850f6da9e0857b08b962ea9796f4
درجة تعقيد الخوارزمية (Time Complexity)
تعقيد من رتبة O(N.LogN).
السبب: تقسم قائمة بحجم N إلى logN جزء، وتستغرق عملية دمج القوائم زمنًا من رتبة O(N). وبالتالي تكون النتيجة من رتبة O(N.LogN).
- إعداد: نور عبدو..
