البحث والترتيب في المصفوفات Array في جافا

تُعتبر المصفوفات Arrays من أهم الهياكل البيانية الأساسية في لغة البرمجة جافا، وتُستخدم لتخزين مجموعة من القيم من نفس النوع في موقع متجاور من الذاكرة. يُعد التعامل مع المصفوفات عن طريق عمليتي “البحث” (Search) و”الترتيب” (Sort) من العمليات الحيوية التي تُمارس بشكل متكرر في البرمجة، سواء في البرمجيات التعليمية أو الأنظمة الكبيرة أو تطبيقات الذكاء الاصطناعي. ويُشكل فهم هذه العمليات جوهرًا لفهم البرمجة الهيكلية والتحكم في البيانات بشكل فعال.

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

أولاً: تعريف المصفوفات Arrays في جافا

المصفوفة هي مجموعة من العناصر من نفس النوع، يتم تخصيصها بشكل متسلسل في الذاكرة. في جافا، يتم إنشاء المصفوفات باستخدام الكلمة المفتاحية new أو مباشرة عند التعريف. وتُخزن المصفوفات ككائنات (Objects) في جافا، حتى وإن كانت تحتوي على عناصر من أنواع بدائية مثل int أو char.

مثال على إنشاء مصفوفة من الأعداد الصحيحة:

java
CopyEdit
int[] numbers = new int[5]; // مصفوفة من 5 عناصر من النوع int

أو بشكل مختصر:

java
CopyEdit
int[] numbers = {5, 3, 7, 1, 9};

تبدأ فهارس المصفوفات في جافا من 0، أي أن العنصر الأول في المصفوفة يُشار إليه بـ array[0].

ثانياً: البحث في المصفوفات

تُعد عملية البحث من العمليات الأساسية التي تسمح للمبرمج بالعثور على عنصر معين داخل المصفوفة. وهناك نوعان رئيسيان للبحث في المصفوفات: البحث الخطي (Linear Search) والبحث الثنائي (Binary Search).

1. البحث الخطي (Linear Search)

يُستخدم عندما تكون المصفوفة غير مرتبة. يتضمن فحص كل عنصر في المصفوفة حتى يتم العثور على العنصر المطلوب أو نهاية المصفوفة.

كود مثال:

java
CopyEdit
public static int linearSearch(int[] array, int key) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == key) {
            return i;
        }
    }
    return -1; // في حال لم يتم العثور على العنصر
}

مزايا وعيوب البحث الخطي:

2. البحث الثنائي (Binary Search)

يُستخدم فقط مع المصفوفات المرتبة (تصاعديًا أو تنازليًا). يعتمد على تقسيم المصفوفة إلى نصفين في كل خطوة، مما يقلل عدد العمليات المطلوبة.

كود مثال:

java
CopyEdit
public static int binarySearch(int[] array, int key) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (array[mid] == key) {
            return mid;
        } else if (array[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

مزايا وعيوب البحث الثنائي:

ثالثاً: الترتيب في المصفوفات

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

1. خوارزمية الترتيب الفقاعي (Bubble Sort)

تعتمد على مقارنة كل عنصر مع العنصر المجاور له وتبديلهما إذا كانا في غير الترتيب المطلوب.

كود مثال:

java
CopyEdit
public static void bubbleSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

تحليل Bubble Sort:

• التعقيد الزمني: O(n²)

• الاستخدام: مناسب للمصفوفات الصغيرة

2. خوارزمية التحديد (Selection Sort)

تبحث عن العنصر الأصغر في الجزء غير المرتب من المصفوفة وتضعه في مكانه الصحيح.

java
CopyEdit
public static void selectionSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        int temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;
    }
}

• التعقيد الزمني: O(n²)

• أفضلية: عدد التبديلات أقل من Bubble Sort

3. خوارزمية الإدراج (Insertion Sort)

تُدخل العناصر واحدًا تلو الآخر في مكانها الصحيح، كما يتم الترتيب يدويًا في لعبة الورق.

java
CopyEdit
public static void insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

• الأفضل مع المصفوفات الصغيرة أو شبه المرتبة

• تعقيد: O(n²) لكن أفضلية أداء على Bubble Sort

4. خوارزمية الدمج (Merge Sort)

تعتمد على مبدأ “فرق تسد”، أي تقسيم المصفوفة إلى أجزاء أصغر ثم دمجها بشكل مرتب.

java
CopyEdit
public static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid, right);
    }
}

private static void merge(int[] array, 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] = array[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = array[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            array[k++] = L[i++];
        } else {
            array[k++] = R[j++];
        }
    }

    while (i < n1) {
        array[k++] = L[i++];
    }
    while (j < n2) {
        array[k++] = R[j++];
    }
}

• تعقيد زمني: O(n log n)

• استهلاك ذاكرة إضافي مرتفع

5. خوارزمية التقسيم السريع (Quick Sort)

واحدة من أسرع خوارزميات الترتيب المستخدمة. تعتمد على اختيار عنصر محوري (Pivot) وتقسيم العناصر حوله.

• التعقيد في أفضل الحالات: O(n log n)

• التعقيد في أسوأ الحالات: O(n²)

• ميزة: لا تستخدم مساحة إضافية كبيرة

6. استخدام مكتبة Java القياسية للترتيب والبحث

توفر مكتبة Java أدوات جاهزة مثل Arrays.sort() و Arrays.binarySearch() والتي تستند إلى خوارزميات محسنة مثل Dual-Pivot Quick Sort.

مثال:

java
CopyEdit
import java.util.Arrays;

int[] arr = {9, 3, 5, 1, 4};
Arrays.sort(arr); // الترتيب تصاعدياً
int index = Arrays.binarySearch(arr, 3); // البحث عن العنصر 3

مقارنة خوارزميات الترتيب من حيث الكفاءة

أهمية اختيار الخوارزمية المناسبة

تؤثر خوارزمية الترتيب أو البحث المختارة بشكل مباشر على الأداء العام للبرنامج. فإذا كان حجم البيانات صغيرًا نسبيًا، يمكن استخدام الخوارزميات البسيطة. أما في حال وجود بيانات ضخمة، فإن استخدام خوارزميات فعالة مثل Merge Sort أو Quick Sort أو Arrays.sort() يعد خيارًا أفضل. كما يجب الانتباه إلى طبيعة البيانات (مرتبة جزئياً، عشوائية، مكررة) لأنها قد تؤثر على أداء بعض الخوارزميات.

الخلاصة التقنية

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

المراجع:

• Oracle Java Documentation – Arrays

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms. MIT Press.