מיזוג מיון ב-Java

מה זה מיון מיזוג?

מיון המיזוג הוא האלגוריתם הנפוץ ביותר למיון נתונים בטכניקת " הפרד וכבוש ". באלגוריתם זה, הבעיה מחולקת לתת-בעיות ולאחר מכן לאחר המיון הן מתמזגות יחד. נניח שיש לנו רשימה של מספרים לא ממוינים, תוצאה של שיעור לנושא מסוים. כדי למיין אותם לפי סדר עולה נצטרך למקם אותם ברשימה שמתחילה מנמוך לגבוה. באלגוריתם מיון מיזוג זה, הרשימה תחולק לרשימות קטנות יותר כדי למיין אותן בסדר עולה ואז היא תמזג את התוצאות להבנה טובה יותר. ניתן להסביר מיזוג מיון ב-Java באמצעות דוגמה של מערך {6,9,8,2,4,1}, שקול אותו כתוצאה ממבחן מחלקה מתוך 10. המערך (של התוצאות) יחולק שוב ושוב לנתחים קטנים יותר עד שגודלם הוא 1. לאחר מכן מתרחש תהליך המיזוג תוך מיון המספרים בו זמנית. זה יספק לנו תוצאה שמתחילה מהציונים הנמוכים ביותר ועד לציונים הגבוהים ביותר שהתקבלו. מערך זה יחולק לשני מערכים שיכילו 3 אלמנטים כל אחד כפי שמוצג להלן בשלב 2 והוא ממשיך להתחלק עד שמגיעים לאחדות בשלב 4 . לאחר מכן, אלגוריתם המיזוג מתחיל למיין את המספרים צעד אחד בכל פעם ( שלב 5 ) ולאחר מכן ממזג את המספרים למערך גדול יותר בשלבים 6 ו-7 .

יישום

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

Merge_Sort_Algo (Array, Beginning, End)
/** Three parameters required for the Merge Sort Algorithm
 * Array = values of the array
 * Beginning = the starting element of the array
 * End = the ending element of the array*/

if (Beginning < End) // condition check Beginning must be less than End

set Middle = (Beginning + End) / 2 // Assigning Middle to the array

Merge_Sort_Algo (Array, Beginning, Middle) /** Sorting and merging of elements from Beginning to the Middle */

Merge_Sort_Algo (Array, Middle +1, End) /** Sorting and merging of elements from Middle to the End */

Merge (Array, Beginning, Middle, End) // Merging both the sorted arrays

end of if

End Merge_Sort_Algo

ראשית, דרך התנאי אם התחלה וסוף משמשים לקביעת האמצע. ואז בשלב הבא נוצרים 2 תת-מערכים חדשים החל מההתחלה לאמצע והשני מתחיל מהאמצע +1 עד הסוף. מערכים אלו מחולקים עד שאורכם הופך ל-1 ואז דרך פונקציית המיזוג מתמזגים בחזרה את מערכי המשנה הממוינים Beginning, Middle, Middle+1 ו-End כדי לרכוש את הפתרון.

דוגמא

הקוד הבא ב-Java מסביר את אלגוריתם מיון המיזוג:

import java.util.Arrays;

class HelloWorld {

    public static void merge(

  int[] array, int[] new_array_1, int[] new_array_2, int left, int right) {
   // defining parameters

    int i = 0, j = 0, k = 0;

    while (i < left && j < right) {  // conditions for merging

        if (new_array_1[i] <= new_array_2[j]) {
            array[k++] = new_array_1[i++];
        }
        else {
            array[k++] = new_array_2[j++];
        }
    }

    while (i < left) {
        array[k++] = new_array_1[i++];
    }

    while (j < right) {
        array[k++] = new_array_2[j++];
    }
}

    public static void mergeSort(int[] array, int length) { /** required parameters */
	if (length < 2) {  //condition for the length of array
    	return;
	}

	int middle = length / 2;  // defining new parameter middle

	int [ ] new_array_1 = new int [middle]; /** defining the new first array after division */
	int [ ] new_array_2 = new int [length - middle]; /** defining the new second array */


	for (int i = 0; i < middle; i++) { /**applying condition for sorting of new array 1 */
    	new_array_1 [ i ] = array [ i ];
	}

	for (int i = middle; i < length ; i++) { /**applying condition for sorting of new array 2 */
    	new_array_2 [ i - middle] = array [ i ];
	}

	mergeSort (new_array_1, middle); /** calling merge sort function for new array 1 */
	mergeSort (new_array_2, length - middle); /** calling merge sort function for new array 2 */


	merge(array, new_array_1, new_array_2, middle, length - middle); /** calling function for merging of new array 1 and new array 2 */
}


    public static void main(String[] args) {

        int [ ] testScores = {6,9,8,2,4,1};
        int size = testScores.length;

        System.out.println("Original Array " + Arrays.toString(testScores) + "\n");

        mergeSort(testScores, size);

        System.out.println("After Merge Sort " + Arrays.toString(testScores) + "\n");
    }
}

תְפוּקָה

סיכום

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