Python Data Structures – Merge Sort

تعتبر خوارزمية الدمج السريع (Merge Sort) من أهم الخوارزميات المستخدمة في البرمجة لترتيب البيانات بفعالية عالية. تعتمد هذه الخوارزمية على مبدأ “فرق تسد” (Divide and Conquer)، حيث تقوم بتقسيم المصفوفة إلى نصفين متساويين، ثم تقوم بترتيب كل نصف بشكل مستقل، وأخيرًا تقوم بدمج النصفين في مجموعة مرتبة. يتميز الدمج السريع بكونه مستقرًا وفعالًا، مما يجعله مناسبًا للتعامل مع مجموعات بيانات كبيرة.

كيفية عمل Merge Sort

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

تنفيذ Merge Sort باستخدام Python

فيما يلي مثال يوضح كيفية تنفيذ خوارزمية الدمج السريع باستخدام لغة البرمجة بايثون:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# مثال على الاستخدام
array = [38, 27, 43, 3, 9, 82, 10]
sorted_array = merge_sort(array)
print("المصفوفة المرتبة:", sorted_array)

في هذا المثال، نقوم بتعريف دالة merge_sort التي تقسم المصفوفة إلى نصفين، ثم تقوم بترتيب كل نصف باستخدام نفس الدالة بشكل متكرر. بعد ذلك، يتم دمج النصفين باستخدام دالة merge، التي تقوم بمقارنة العناصر ودمجها في مصفوفة جديدة مرتبة. النتيجة النهائية هي مصفوفة مرتبة بالكامل، كما يظهر في المثال عند ترتيب الأرقام.