كيفية فرز صفيف في جافا

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

باختصار حول الفرز

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

الطريقة المضمنة لفرز المصفوفات في Java: Arrays.sort

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

• Arrays.sort(Array) : استخدمه لفرز صفائف الأنواع أو الكائنات البدائية بترتيب تصاعدي. ويستخدم الترتيب الطبيعي للعناصر.
• Arrays.sort(Array, fromIndex, toIndex) : تسمح لك طريقة الفرز المحملة بشكل زائد بفرز جزء فقط من المصفوفة المحددة بواسطة معلمات fromIndex وtoIndex.
• Arrays.sort(Array, comparator) : هذا الخيار مخصص لفرز صفائف الكائنات باستخدام مقارن مخصص. يحدد المقارنة ترتيب العناصر.
• Arrays.parallelSort(Array) : يقوم إصدار هذه الطريقة بفرز المصفوفة بشكل متوازٍ، باستخدام سلاسل رسائل متعددة لتحسين الأداء. إنه مفيد لفرز المصفوفات الكبيرة.
• Arrays.parallelSort(Array, fromIndex, toIndex) : هذه النسخة المحملة بشكل زائد من طريقة ParallelSort تسمح بفرز نطاق معين من العناصر في Array .

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

مثال 1: فرز السلاسل

لنفترض أن لدينا مجموعة من الآلات الموسيقية الوترية: "الكمان"، و"الفيولا"، و"التشيلو"، و"الباس المزدوج". يمكننا استخدام طريقة Array.sort لترتيبها أبجديًا.

import java.util.Arrays;
//Arrays.sort example
public class StringSortExample {
    public static void main(String[] args) {
        String[] instruments = {"violin", "viola", "cello", "double bass"};

        Arrays.sort(instruments);

        System.out.println("Sorted Instruments:");
        for (String instrument : instruments) {
            System.out.println(instrument);
        }
    }
}

الإخراج هنا: في هذا البرنامج، نقوم أولاً باستيراد فئة java.util.Arrays للوصول إلى طريقة Array.sort . ثم نقوم بإنشاء مصفوفة سلسلة تسمى الآلات التي تحتوي على أسماء الآلات الموسيقية. بعد ذلك، نسمي Arrays.sort(instruments) . لذلك تحصل هذه الطريقة على مصفوفة، وتقوم بفرز العناصر بترتيب تصاعدي بناءً على ترتيبها الطبيعي (أبجديًا). أخيرًا، نمر عبر المصفوفة التي تم فرزها ونطبع كل أداة.

مثال 2: فرز الأعداد الصحيحة

دعونا نفكر في مثال آخر حيث نقوم بفرز مجموعة من الأعداد الصحيحة بترتيب تصاعدي.

import java.util.Arrays;

