خوارزمية الدمج: تحليل وتصحيح لكود فرز البيانات في C++

عند فحص الشيفرة التي قدمتها للخوارزمية MergeSort في لغة C++، يظهر أن هناك خطأ صغير في دالة الدمج (Merge function). الخطأ يكمن في الفور لوب الأخير حيث يجب أن يكون الشرط فيه يشمل العنصر r، بدلاً من ذلك يجب أن يكون i < = r بدلاً من i < r. هذا يؤدي إلى أن يتم ترك عنصر واحد دون دمج في المصفوفة النهائية. إليك الشيفرة المصححة:

cppCopy code
void Merge(int* A, int p, int q, int r)
{
    int B[100], i = 0, j = 0, k = 0;

    i = p;
    k = p;
    j = q + 1;

    while (i <= q && j <= r)
    {
        if (A[i] <= A[j])
        {
            B[k] = A[i];
            k++;
            i++;
        }

        else
        {
            B[k] = A[j];
            k++;
            j++;
        }
    }

    while (i <= q)
    {
        B[k] = A[i];
        k++;
        i++;
    }

    while (j <= r)
    {
        B[k] = A[j];
        k++;
        j++;
    }

    for (i = p; i <= r; i++) // Fix: Change i
    {
        A[i] = B[i];
    }
}

void MergeSort(int A[], int p, int r)
{
    int q;

    if (p < r)
    {
        q = (p + r) / 2;
        MergeSort(A, p, q);
        MergeSort(A, q + 1, r);
        Merge(A, p, q, r);
    }
}

int main(void)
{
    int N[10];

    N[0] = 4;
    N[1] = 5;
    N[2] = 8;
    N[3] = 12;
    N[4] = 7;
    N[5] = 3;
    N[6] = 23;
    N[7] = 1;
    N[8] = 90;
    N[9] = 26;

    MergeSort(N, 0, 9);

    for (int i = 0; i < 10; i++)
    {
        cout << N[i] << endl;
    }
}

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

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

في مثال الشيفرة الذي قدمته، تقوم دالة MergeSort بتقسيم المصفوفة إلى نصفين واستدعاء نفسها لكل نصف بشكل متكرر حتى تكون النصفين مرتبين. ثم تأتي دالة Merge لدمج هذين النصفين المرتبين إلى مصفوفة مرتبة.

المصفوفة التي استخدمتها في دالة main هي مصفوفة عشوائية من 10 عناصر، وتم طباعة النتائج المرتبة بعد تنفيذ خوارزمية الدمج.

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

هذا التحسين يمكن تحقيقه عبر استخدام الذاكرة الديناميكية (مثل new وdelete في C++) أو باستخدام هيكل بيانات يمكنه التعامل مع مصفوفات ذات حجم متغير.