دليل تعليمي لفرز الدمج بلغة Python

فرز البيانات هو واحد من أكثر العمليات شيوعًا التي يقوم بها الممارسون في مجال البيانات في عملهم اليومي. في كثير من الأحيان نحتاج إلى عرض البيانات بترتيب معين لاستخراج معلومات ذات مغزى. لحسن الحظ، في الوقت الحالي لم نعد مضطرين للقيام بهذه المهمة يدويًا. يمكن للحواسيب أن تقوم بالسحر بدلاً منا بأداء لا يضاهى.

هناك عدة استراتيجيات لفرز البيانات. في هذا البرنامج التعليمي، سنحلل واحدة من أكثر تقنيات الفرز فعالية. يستخدم خوارزمية “مرتبط الفرز” استراتيجية القسمة والفتح لفرز مصفوفة غير مرتبة عن طريق تقسيمها أولاً إلى مصفوفات أصغر، التي يتم دمجها فيما بعد بالترتيب الصحيح.

في الأقسام القادمة، سنناقش جميع تفاصيل خوارزمية مرتبط الفرز، كيف تبدو في لغة البرمجة Python، وبعض النصائح العملية لتنفيذها بسلاسة.

ما هو مرتبط الفرز؟

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

تعتمد الخوارزمية على نمط القسمة والفتح، الذي يمكن تقسيمه إلى ثلاثة أجزاء:

• القسمة: هذه العملية تقسم المشكلة إلى مشاكل فرعية أصغر. 
• الفتح: يتم حل المشاكل الفرعية بشكل تكراري. 
• الدمج: يتم دمج حلول المشاكل الفرعية لتحقيق الحل النهائي.

استراتيجية القسمة والفتح

دعونا نرى كيف تعمل خوارزمية الدمج. لنفترض أننا نريد ترتيب الأعداد التالية عن طريق تطبيق خوارزمية الدمج. تقوم الخوارزمية بتقسيم البيانات بشكل متكرر إلى جزئين وتستمر في التقسيم حتى تحتوي كل قائمة على عنصر واحد. ثم نقوم بدمجها عن طريق ترتيبها في قائمة أخرى.

مشكلة خوارزمية الدمج. المصدر: DataCamp

تعقيد الزمن والمساحة لخوارزمية الدمج

من المستحيل معرفة مسبقًا ما هي خوارزمية الفرز التي تعمل بشكل أفضل لمشكلة معينة. يجب أخذ العديد من المتغيرات بعين الاعتبار بخلاف الخوارزمية، بما في ذلك لغة البرمجة المستخدمة لكتابة الشيفرة، والأجهزة التي يتم تنفيذها عليها، وخصوصيات البيانات المراد فرزها.

على الرغم من أنه لا يمكننا التنبؤ بالوقت المحدد لتشغيل خوارزمية الفرز، إلا أنه يمكننا مقارنة أداء خوارزميات الفرز المختلفة عن طريق تحليل تعقيد الزمن والمساحة.

تعقيد الزمن لخوارزمية الدمج

كما أوضحنا في دليل منفصل حول ترميز Big O وتعقيد الوقت، فإن هدف تحليل تعقيد الوقت ليس التنبؤ بالوقت الدقيق لتنفيذ خوارزمية معينة، بل تقييم مدى كفاءة الخوارزمية من خلال تحليل كيفية تغير وقت تنفيذها مع زيادة كمية بيانات الإدخال.

يتم كتابة تحليل تعقيد الوقت باستخدام ترميز Big O، وهو ترميز رياضي يصف معدل نمو أو تراجع دالة معينة. خوارزمية الفرز بالدمج لها تعقيد زمني لوغاريتمي-خطّي، يُشار إليه بـ O(N log(N))، حيث N هو عدد العناصر في القائمة. الحرف ‘O’ يدل على ‘رتبة’ النمو.

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

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

تعقيد المساحة لخوارزمية الفرز بالدمج

أخيرًا، بالإضافة إلى الوقت المطلوب لإنهاء المهمة، يعد تقدير كمية الذاكرة التي ستحتاجها الخوارزمية لإكمال المهمة مع زيادة حجم المشكلة جانبًا مهمًا عند تحليل تعقيد الخوارزمية.

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

يمتلك خوارزم الدمج تعقيد مساحة قدره O(N). وذلك لأنه يستخدم مصفوفة مساعدة بحجم N لدمج النصفين المرتبين من مصفوفة المدخلات. تُستخدم المصفوفة المساعدة لتخزين النتيجة المدمجة، ويتم الكتابة فوق مصفوفة المدخلات بالنتيجة المرتبة.

تنفيذ خوارزم الدمج في بايثون

لنقم بتنفيذ خوارزم الدمج في بايثون. هناك عدة طرق لكتابة الخوارزم؛ ومع ذلك، سنلتزم بتلك القائمة على الاستدعاء الذاتي، والتي يمكن القول إنها الأسهل في الفهم وتتطلب خطوط كود أقل من البدائل الأخرى القائمة على التكرار.

فهم الاستدعاء الذاتي في خوارزم الدمج

إذا كنت جديدًا على الموضوع، فإن الاستدعاء الذاتي يحدث عندما تستدعي الدالة نفسها. يمكنك الاطلاع على دليل فهم الدوال الاستدعائية في بايثون لتتعلم كل شيء عن هذه الدوال القوية.

لتنفيذ فرز الاندماج، نعرف أولا حالة القاعدة: إذا كانت القائمة تحتوي على عنصر واحد فقط، فإنها مرتبة بالفعل، لذا نقوم بالعودة مباشرة. في حالة أخرى، نقوم بتقسيم القائمة إلى نصفين، left_half و right_half، ونستدعي merge_sort() بشكل متكرر على كل منهما. يستمر هذا العملية حتى تحتوي كل قوائم فرعية على عنصر واحد.