public class IntegerSortExample {
    public static void main(String[] args) {
        int[] numbers = {8, 2, 7, 3, 1, 5};
//sort an array using Arrays.sort
        Arrays.sort(numbers);

        System.out.println("Sorted Numbers:");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

انتاج: نقوم هنا بإنشاء مصفوفة أعداد صحيحة تسمى أرقامًا تحتوي على عدة عناصر غير مصنفة. بعد ذلك، نستدعي Arrays.sort(numbers) لفرز مصفوفة بترتيب تصاعدي. لاحظ أن الأسلوب Array.sort يقوم بتعديل المصفوفة الأصلية في مكانها. لذا، للحفاظ على المصفوفة الأصلية ، قم بعمل نسخة قبل الفرز.

مثال 3: ترتيب تنازلي

ماذا عن الترتيب التنازلي؟ كما أنه سهل مع Arrays.sort . مجرد استخدام المقارنة المخصصة. هنا مثال:

import java.util.Arrays;
import java.util.Comparator;
//Arrays.sort with custom comparator example
public class DescendingSortExample {
    public static void main(String[] args) {
        Integer[] numbers = {8, 2, 7, 3, 1, 5};
        //sort an Array using Arrays.sort
        Arrays.sort(numbers, Comparator.reverseOrder());

        System.out.println("Sorted Numbers (Descending):");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

الإخراج هو التالي: لدينا هنا مجموعة من الأعداد الصحيحة المسماة أرقامًا. من خلال تمرير Comparator.reverseOrder() ‎ كوسيطة ثانية للأسلوب Arrays.sort ، فإننا نحدد مقارنًا مخصصًا يقوم بفرز العناصر بترتيب تنازلي. يقوم الأسلوب Comparator.reverseOrder() بإرجاع مقارن يعكس الترتيب الطبيعي للعناصر. لاحظ أننا هنا نستخدم فئة مجمّع Integer بدلاً من النوع int البدائي لأن أسلوب Comparator.reverseOrder() يتطلب كائنات. إذا كان لديك مصفوفة من قيم int البدائية، فستحتاج أيضًا إلى تحويلها إلى كائنات Integer قبل استخدام هذا الأسلوب. باستخدام مقارنة مخصصة، يمكنك بسهولة فرز المصفوفة بترتيب تنازلي باستخدام طريقة Arrays.sort في Java.

خوارزميات الفرز الكلاسيكية المكتوبة ذاتيًا في Java

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

فقاعة الفرز

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

public class BubbleSort {

       public static void bubbleSort(int[] myArray) {
           int n = myArray.length;
           for (int i = 0; i < n - 1; i++) {
               for (int j = 0; j < n - i - 1; j++) {
                   if (myArray[j] > myArray[j + 1]) {
                       // Swap myArray[j] and myArray[j+1]
                       int temp = myArray[j];
                       myArray[j] = myArray[j + 1];
                       myArray[j + 1] = temp;
                   }
               }
           }
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 7, 90, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           bubbleSort(arr);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

هنا تأخذ الطريقة مجموعة من الأعداد الصحيحة كمدخلات. تتراوح الحلقة الخارجية من 0 إلى n-1. حيث n هو حجم المصفوفة. تقارن الحلقة الداخلية العناصر المجاورة. إذا كان الترتيب خاطئا، فإن الطريقة تستبدلهم. يتم تكرار هذا الإجراء حتى يتم فرز المصفوفة بأكملها. هنا هو الناتج من برنامجنا:

اختيار نوع

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

public class SelectionSort {
   public static void selectionSort(int[] myArray) {
       int n = myArray.length;

       for (int i = 0; i < n - 1; i++) {
           int minIndex = i;

           // Find the index of the minimum element in the unsorted part of the array
           for (int j = i + 1; j < n; j++) {
               if (myArray[j] < myArray[minIndex]) {
                   minIndex = j;
               }
           }

           // Swap the minimum element with the first element of the unsorted part
           int temp = myArray[minIndex];
           myArray[minIndex] = myArray[i];
           myArray[i] = temp;
       }
   }

   public static void main(String[] args) {
       int[] arr = {18, 28, 45, 2, 90, 7};

       System.out.println("Array before sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }

       selectionSort(arr);

       System.out.println("\nArray after sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }
   }
}

وهنا إخراج البرنامج: دعونا نشرح ذلك خطوة بخطوة. تتكرر الحلقة الخارجية من بداية المصفوفة إلى العنصر الثاني إلى الأخير (حتى n-1). تحدد هذه الحلقة كل عنصر واحدًا تلو الآخر كنقطة بداية للجزء غير المصنف من المصفوفة . داخل الحلقة الخارجية، نقوم بتهيئة minIndex إلى الفهرس الحالي i ، على افتراض أنه فهرس أصغر عنصر في الجزء غير المصنف من المصفوفة . تبدأ الحلقة الداخلية من i+1 وتنتقل إلى العنصر الأخير في المصفوفة . يبحث عن فهرس أصغر عنصر في الجزء غير المصنف من المصفوفة من خلال مقارنة كل عنصر بالعنصر الأدنى الحالي ( arr[minIndex] ). إذا وجدنا عنصرًا أصغر من الحد الأدنى الحالي للعنصر، فإننا نقوم بتحديث minIndex إلى فهرس الحد الأدنى الجديد للعنصر. بعد اكتمال الحلقة الداخلية، وجدنا فهرس الحد الأدنى من العناصر في الجزء غير المصنف من المصفوفة . نقوم بعد ذلك بتبديل العنصر الأدنى بالعنصر الأول من الجزء غير المصنف باستخدام متغير مؤقت. تستمر الحلقة الخارجية حتى يتم فرز جميع العناصر، مما يؤدي إلى توسيع الجزء المصنف من المصفوفة تدريجيًا . أخيرًا، تتم طباعة المصفوفة التي تم فرزها بالطريقة الرئيسية قبل وبعد استدعاء طريقة التحديد .

دمج الفرز

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

public class MergeSort {

      //Merge Sort array
      public static void mergeSort(int[] myArray) {
        if (myArray.length <= 1) {
            return;
        }

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

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

        mergeSort(left);
        mergeSort(right);

        merge(myArray, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0; // index for left subarray
        int j = 0; // index for right subarray
        int k = 0; // index for merged array

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

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

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

    public static void main(String[] args) {
        int[] arr = {18, 2, 28, 7, 90, 45};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        mergeSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

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

ترتيب بالإدراج

يعمل فرز الإدراج عن طريق إدراج عنصر من الجزء الذي لم يتم فرزه بشكل متكرر في موضعه الصحيح في الجزء الذي تم فرزه. إنه يؤدي أداءً جيدًا لمجموعات البيانات الصغيرة أو البيانات التي تم فرزها تقريبًا.

public class InsertionSort {
    public static void insertionSort(int[] myArray) {
        int n = myArray.length;

        for (int i = 1; i < n; i++) {
            int key = myArray[i];
            int j = i - 1;

            while (j >= 0 && myArray[j] > key) {
                myArray[j + 1] = myArray[j];
                j--;
            }

            myArray[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 90, 7, 28, 45, 2};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        insertionSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

مخرجات البرنامج كالعادة: هنا تقوم طريقة الإدراج بتنفيذ خوارزمية فرز الإدراج. إنه يتكرر عبر المصفوفة ويعتبر كل عنصر بمثابة مفتاح. فهو يقارن المفتاح بالعناصر التي أمامه ويحركها إلى الأمام بمقدار موضع واحد إذا كانت أكبر، مما يؤدي إلى تحويل العناصر بشكل فعال لإفساح المجال للمفتاح في الموضع الصحيح. تتكرر الحلقة الخارجية من العنصر الثاني ( i = 1 ) إلى العنصر الأخير في المصفوفة. تبدأ الحلقة الداخلية من العنصر الحالي ( arr[i] ) وتعود للخلف ( j = i - 1 ) حتى تجد الموضع الصحيح للمفتاح أو تصل إلى بداية المصفوفة . داخل الحلقة الداخلية، إذا كان العنصر ( arr[j] ) أكبر من المفتاح، فسيتم إزاحته موضعًا واحدًا للأمام ( arr[j + 1] = arr[j] ) لإفساح المجال للمفتاح. تستمر هذه العملية حتى يتم العثور على الموضع الصحيح للمفتاح. بعد اكتمال الحلقة الداخلية، يتم وضع المفتاح في الموضع الصحيح ( arr[j + 1] = key ). في الطريقة الرئيسية، يتم إنشاء مصفوفة نموذجية وطباعتها قبل وبعد الفرز باستخدام طريقة الإدراج .

فرز سريع

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

public class QuickSort {

       public static void quickSort(int[] myArray, int low, int high) {
           if (low < high) {
               int pivotIndex = partition(myArray, low, high);
               quickSort(myArray, low, pivotIndex - 1);
               quickSort(myArray, pivotIndex + 1, high);
           }
       }

       public static int partition(int[] arr, int low, int high) {
           int pivot = arr[high];
           int i = low - 1;

           for (int j = low; j < high; j++) {
               if (arr[j] <= pivot) {
                   i++;
                   swap(arr, i, j);
               }
           }

           swap(arr, i + 1, high);
           return i + 1;
       }

       public static void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 90, 7, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           quickSort(arr, 0, arr.length - 1);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

الإخراج هنا: إذن لدينا هنا ثلاث طرق لتنفيذ الفرز السريع. تأخذ طريقة الفرز السريع ثلاث معلمات: المصفوفة المراد فرزها، والمؤشر المنخفض للمصفوفة الفرعية، والمؤشر المرتفع للمصفوفة الفرعية. في البداية، يتحقق مما إذا كانت المصفوفة الفرعية تحتوي على أكثر من عنصر واحد. إذا كان الأمر كذلك، فإنه يحدد محورًا باستخدام طريقة التقسيم، ويفرز المصفوفة الفرعية بشكل متكرر قبل المحور، ويفرز بشكل متكرر المصفوفة الفرعية بعد المحور. تحدد طريقة التقسيم المحور باعتباره العنصر الأخير في المصفوفة الفرعية ( arr[high] ). يقوم بتعيين فهرس القسم (i) على الفهرس المنخفض ناقص 1. ثم يتكرر من الفهرس المنخفض إلى الفهرس العالي - 1 ويتحقق مما إذا كان كل عنصر أقل من أو يساوي المحور. إذا كان الأمر كذلك، فإنه يقوم بتبديل العنصر بالعنصر الموجود في فهرس القسم (i) ويزيد من فهرس القسم. وأخيرًا، يقوم بتبديل العنصر المحوري بالعنصر الموجود في فهرس القسم + 1 وإرجاع فهرس القسم. تحدد طريقة التقسيم المحور باعتباره العنصر الأخير في المصفوفة الفرعية ( arr[high] ). يقوم بتعيين فهرس القسم (i) على الفهرس المنخفض ناقص 1. ثم يتكرر من الفهرس المنخفض إلى الفهرس العالي - 1 ويتحقق مما إذا كان كل عنصر أصغر أو يساوي المحور. إذا كان الأمر كذلك، فإنه يقوم بتبديل العنصر بالعنصر الموجود في فهرس القسم (i) ويزيد من فهرس القسم. وأخيرًا، يقوم بتبديل العنصر المحوري بالعنصر الموجود في فهرس القسم + 1 وإرجاع فهرس القسم. طريقة المبادلة هي طريقة مساعدة تستخدم لتبديل عنصرين في المصفوفة . في الطريقة الرئيسية ، يتم إنشاء مصفوفة نموذجية وطباعتها قبل وبعد الفرز باستخدام طريقة الفرز السريع .

الاستنتاجات

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