خوارزمية الفرز بالدمج (Merge Sort)

إنّ الغاية من خوارزميات الفرز (الترتيب) هي ترتيب أو فهرسة العناصر تصاعديًا أو تنازليًا، يمكن أن تكون هذه العناصر مجموعات من الأعداد، أو المحارف، أو أي بنية تحوي أحد هذه الأنماط. وقد تحدّثنا في مقالات سابقة عن عدّة أنواع لخوارزميات الفرز، الآن سنكمل في سلسلتنا ونبدأ بالحديث عن خوارزمية الفرز بالدمج (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).

مثال برمجي لتوضيح آلية العمل من خلال التابعين التاليين :

درجة تعقيد الخوارزمية (Time Complexity)

تعقيد من رتبة O(N.LogN).

السبب: تقسم قائمة بحجم N  إلى logN جزء، وتستغرق عملية دمج القوائم زمنًا من رتبة O(N). وبالتالي تكون النتيجة من رتبة O(N.LogN).


المصدر

مشروعنا غير ربحي، ومُموّل ذاتيًا، نحن لا نتلقى أي أموال حكومية أو من أي جهة كانت سياسية أو غيرها، كما أنّنا لا نلتمس ذلك. و بالإضافة للتمويل الذاتي، الذي يبلغ حاليا 99٪ من مجمل التمويل، نحن نعتمد على المساهمة الطوعية لمؤسسات خاصة وأفراد مثلك لتطوير المشروع وتحقيق أهدافه.لدعمنا إضغط هنا

  • إعداد: نور عبدو.
تعليقات
Loading...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. AcceptRead More