عندما نحصل على هذه القوائم الفرعية المرتبة، نبدأ عملية الدمج. لفعل ذلك، نقوم بتهيئة ثلاث متغيرات فهرسية: i لتتبع الموضع في left_half، j لـ right_half، و k للقائمة المدمجة النهائية. ثم نقارن العناصر من النصفين. إذا كان العنصر الحالي في left_half أصغر، نضعه في my_list[k] ونزيد قيمة i. في حالة أخرى، نأخذ العنصر من right_half، نضعه في my_list[k]، ونزيد قيمة j. بعد كل مقارنة، نزيد قيمة k للانتقال إلى الموضع التالي في القائمة النهائية.

تستمر هذه العملية حتى نقوم بمقارنة جميع العناصر في أحد النصفين. إذا ظلت أي عناصر في left_half أو right_half، فإننا نضيفها مباشرة إلى القائمة النهائية، مضمنين عدم ترك أي بيانات خلف. بسبب طبيعة فرز الاندماج العاملة بشكل متكرر، يتم تنفيذ عملية الدمج هذه على كل مستوى من المراحل التكرارية حتى تتم مرتبة القائمة بأكملها.

تنفيذ بلغة Python

أدناه، يمكنك العثور على الشيفرة باستخدام القائمة غير المرتبة من المخطط السابق كمثال:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]

مقارنة بين فرز المزج وخوارزميات الفرز الأخرى

يعتبر فرز المزج خوارزمية فرز سريعة إلى حد ما، خاصة ملائمة لقواعد بيانات كبيرة، وغالبًا ما تُستخدم كقياس مقايس للخوارزميات الأخرى. ومع ذلك، عندما يتعلق الأمر بالقوائم القصيرة، يميل أداؤها إلى أن يكون أقل من غيرها من خوارزميات الفرز.

في الجدول التالي، يمكنك العثور على مقارنة بين فرز المزج وغيرها من الخوارزميات الشهيرة.

التطبيقات العملية لفرز الدمج

تتميز خوارزمية الفرز بالدمج بأداء عالٍ عند فرز القوائم الكبيرة، ولكن كفاءتها تنخفض عند العمل مع القوائم الصغيرة. بنفس القدر، تميل إلى أن تكون أقل كفاءة في السيناريوهات التي يكون فيها بالفعل بعض درجات الترتيب في قوائم الإدخال، حيث ستقوم خوارزمية الفرز بالدمج بنفس الخطوات بغض النظر عن ترتيب القائمة.

حالة استخدام رائعة حيث تكون خوارزمية الفرز بالدمج مفيدة بشكل خاص هي القوائم المرتبطة. القائمة المرتبطة هي هيكل بيانات يتكون من اتصال من العقد مرتبطة بشكل خطي ببعضها البعض. تحتوي كل عقدة على البيانات والرابط لربطها بالعقدة التالية.

يفضل استخدام خوارزمية الفرز بالدمج للقوائم المرتبطة لأنها تتطلب فقط الوصول التسلسلي إلى البيانات، مما يتوافق بشكل جيد مع طبيعة القوائم المرتبطة. أيضًا، تعتبر خوارزمية الفرز بالدمج خوارزمية فرز مستقرة (أي أنها تحافظ على الترتيب النسبي للعناصر المتساوية في النتيجة المفرزة)، وهو اعتبار مهم جدًا في الحفاظ على ترتيب القوائم المرتبطة.

الأخطاء الشائعة واستكشاف الأخطاء وإصلاحها

تعتبر خوارزمية الفرز بالدمج بسيطة جدًا، وهناك مجال محدود لتحسين الكود. ومع ذلك، يمكنك زيادة تعقيد استراتيجية الفرز الخاصة بك من خلال مراعاة حجم بيانات الإدخال.

لقد أشرنا بالفعل إلى أن خوارزمية الفرز بالدمج تعمل بشكل أفضل مع مجموعات البيانات الكبيرة. بالنسبة لمجموعات البيانات الصغيرة، فإن خوارزميات الفرز الأخرى ذات التعقيد الزمني O(N^2)، مثل خوارزمية الفرز بالإدراج، تعمل بشكل أفضل. في هذه الحالة، تحتاج فقط إلى إنشاء عتبة حجم أدنى تختار تحتها استخدام خوارزمية الفرز بالإدراج بدلاً من الفرز بالدمج.

بالإضافة إلى ذلك، فكرة جيدة لاستكشافها هي التوازي. يمكن توازي خطوات فرز الدمج بسهولة باستخدام الطاقة الحاسوبية الصحيحة، مما يقلل من الوقت اللازم للاكتمال. اقرأ دليلنا حول المعالج المركزي مقابل وحدة المعالجة الرسومية لمعرفة المزيد حول الحوسبة الموازية. 

الاستنتاج

يعتبر فرز الدمج أحد أكثر خوارزميات الفرز فعالية وشهرة، ولكن هناك الكثير لتعلمه في عالم الخوارزميات الرائع والمتنامي باستمرار. إذا كنت مهتمًا بجوانب تقنية الخوارزميات، كيفية عملها، وتعقيدها، فضائلها، وعيوبها، فيمكن لهذه الموارد من DataCamp مساعدتك في مواصلة تعلمك:

• دورة مقدمة في هياكل البيانات والخوارزميات
• مسار مهارات برمجة Python
• مسار أساسيات بيانات Python
• دورة Python متقدمة
• مسار مهنة محلل بيانات بلغة Python
• ملاحظة O الكبيرة وتعقيد الوقت