فهم الفرز الدمجي (Merge Sort) مع أمثلة في Python، Java، و C

1. مقدمة عن المشكلة

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

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

المدخلات والمخرجات:

• المدخلات: مصفوفة غير مرتبة من العناصر (مثل الأعداد الصحيحة).
• المخرجات: مصفوفة مرتبة تصاعدياً.

2. شرح تعليمي للحل

مفهوم الفرز الدمجي:

• التقسيم: قم بتقسيم المصفوفة إلى نصفين حتى يحتوي كل نصف على عنصر واحد فقط.
• التغلب: قم بفرز كل نصف بشكل منفصل باستخدام الفرز الدمجي بشكل عودي.
• الدمج: قم بدمج النصفين المرتبين للحصول على مصفوفة مرتبة.

عملية الدمج تتضمن مقارنة العناصر في النصفين وترتيبها في مصفوفة جديدة.

تعقيد الوقت:

• أفضل، متوسط، وأسوأ حالة: O(n log n)، حيث n هو عدد العناصر في المصفوفة.

تعقيد المساحة:

• O(n) بسبب المصفوفة المؤقتة المستخدمة خلال عملية الدمج.

3. الحل في Python

def merge_sort(arr):
    if len(arr) > 1:
        # تقسيم المصفوفة إلى نصفين
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[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]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # إضافة العناصر المتبقية
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# استخدام المثال
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("المصفوفة المرتبة هي:", arr)

4. الحل في Java

public class MergeSort {

    // دمج مصفوفتين فرعيتين
    void merge(int arr[], int left, int mid, int right) {
        // إيجاد حجم المصفوفتين الفرعيتين
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // إنشاء مصفوفتين مؤقتتين
        int L[] = new int[n1];
        int R[] = new int[n2];

        // نسخ البيانات إلى المصفوفات المؤقتة
        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[mid + 1 + j];

        // دمج المصفوفتين المؤقتتين
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // نسخ العناصر المتبقية من L[]
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // نسخ العناصر المتبقية من R[]
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // الفرز الدمجي الرئيسي الذي يستخدم الدمج
    void sort(int arr[], int left, int right) {
        if (left < right) {
            // إيجاد نقطة المنتصف
            int mid = (left + right) / 2;

            // فرز النصفين
            sort(arr, left, mid);
            sort(arr, mid + 1, right);

            // دمج النصفين
            merge(arr, left, mid, right);
        }
    }

    // دالة القيادة لاختبار ما سبق
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};

        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length - 1);

        System.out.println("المصفوفة المرتبة:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

5. الحل في C

#include <stdio.h>

// دمج مصفوفتين فرعيتين
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // إنشاء مصفوفتين مؤقتتين
    int L[n1], R[n2];

    // نسخ البيانات إلى المصفوفتين المؤقتتين
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // دمج المصفوفتين الفرعيتين
    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // نسخ العناصر المتبقية من L[]
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // نسخ العناصر المتبقية من R[]
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// الفرز الدمجي الذي يقوم بفرز arr[l..r]
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // إيجاد نقطة المنتصف
        int mid = left + (right - left) / 2;

        // فرز النصفين
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // دمج النصفين
        merge(arr, left, mid, right);
    }
}

// دالة الطباعة للمصفوفة
void printArray(int A[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}

// دالة القيادة لاختبار ما سبق
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("المصفوفة المعطاة هي:\n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nالمصفوفة المرتبة هي:\n");
    printArray(arr, arr_size);
    return 0;
}