خوارزمية MergeSort في C وJava

إنفورماتيك ديجيتال » خوارزميات » خوارزمية MergeSort في C وJava

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

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

خوارزمية MergeSort في C وJava

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

تنفيذ MergeSort في لغة C

فيما يلي تنفيذ لخوارزمية MergeSort في C:

#include <stdio.h>

void merge(int arr[], int left[], int right[], int left_size, int right_size) {
    int i = 0, j = 0, k = 0;
    
    while (i < left_size && j < right_size) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    
    while (i < left_size) {
        arr[k] = left[i];
        i++;
        k++;
    }
    
    while (j < right_size) {
        arr[k] = right[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int size) {
    if (size < 2) {
        return;
    }
    
    int mid = size / 2;
    int left[mid];
    int right[size - mid];
    
    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }
    
    for (int i = mid; i < size; i++) {
        right[i - mid] = arr[i];
    }
    
    mergeSort(left, mid);
    mergeSort(right, size - mid);
    merge(arr, left, right, mid, size - mid);
}

int main() {
    int arr[] = {9, 5, 2, 7, 1, 8, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    mergeSort(arr, size);
    
    printf("Sorted array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

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

تنفيذ MergeSort في Java

الآن، دعونا نرى كيفية تنفيذ خوارزمية MergeSort في Java:

public class MergeSort {
    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < left.length) {
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < right.length) {
            arr[k] = right[j];
            j++;
            k++;
        }
    }

    public static void mergeSort(int[] arr) {
        if (arr.length < 2) {
            return;
        }

        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];

        System.arraycopy(arr, 0, left, 0, mid);
        System.arraycopy(arr, mid, right, 0, arr.length - mid);

        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 1, 8, 3};

        mergeSort(arr);

        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

في هذا التنفيذ لـ MergeSort في Java، نستخدم طرقًا ثابتة للوظيفة merge y mergeSort. الوظيفة merge يؤدي نفس المهمة كما هو الحال في تنفيذ C، والوظيفة mergeSort يتبع نفس منطق تقسيم ودمج المصفوفات الفرعية. في الحفلة main، نقوم بإنشاء مجموعة اختبار، ونستدعي mergeSort ونعرض المصفوفة المفروزة في وحدة التحكم.

ما هي التعقيد الزمني لخوارزمية MergeSort؟

تبلغ التعقيد الزمني لخوارزمية MergeSort O(n log n)، حيث يمثل "n" عدد العناصر في المصفوفة التي يجب فرزها. وهذا يعني أن وقت تشغيل الخوارزمية يزداد بشكل متناسب مع حاصل ضرب "n" واللوغاريتم الأساسي 2 لـ "n". يجعل هذا التعقيد MergeSort أحد أكثر خوارزميات الفرز المتاحة كفاءة.

مقارنة MergeSort مع خوارزميات الفرز الأخرى

تتميز MergeSort بكفاءتها في فرز البيانات. بالمقارنة مع الخوارزميات الشائعة الأخرى مثل Bubble Sort أو Selection Sort، فإن MergeSort يتمتع بتعقيد زمني أفضل بكثير. في حين أن فرز الفقاعات وفرز التحديد لهما تعقيد زمني يبلغ O(n^2)، فإن فرز الدمج لديه تعقيد زمني يبلغ O(n log n). وهذا يعني أن MergeSort قادر على التعامل مع كميات كبيرة من البيانات بكفاءة وسرعة أكبر من هذه الخوارزميات الأقل كفاءة.

الأسئلة الشائعة

1: لماذا نستخدم MergeSort بدلاً من خوارزميات الفرز الأخرى؟

يتم تفضيل MergeSort على خوارزميات الفرز الأخرى بسبب كفاءتها وأدائها. بفضل تعقيد زمني يبلغ O(n log n)، تتمكن MergeSort من فرز مجموعات كبيرة من البيانات بشكل أسرع وأكثر كفاءة من الخوارزميات ذات التعقيدات التربيعية، مثل Bubble Sort أو Selection Sort. بالإضافة إلى ذلك، تعد MergeSort خوارزمية مستقرة، مما يعني أنها تحافظ على الترتيب النسبي للعناصر ذات القيم المتساوية، وهو أمر قد يكون مهمًا في سياقات معينة.

2: متى يجب عليّ استخدام MergeSort في مشاريعي؟

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

3: هل هناك أي عيوب لاستخدام MergeSort؟

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

4: هل يمكن لـ MergeSort التعامل مع العناصر المكررة في المصفوفة؟

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

5: هل هناك أي متغيرات أو تحسينات على خوارزمية MergeSort؟

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

6: أين يمكنني معرفة المزيد عن MergeSort وخوارزميات الفرز الأخرى؟

إذا كنت تريد معرفة المزيد حول MergeSort وخوارزميات الفرز الأخرى، فيمكنك مراجعة الموارد التالية:

• ويكيبيديا – دمج الفرز
• GeeksforGeeks – دمج الفرز

اختتام

في هذه المقالة، قمنا باستكشاف خوارزمية MergeSort في لغات البرمجة C وJava. لقد تعلمنا كيفية تنفيذ خوارزمية فرز البيانات الفعالة هذه وناقشنا تعقيدها الزمني. من خلال الأمثلة والشروحات التفصيلية، أصبح لديك الآن فهم قوي لكيفية عمل MergeSort في C وJava، وكيف يمكنك تطبيقه في مشاريعك الخاصة.

MergeSort هي أداة قوية لفرز مجموعات كبيرة من البيانات وتعقيدها الزمني O(n log n) يجعلها خيارًا جذابًا مقارنة بخوارزميات الفرز الأخرى الأقل كفاءة. إذا كنت بحاجة إلى فرز البيانات بكفاءة وسرعة، ففكر في استخدام MergeSort كخوارزمية مفضلة لديك.

استكشف وجرب MergeSort في مشاريعك لجني فوائده والاستمتاع بأداء فرز البيانات الأمثل!