אלגוריתמי מיון

מיון הוא תהליך של סידור האלמנטים של מערך כך שניתן למקם אותם בסדר עולה או יורד. לדוגמה, שקול מערך A = {A1, A2, A3, A4, ?? An }, המערך נקרא להיות בסדר עולה אם הרכיב של A מסודרים כמו A1 > A2 > A3 > A4 > A5 > ? > א.

שקול מערך;

int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9)

המערך הממוין בסדר עולה יינתן בתור;

A[] = { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }

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

אלגוריתמי מיון

אלגוריתמי מיון מתוארים בטבלה הבאה יחד עם התיאור.

SN	אלגוריתמי מיון	תיאור
1	מיון בועות	זוהי שיטת המיון הפשוטה ביותר שמבצעת מיון על ידי הזזת האלמנט הגדול ביותר לאינדקס הגבוה ביותר של המערך. זה כולל השוואת כל אלמנט לאלמנט הסמוך לו והחלפתם בהתאם.
2	מיון דלי	מיון דלי ידוע גם בשם מיון פח. זה עובד על ידי הפצת האלמנט לתוך המערך הנקרא גם buckets. באלגוריתמי מיון זה, הדליים ממוינים בנפרד באמצעות אלגוריתמי מיון שונים.
3	מיון מסרק	Comb Sort היא הצורה המתקדמת של Bubble Sort. מיון בועה משווה את כל הערכים הסמוכים בעוד מיון מסרק מסיר את כל ערכי הצבים או ערכים קטנים לקראת סוף הרשימה.
4	ספירת מיון	זוהי טכניקת מיון המבוססת על המפתחות כלומר אובייקטים נאספים לפי מפתחות שהם מספרים שלמים קטנים. ספירת מיון מחשבת את מספר המופעים של אובייקטים ומאחסנת את ערכי המפתח שלו. מערך חדש נוצר על ידי הוספת רכיבי מפתח קודמים והקצאה לאובייקטים.
5	מיון ערימה	במיון הערימה, הערימה המינימלית או הערימה המקסימלית נשמרת ממרכיבי המערך בהתאם לבחירה והאלמנטים ממוינים על ידי מחיקת אלמנט הבסיס של הערימה.
6	מיון הכנסה	כפי שהשם מרמז, מיון הוספה מכניס כל רכיב של המערך למקומו המתאים. זוהי שיטת מיון פשוטה מאוד המשמשת לסידור חפיסת הקלפים תוך כדי משחק ברידג'.
7	מיזוג מיון	מיון מיזוג עוקב אחר גישת חלוקה וכבוש שבה, הרשימה מחולקת תחילה לקבוצות של אלמנטים שווים ולאחר מכן כל מחצית מהרשימה ממוינת באמצעות מיון מיזוג. הרשימה הממוינת משולבת שוב ליצירת מערך ממוין יסודי.
8	מיון מהיר	מיון מהיר הוא אלגוריתמי המיון האופטימליים ביותר שמבצעים מיון בהשוואות O(n log n). כמו מיון מיזוג, גם מיון מהיר פועל באמצעות גישת חלוקה וכבוש.
9	מיון רדיקס	במיון Radix, המיון נעשה תוך שאנו ממיינים את השמות לפי סדר האלפביתי שלהם. זהו אלגוריתם המיון הליניארי המשמש עבור אינגרס.
10	מיון בחירה	מיון הבחירה מוצא את האלמנט הקטן ביותר במערך וממקם אותו במקום הראשון ברשימה, ואז הוא מוצא את האלמנט השני הקטן ביותר במערך וממקם אותו במקום השני. תהליך זה נמשך עד שכל האלמנטים מועברים לסדר הנכון שלהם. הוא נושא זמן ריצה O(n2) שהוא גרוע יותר ממיון ההכנסה.
אחד עשר	מיון מעטפת	מיון מעטפת הוא הכללה של מיון הכנסה שמתגבר על החסרונות של מיון הכנסה על ידי השוואת אלמנטים המופרדים בפער של מספר מיקומים.