כיצד להשתמש במיון הבחירה

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

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

מיון הבחירה: מבט קרוב יותר

נניח שיש לך את הרשימה: [39, 82, 2, 51, 30, 42, 7]. כדי למיין את הרשימה באמצעות מיון הבחירה, יהיה עליכם למצוא תחילה את המספר הגבוה ביותר בה.

ברשימה הנתונה המספר הוא 82. החלף 82 עם המספר באינדקס הגבוה ביותר (כלומר 7).

לאחר המעבר הראשון, סדר הרשימה החדש יהיה: [39, 7, 2, 51, 30, 42, 82]. בכל פעם שהאלגוריתם עובר על כל הרשימה, זה נקרא "לעבור".

שים לב שהרשימה שומרת על רשימת משנה ממוינת ועל רשימת משנה לא ממוינת במהלך תהליך המיון.

קָשׁוּר: מהי סימון ביג-או?

הרשימה המקורית מתחילה ברשימה ממוינת של אפס פריטים ורשימה לא ממוינת של כל הפריטים. לאחר המעבר הראשון, יש לו רשימה ממוינת הכוללת רק את המספר 82.

במעבר השני, המספר הגבוה ביותר ברשימת המשנה הלא ממוינת יהיה 51. מספר זה יוחלף עם 42 בכדי לתת את סדר הרשימה החדש למטה:

[39, 7, 2, 42, 30, 51, 82].

התהליך חוזר על עצמו עד למיון הרשימה כולה. האיור שלהלן מסכם את כל התהליך:

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

ניתוח אלגוריתמים

כדי להשיג את המורכבות (באמצעות סימון Big-O) של אלגוריתם זה, פעל למטה:

במעבר הראשון, (n-1) נערכות השוואות. במעבר השני, (n-2). במעבר השלישי, (n-3) וכן הלאה עד המעבר (n-1) העושה השוואה אחת בלבד.

סיכום ההשוואות להלן נותן:

(n-1) + (n-1) + (n-1) +... + 1 = ((n-1) n) / 2.

לכן מיון הבחירה הוא O (n²).

יישום קוד

הקוד מציג פונקציות בהן ניתן להשתמש לביצוע מיון בחירה באמצעות פייתון וג'אווה.

פִּיתוֹן:

בחירת def סוג (הרשימה שלי):
עבור x בטווח (len (mylist) - 1, 0, -1):
max_idx = 0
עבור posn בטווח (1, x + 1):
אם הרשימה שלי [posn]> הרשימה שלי [max_idx]:
max_idx = posn
temp = הרשימה שלי [x]
mylist [x] = mylist [max_idx]
mylist [max_idx] = temp

Java:

בחירת בטל סדר (int my_array []) { 
עבור (int x = 0; x { 
אינדקס int = x; 
עבור (int y = x + 1; y אם (my_array [y] אינדקס = y; // מצא את האינדקס הנמוך ביותר 
} 
} 
int temp = my_array [index]; // temp הוא אחסון זמני
my_array [index] = my_array [x]; 
my_array [x] = temp; 
}}

עוברים ממבחר למיון למיון מיזוג

כפי שהראה ניתוח האלגוריתם לעיל, אלגוריתם מיון הבחירה הוא O (n²). יש לו מורכבות אקספוננציאלית ולכן הוא לא יעיל עבור מערכי נתונים גדולים מאוד.

אלגוריתם הרבה יותר טוב לשימוש יהיה מיון מיזוג עם מורכבות O (nlogn). ועכשיו אתה יודע איך עובד מיון הבחירה, הבא ברשימת המחקר שלך לאלגוריתמי מיון צריך להיות מיון המיזוג.

על הסופר