حساب العكس في المصفوفة

لدينا مشكلة تتطلب العثور على عدد “العكس” في مصفوفة معينة. العكس هو زوج من العناصر في المصفوفة حيث العنصر الأيسر أكبر من العنصر الأيمن والفهم الأساسي هو العثور على جميع الأزواج التي تحقق هذا الشرط. في هذه الحالة، نريد تنفيذ هذا البحث بتعقيد زمني يبلغ O(nlogn).

للقيام بذلك، يمكننا استخدام فكرة المزج والفرز (Merge Sort) لحساب عدد الأزواج التي تحقق الشرط. نقوم بتطبيق فكرة مشابهة للدمج، لكن مع تغييرات بسيطة لتتناسب مع متطلباتنا.

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

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

فيما يلي الكود بلغة C++:

cppCopy code
#include
using namespace std;

long long merge(int arr[], int temp[], int left, int mid, int right) {
    int i, j, k;
    long long inv_count = 0;

    i = left; // Index for the left subarray
    j = mid; // Index for the right subarray
    k = left; // Index for the merged subarray

    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];
            // Count the inversions
            inv_count += (mid - i);
        }
    }

    // Copy the remaining elements of left subarray (if any)
    while (i <= mid - 1) {
        temp[k++] = arr[i++];
    }

    // Copy the remaining elements of right subarray (if any)
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // Copy back the merged elements to original array
    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }

    return inv_count;
}

long long _mergeSort(int arr[], int temp[], int left, int right) {
    int mid;
    long long inv_count = 0;

    if (right > left) {
        mid = (right + left) / 2;

        // Recursively count inversions in the left subarray
        inv_count += _mergeSort(arr, temp, left, mid);

        // Recursively count inversions in the right subarray
        inv_count += _mergeSort(arr, temp, mid + 1, right);

        // Merge the two sorted halves and count inversions
        inv_count += merge(arr, temp, left, mid + 1, right);
    }

    return inv_count;
}

long long countInversions(int arr[], int n) {
    int* temp = new int[n];
    return _mergeSort(arr, temp, 0, n - 1);
}

int main() {
    int arr[] = {2, 3, 8, 6, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Number of inversions are " << countInversions(arr, n);
    return 0;
}

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

بالطبع، يمكننا استكمال المقال بشرح أعمق للكود ولعملية حساب العكس في المصفوفة، بالإضافة إلى بعض النقاط الإضافية التي قد تكون مفيدة للقراء. لنواصل:

فهم الكود:

1. الدالة merge:

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

2. الدالة _mergeSort:

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

3. الدالة countInversions:

   • تهيئ مصفوفة مؤقتة للاستخدام في الفرز.
   • تستدعي _mergeSort لبدء عملية الفرز وحساب عدد العكس.

مزايا هذا الحل:

• زمن التشغيل الفعال: يعتبر هذا الحل من أسرع الطرق لحساب عدد العكس في مصفوفة بزمن تشغيل يقارب O(nlogn)، مما يجعله مفضلًا للمصفوفات الكبيرة.

• فعالية في استخدام الذاكرة: يستخدم الحل مصفوفة مؤقتة للفرز، ولا يقوم بإنشاء مصفوفات جديدة بشكل متكرر، مما يقلل من استخدام الذاكرة الفعالة.

• سهولة التنفيذ: الكود مبني على أفكار بسيطة وواضحة، مما يجعله سهل الفهم والتنفيذ.

الاعتبارات الإضافية:

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

• يمكن تحسين الأداء من خلال استخدام تقنيات البرمجة المتعددة المواضيع (Multithreading) لتوزيع عملية الفرز على عدة معالجات.

• يجب اختبار الحل جيدًا للتأكد من صحة وأداء الكود مع مصفوفات متنوعة من الحجم.

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