כיצד למיין מערך ב-Java

מיון היא אחת הפעולות הנפוצות וההכרחיות ביותר בתכנות. זה מייצג את הסדר של קבוצה כלשהי של אלמנטים בסדר מסוים. מאמר זה עוסק בשיטות סטנדרטיות למיון מערכים ב-Java.

בקצרה על מיון

אז, מיון הוא הסדר של קבוצת נתונים. במקרה שלנו, מערכים. מטרת המיון של מערכים או מבני נתונים אחרים היא להקל על איתור, מניפולציה או ניתוח של הנתונים באוסף. מתכנתים צריכים מיון לעתים קרובות כל כך, שכל שפת תכנות כוללת שיטות מובנות למיון מערכים, רשימות ומבני נתונים מסודרים אחרים. כדי להשתמש בשיטות כאלה, התקשר אליהם. הפעולה מפשטת ככל האפשר. בדרך כלל, שיטות מובנות עוברות אופטימיזציה מקסימלית; ברוב המקרים, שימוש בהם עבור העבודה או הפרויקטים שלך הוא רעיון טוב. עם זאת, כמעט כל מתכנת, במהלך לימודיו, צריך ליישם אלגוריתמי מיון בעצמו. לכן, התרגילים המושלמים האלה מלמדים אותך להבין את עצם התכנות. בנוסף, לפעמים צריך שיטות מיון לא סטנדרטיות בעבודה. ישנם אלגוריתמי מיון רבים. יש להם חוזקות וחולשות בהתאם לסוג או גודלם של מערכי הנתונים. אלגוריתמי מיון סטנדרטיים כוללים מיון בועות, מיון בחירה, מיון הכנסה, מיון מיזוג ומיון מהיר.

שיטה מובנית למיון מערכים ב-Java: Arrays.sort

נתחיל מהפשוט ביותר. מישהו כבר כתב לנו שיטה למיון מערכים בג'אווה. שיטה זו נמצאת במחלקה 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 מאפשרת מיון טווח ספציפי של אלמנטים במערך .

הם מאפשרים לך לסדר במהירות את האלמנטים על סמך הסדר הטבעי שלהם או באמצעות השוואה מותאמת אישית. הבה נחקור שיטה זו באמצעות שתי דוגמאות, האחת כוללת מחרוזות.

דוגמה 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 wrapper במקום בסוג int הפרימיטיבי מכיוון שהמתודה Comparator.reverseOrder() דורשת אובייקטים. אם יש לך מערך של ערכי int פרימיטיביים, תצטרך גם להמיר אותם לאובייקטים שלמים לפני השימוש בגישה זו. באמצעות השוואה מותאמת אישית, תוכל למיין מערך בקלות בסדר יורד באמצעות שיטת Arrays.sort ב-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 הוא גודל המערך. הלולאה הפנימית משווה בין אלמנטים סמוכים. אם ההזמנה שגויה, השיטה מחליפה אותם. הליך זה חוזר על עצמו עד למיון המערך כולו. להלן פלט של התוכנית שלנו:

מיון בחירה

אלגוריתם הבחירה ממיין מערך על ידי מציאת שוב ושוב את האלמנט הקטן ביותר מהחלק הלא ממוין והצבתו בהתחלה. בוא נכתוב את זה ב-Java:

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+1 ועולה לאלמנט האחרון של המערך . הוא מחפש את האינדקס של הפריט הקטן ביותר בחלק הלא ממוין של המערך על ידי השוואת כל אלמנט עם האלמנט המינימלי הנוכחי ( arr[minIndex] ). אם נמצא אלמנט קטן מהאלמנט המינימלי הנוכחי, אנו מעדכנים את minIndex לאינדקס של אלמנט המינימום החדש. לאחר סיום הלולאה הפנימית, מצאנו את האינדקס של האלמנט המינימלי בחלק הלא ממוין של המערך . לאחר מכן אנו מחליפים את האלמנט המינימלי עם האלמנט הראשון של החלק הלא ממוין על ידי שימוש בטמפ' משתנה זמני. הלולאה החיצונית ממשיכה עד שכל הרכיבים ממוינים, ומרחיבה בהדרגה את החלק הממוין של המערך . לבסוף, המערך הממוין מודפס בשיטה הראשית לפני ואחרי הקריאה לשיטת selectSort .

מיזוג מיון

מיזוג מיון הוא אלגוריתם חלוקה-וכבוש המחלק באופן רקורסיבי את המערך לתת-מערכי משנה קטנים יותר, ממיין אותם ואז ממזג אותם כדי לקבל מערך ממוין. מיזוג מיון הוא יציב ונמצא בשימוש נרחב, במיוחד כאשר נדרשות יציבות ומורכבות זמן מובטחת במקרה הגרוע ביותר.

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 + " ");
        }
    }
}

