اقرأ في هذا المقال
- ما هي خوارزمية الترتيب بالدمج Merge Sort؟
- كيف تعمل خوارزمية الترتيب بالدمج؟
- خطوات خوارزمية الترتيب بالدمج
- تعقيد الوقت لخوارزمية الترتيب بالدمج
ما هي خوارزمية الترتيب بالدمج Merge Sort؟
الترتيب بالدمج وهي خوارزمية “فرق تسد” أي (divide-and-conquer)، حيث يتم أولاً تقسيم المشكلة إلى مشكلات فرعية، عندما تكون حلول المشكلات الفرعية جاهزة، نجمعها معًا للحصول على الحل النهائي للمشكلة، هذه إحدى الخوارزميات التي يمكن تنفيذها بسهولة باستخدام تقنية الاستدعاء الذاتي (recursion)؛ لأننا نتعامل مع المشكلات الفرعية بدلاً من المشكلة الرئيسية، ويمكن وصف الخوارزمية بأنها العملية التالية المكونة من خطوتين:
- القسمة (Divide): في هذه الخطوة، يتم تقسيم المصفوفة الأصلية إلى نصفين، المحور هو نقطة المنتصف للمصفوفة، يتم تنفيذ هذه الخطوة بشكل متكرر لجميع المصفوفات النصفية حتى يصبح حجم المصفوفات يساوي (1).
- القهر (Conquer): في هذه الخطوة، بمجرد أن يصبح الحجم المصفوفات يساوي (1)، نقوم بفرز ودمج المصفوفات المقسمة من أسفل إلى أعلى، والحصول على مصفوفة مرتبة.
كيف تعمل خوارزمية الترتيب بالدمج؟
لتتعرف على كيفية عمل هذه الخوارزمية، دعنا نأخذ مصفوفة غير مرتبة، على سبيل المثال:
نعلم أن خوارزمية الترتيب بالدمج تقوم أولاً بتقسيم المصفوفة بأكملها بشكل تكراري إلى نصفين متساويين حتى يصبح حجم المصفوفة يساوي (1)، نرى هنا أن مصفوفة مكونة من (8) عناصر مقسمة إلى مصفوفتين كل واحدة منهم بحجم (4):
هذا لا يغير تسلسل ظهور العناصر في الأصل، الآن نقسم هاتين المصفوفتين إلى نصفين:
نقسم هذه المصفوفات مرة أخرى، أصبح حجم المصفوفة يساوي (1)، ولا يمكن تقسيمها اكثر من ذلك:
الآن، نقوم بدمجها بنفس الطريقة تمامًا كما تم تقسيمها (لاحظ رموز الألوان المعطاة لهذه القوائم)، تقارن الخوارزمية أولاً عنصر كل قائمة ثم تدمجها في قائمة أخرى بطريقة مرتبة، نرى أن (14 و 33) موجودة في موقعها بشكل مرتب، ثم تقوم الخوارزمية بمقارنة بين (27 و 10) في القائمة المستهدفة المكونة من قيمتين، فتضع (10) أولاً، متبوعًا بـ (27)، وتعيد ترتيب (19 و 35)، بينما يتم وضع (42 و 44) بنفس التسلسل:
في التكرار التالي لمرحلة الدمج، نقوم بمقارنة القوائم ذات القيمتين، ودمجها في قائمة واحدة ووضعها كلها في ترتيب تصاعدي:
بعد الدمج النهائي، تبدو القائمة كما يلي:
خطوات خوارزمية الترتيب بالدمج:
الخطوة (1): إذا كان هناك عنصرًا واحدًا فقط في القائمة، فالقائمة قد تم فرزها بالفعل، فارجع (return)، يعني توقف.
الخطوة (2): قسّم القائمة بشكل متكرر إلى نصفين حتى لا يمكن تقسيمها.
الخطوة (3): ادمج القوائم الأصغر في قائمة جديدة بالترتيب التصاعدي.
تعقيد الوقت لخوارزمية الترتيب بالدمج:
مصفوفة حجمها “N”، يتم تقسيمها بوقت يستغرق “O(logN)”، ودمج جميع القوائم الفرعية في قائمة واحدة يستغرق وقت “O(N)”، وهذه الخوارزمية في أسوأ حالة وأفضل حالة والمتوسط تعمل بوقت تشغيل هو O(N * logN).
