شرح خوارزمية Selection Sort في Java مع مثال وكود كامل

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

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

هذا برنامج كامل يرتب الأعداد تصاعديًا ويطبع المصفوفة قبل الترتيب وبعده. احفظه باسم SelectionSort.java:

import java.util.Arrays;

public class SelectionSort {
    static void sort(int[] values) {
        for (int i = 0; i < values.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < values.length; j++) {
                if (values[j] < values[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = values[i];
            values[i] = values[minIndex];
            values[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {25, 20, 11, 18, 12};
        System.out.println("Before: " + Arrays.toString(numbers));
        sort(numbers);
        System.out.println("After:  " + Arrays.toString(numbers));
    }
}

الناتج بعد الترتيب هو [11, 12, 18, 20, 25]. تستخدم الدالة مصفوفة أعداد صحيحة، وتعدل ترتيب عناصرها مباشرة. المتغير minIndex يحتفظ بموقع أصغر عنصر تم العثور عليه في الدورة الحالية، بينما يحرك j عملية البحث من العنصر التالي حتى نهاية المصفوفة.

لنبدأ بالمصفوفة [25, 20, 11, 18, 12]. في الدورة الأولى نفحص العناصر كلها ونجد أن 11 هو الأصغر، فنبدله مع 25: [11, 20, 25, 18, 12]. في الدورة الثانية نبحث ابتداءً من الفهرس 1 ونجد 12، ثم نبدله مع 20: [11, 12, 25, 18, 20]. في الدورة الثالثة يصبح 18 أصغر عناصر الجزء المتبقي، ثم نكمل حتى نحصل على الترتيب النهائي.

بعد ترتيب أول n – 1 عناصر، يكون العنصر الأخير مرتبًا تلقائيًا لأنه القيمة المتبقية الوحيدة. لذلك لا تحتاج الحلقة الخارجية إلى دورة إضافية. أما الحلقة الداخلية فتبدأ من i + 1 لأن الجزء الذي يقع قبل i قد انتهى ترتيبه. هذه الحدود مهمة لتجنب مقارنة عنصر بنفسه أو الوصول إلى فهرس خارج المصفوفة.

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

لترتيب القيم من الأكبر إلى الأصغر، بدّل شرط المقارنة من values[j] < values[minIndex] إلى values[j] > values[minIndex]. تتبع الخوارزمية الفكرة نفسها لكنها تختار أكبر عنصر في كل دورة. القيم المكررة لا تسبب مشكلة؛ ستظهر متجاورة في النتيجة. لكن Selection Sort التقليدية ليست مستقرة دائمًا، أي إن ترتيب العناصر المتساوية قد يتغير عند نقل العناصر البعيدة.

استخدمها لفهم فكرة الفرز والحلقات المتداخلة أو لترتيب مجموعة صغيرة جدًا. في المشاريع الفعلية، توفر Java الدالة Arrays.sort، وهي أسرع ومختبرة لحالات متنوعة. إذا كان هدفك دراسة الخوارزميات فاقرأ أيضًا شرح Bubble Sort في Java ودرس البحث الثنائي Binary Search، واستكشف بقية دروس Java.

نعم، المثال يعدل المصفوفة الممررة نفسها، لذلك ستظهر النتيجة الجديدة عند طباعتها بعد استدعاء sort.

كلاهما تربيعي في الزمن، لكن Selection Sort تنفذ عادة تبديلات أقل. لا يعني ذلك أنها الخيار الأفضل للبيانات الكبيرة؛ فالخوارزميات القياسية في Java أكثر كفاءة.