מיון הבחירה ב- Java
1. הקדמה
במדריך זה, אנו ללמוד מיון בחירה, ראה את יישומה ב- Java, ונתח את ביצועיה.
2. סקירת אלגוריתם
מיון בחירה מתחיל באלמנט במיקום הראשון של מערך לא ממוין וסורק דרך האלמנטים הבאים אל למצוא את האלמנט הקטן ביותר. לאחר שנמצא, האלמנט הקטן ביותר מוחלף עם האלמנט במצב הראשון.
האלגוריתם עובר לאחר מכן לאלמנט במיקום השני וסורק דרך אלמנטים הבאים כדי למצוא את האינדקס של האלמנט הקטן ביותר. לאחר שנמצא, האלמנט השני הקטן ביותר מוחלף עם האלמנט במצב השני.
תהליך זה נמשך עד שנגיע לאלמנט n-1 של המערך, מה שמציב את האלמנט הקטן ביותר n-1 במיקום n-1. האלמנט האחרון נופל באופן אוטומטי במקומו, באיטרציה n-1, ובכך ממיין את המערך.
אנחנו מוצאים האלמנט הגדול ביותר במקום האלמנט הקטן ביותר למיון המערך בסדר יורד.
בואו נראה דוגמה למערך לא ממוין ונמיין אותו בסדר עולה בכדי להבין את האלגוריתם באופן חזותי.
2.1. דוגמה
שקול את המערך הלא ממוין הבא:
int [] arr = {5, 4, 1, 6, 2}
איטרציה 1
בהתחשב בעבודה של האלגוריתם לעיל, אנו מתחילים עם האלמנט במיקום הראשון - 5 - וסורקים דרך כל האלמנטים הבאים כדי למצוא את האלמנט הקטן ביותר - 1. לאחר מכן אנו מחליפים את האלמנט הקטן ביותר עם האלמנט במיקום הראשון.
מערך השינויים שעבר שינוי נראה כך:
{ 1 , 4 , 5 , 6 , 2 }
סך כל ההשוואות שנעשו: 4
איטרציה 2
באיטרציה השנייה, אנו עוברים לאלמנט השני - 4 - וסורקים דרך האלמנטים הבאים כדי למצוא את האלמנט השני הקטן ביותר - 2. לאחר מכן אנו מחליפים את האלמנט השני הקטן ביותר עם האלמנט במצב השני.
המערך ששונה נראה כעת:
{ 1 , 2 , 5 , 6 , 4 }
סך כל ההשוואות שנעשו: 3
אם נמשיך באופן דומה, יש לנו את האיטרציות הבאות:
איטרציה 3
{ 1 , 2 , 4 , 6 , 5 }
סך כל ההשוואות שבוצעו: 2
איטרציה 4
{ 1 , 2 , 4 , 5 , 6 }
סך כל ההשוואות שנעשו: 1
3.יישום
בואו ניישם את מיון הבחירה באמצעות כמה ל לולאות:
public static void sortAscending (final int [] arr) {for (int i = 0; i <arrlength - 1; i ++) {int minElementIndex = i; עבור (int j = i + 1; j arr [j]) {minElementIndex = j; }} אם (minElementIndex! = i) {int temp = arr [i]; arr [i] = arr [minElementIndex]; arr [minElementIndex] = temp; }}}כמובן, כדי להפוך את זה נוכל לעשות משהו די דומה:
חלל סטטי ציבורי sortDescending (final int [] arr) {for (int i = 0; i <arrlength - 1; i ++) {int maxElementIndex = i; עבור (int j = i + 1; j <arrlength; j ++) {if (arr [maxElementIndex] <arr [j]) {maxElementIndex = j; }} אם (maxElementIndex! = i) {int temp = arr [i]; arr [i] = arr [maxElementIndex]; arr [maxElementIndex] = temp; }}}ועם קצת יותר שומן במרפקים, נוכל לשלב אותם באמצעות משווהס.
4. סקירת הביצועים
4.1. זְמַן
בדוגמה שראינו קודם, בחירת האלמנט הקטן ביותר דרשה סך של (n-1) השוואות ואחריו החלפתו למיקום הראשון. בדומה לכך, בחירת האלמנט הקטן ביותר הבא הנדרש (n-2) השוואות ואחריהן החלפה במיקום השני, וכן הלאה.
לפיכך, החל מאינדקס 0, אנו מבצעים n-1, n-2, n-3, n-4…. 1 השוואות. האלמנט האחרון נופל באופן אוטומטי עקב איטרציות והחלפות קודמות.
מתמטית, ה סכום הראשון n-1 מספרים טבעיים יגידו לנו כמה השוואות אנחנו צריכים בכדי למיין מערך בגודל נ באמצעות מיון בחירה.
הנוסחה לסכום של נ מספרים טבעיים הוא n (n + 1) / 2.
במקרה שלנו, אנחנו צריכים את הסכום של הראשון n-1 מספרים טבעיים. לכן, אנחנו מחליפים נ עם n-1 בנוסחה שלעיל כדי להשיג:
(n-1) (n-1 + 1) / 2 = (n-1) n / 2 = (n ^ 2-n) / 2
כפי ש n ^ 2 גדל באופן בולט כמו נ גדל, אנו רואים את הכוח הגבוה יותר של נ כמדד הביצועים, מה שהופך את האלגוריתם הזה ל- מורכבות הזמן של O (n ^ 2).
4.2. מֶרחָב
מבחינת מורכבות שטח עזר, מיון הבחירה דורש משתנה נוסף אחד כדי להחזיק את הערך באופן זמני להחלפה. לכן, מיון הבחירה מורכבות החלל היא O (1).
5. מסקנה
מיון הבחירה הוא אלגוריתם מיון פשוט מאוד להבנה וליישום. לצערי, מורכבות הזמן הריבועית שלה הופכת אותו לטכניקת מיון יקרה. כמו כן, מכיוון שהאלגוריתם צריך לסרוק דרך כל אלמנט, המקרה הטוב ביותר, המקרה הממוצע ומורכבות הזמן הגרועה ביותר זהה.
לטכניקות מיון אחרות כמו מיון הכנסה ומיון מעטפת יש מורכבות זמן ריבועית בזמן הגרוע ביותר, אך הן טובות יותר במקרים הטובים והממוצעים.
בדוק את הקוד השלם עבור בחירה מיין ב- GitHub.