הפלט של התוכנית הוא בדיוק כרגיל: כאן שיטת insertionSort מיישמת את אלגוריתם Insertion Sort. הוא חוזר דרך המערך ומחשיב כל אלמנט כמפתח. הוא משווה את המפתח עם האלמנטים שלפניו ומזיז אותם עמדה אחת קדימה אם הם גדולים יותר, למעשה מעביר את האלמנטים כדי לפנות מקום למפתח במיקום הנכון. הלולאה החיצונית חוזרת מהאלמנט השני ( i = 1 ) לאלמנט האחרון של המערך. הלולאה הפנימית מתחילה מהאלמנט הנוכחי ( arr[i] ) והולכת אחורה ( j = i - 1 ) עד שהיא מוצאת את המיקום הנכון עבור המפתח או מגיעה לתחילת המערך . בתוך הלולאה הפנימית, אם אלמנט ( arr[j] ) גדול מהמפתח, הוא מוזז עמדה אחת קדימה ( arr[j + 1] = arr[j] ) כדי לפנות מקום למפתח. תהליך זה נמשך עד שנמצא המיקום הנכון עבור המפתח. לאחר סיום הלולאה הפנימית, המפתח ממוקם במיקום הנכון ( arr[j + 1] = מפתח ). בשיטה הראשית נוצר מערך לדוגמה ומדפיס לפני ואחרי המיון בשיטת insertionSort .

מיון מהיר

מיון מהיר הוא אלגוריתם חלוקה-וכבוש שבוחר אלמנט pivot ומחלק את המערך סביב הציר. ככלל, מיון מהיר מהיר יותר ממיזוג מיון עבור מערכי נתונים קטנים ובינוניים בשל הגורמים הקבועים הנמוכים שלו.

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 + " ");
           }
       }
}

הפלט נמצא כאן: אז הנה יש לנו שלוש שיטות ליישם מיון מהיר. שיטת quickSort לוקחת שלושה פרמטרים: המערך למיון, האינדקס הנמוך של תת-המערך והאינדקס הגבוה של תת-המערך. בתחילה, הוא בודק אם למערך המשנה יש יותר מאלמנט אחד. אם כן, הוא בוחר ציר באמצעות שיטת המחיצה, ממיין באופן רקורסיבי את תת-המערך לפני הציר, וממיין באופן רקורסיבי את תת-המערך אחרי הציר. שיטת המחיצה בוחרת את הציר כאלמנט האחרון של המשנה ( arr[high] ). הוא מגדיר את מדד המחיצה (i) לאינדקס הנמוך מינוס 1. לאחר מכן הוא חוזר מהאינדקס הנמוך לאינדקס הגבוה - 1 ובודק אם כל אלמנט קטן או שווה לציר. אם כן, הוא מחליף את האלמנט עם האלמנט באינדקס המחיצה (i) ומגדיל את אינדקס המחיצה. לבסוף, הוא מחליף את אלמנט הציר עם האלמנט באינדקס המחיצה + 1 ומחזיר את אינדקס המחיצה. שיטת המחיצה בוחרת את הציר כאלמנט האחרון של המשנה ( arr[high] ). הוא מגדיר את מדד המחיצה (i) לאינדקס הנמוך מינוס 1. לאחר מכן הוא חוזר מהאינדקס הנמוך לאינדקס הגבוה - 1 ובודק אם כל פריט קטן או שווה לציר. אם כן, הוא מחליף את האלמנט עם האלמנט באינדקס המחיצה (i) ומגדיל את אינדקס המחיצה. לבסוף, הוא מחליף את אלמנט הציר עם האלמנט באינדקס המחיצה + 1 ומחזיר את אינדקס המחיצה. שיטת ההחלפה היא שיטת שירות המשמשת להחלפת שני אלמנטים במערך . בשיטה הראשית נוצר מערך לדוגמה ומדפיס לפני ואחרי המיון בשיטת quickSort .

מסקנות

ממאמר זה גילית כיצד למיין מערך בשפת Java. אתה יכול להשתמש בשיטת Arrays.sort מובנית או לכתוב יישומים משלך של שיטות מיון פופולריות כגון מיון בועות, מיון מיזוג וכן הלאה. כמו כן אתה יכול לנסות לפלוש לשיטת המיון שלך. זה תלוי במשימה שלך. אם אתה צריך לפתור בעיית מיון במהירות, פשוט השתמש בשיטה כתובה מראש. אם אתה לומד תכנות ומנסה להיות טוב יותר בזה, זה רעיון ממש טוב לכתוב כמה שיטות מיון לבד.