מיון (אלגוריתם)

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

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

תעודת זהות	שם משפחה	שם פרטי
198756179	תמם	ראובן
296097267	שפירא	אברהם
567323908	אוחנה	גל
490897299	ברקוביץ	טל

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

באלגוריתמים הדבר נחוץ כי לעיתים קרובות פעולות על קלט ממוין הן מסיבוכיות נמוכה יותר. למשל, ניתן למצוא את הערך המקסימלי והמינימלי (או בכלל, ה-$\ k$ בגודלו) במערך ממוין בסיבוכיות זמן של $\ O(1)$ ולמצוא איבר כללי במערך בסיבוכיות לוגריתמית. (באמצעות חיפוש בינארי, למשל)

אלגוריתמי מיון מבוססי השוואות

ישנם אלגוריתמי מיון רבים, הנבדלים זה מזה בסיבוכיות הזמן והזיכרון שלהם, בפשטות מימושם ובהנחה על הפעולות הבסיסיות. חלוקה מקובלת היא בין אלגוריתמי המיון המבוססים על פעולת השוואה בין האיברים הנתונים לבין אלה המאפשרים פעולות כלליות על האיברים. כל אלגוריתמי המיון המבוססים על פעולת השוואה דורשים לפחות $\ \Omega (n\log n)$ פעולות השוואה במקרה הגרוע על-מנת לבצעם.

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

מאחר שקיימות לכל $\ n$ איברים $\ n!$ דרכים לסדרם, הרי שמספר העלים בעץ יהיה $\ n!$, ומכיוון שדרגת העץ חסומה, לפי משפט מתורת הגרפים גובה העץ (מספר ההשוואות שהאלגוריתם יאלץ לעשות לפני שיגיע לעלה) יהיה $\ \log(n!)$. ניתן לראות ש-$\ \log(n!)=\Theta (n\log n)$ (באמצעות נוסחת סטירלינג) ומכאן נובע החסם.

סיווג מיונים

את המיונים נהוג לסווג לפי מספר נתונים:

• סיבוכיות האלגוריתם - (טוב, גרוע וממוצע) כאשר נתון גודל מערך $\ n$, לרוב המיונים יהיה סיבוכיות בגודל $\ O(n\log n)$ במקרה הממוצע, ו $\ O(n^{2})$ במקרה הגרוע. הרצוי והשאיפה היא להגיע ל $\ O(n)$ אולם מקרה זה אינו מציאותי באלגרותמי מיון על בסיס השוואה.
• שימוש בזיכרון מחשב - מיונים שונים צורכים מקומות זכרון נוספים, ואילו אלגוריתמי מיון אחרים הנחשבים לתוך מקומיים הממיינים את המערך באותו מקום, לעיתים גם עד $\ O(logn)$ של תוספת זכרון נחשב לאלגוריתם תוך מקומי.
• שימוש ברקורסיה - אלגוריתמים שונים בנויים על רקורסיות, אחרים לא ניתן לממש ברקורסייה, וישנם כאילו שניתן לממשם בשני הצורות.
• יציבות - אלגוריתמי מיון יציבים ממיינים אלמנטים זהים באותו סדר שהם מופיעים בקלט. סידור מחדש של האוסף אינו גורם לשינוי בסדר שבין האלמנטים הזהים בינם לבין עצמם.

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

מיונים מבוססי השוואות:

• מיון בועות (bubble sort), הידוע גם בכינוי מיון החלפה הוא מיון פשוט, שבו מושווים שני איברים סמוכים במערך המתמיין. מיון זה הפועל בסיבוכיות של $\ \Theta (n^{2})$. המיון קיבל את שמו מהדרך בה מבעבעים אלמנטים במערך. מבחינת צריכת זיכרון האלגוריתם חסכוני, והוא דורש $O\left(1\right)$.
• מיון הכנסה (insertion sort) הוא אלגוריתם מיון השוואתי פשוט. הוא יעיל עבור מערכים קטנים ועבור מערכים ממוינים או כמעט ממוינים. סיבוכיות הזמן של האלגוריתם היא $O\left(n^{2}\right)$. מבחינת צריכת זיכרון האלגוריתם חסכוני, והוא דורש $O\left(1\right)$.
• מיון בחירה (selection sort) הוא אלגוריתם השוואתי פשוט אך לא יעיל, שבו נמצא בכל צעד האיבר בעל הערך הקטן ביותר, והוא מועבר למקומו. סיבוכיות הזמן של האלגוריתם היא $O\left(n^{2}\right)$. מבחינת צריכת זיכרון האלגוריתם חסכוני, והוא דורש $O\left(1\right)$.
• מיון ערימה (heap sort) הוא אלגוריתם מיון אשר נעזר במבנה נתונים הקרוי ערימה כדי לממש את מיון הבחירה בצורה יעילה יותר. האלגוריתם בונה ערימה מהקלט ואז שולף בכל פעם את האיבר שבראש הערימה, שהוא האיבר הגדול ביותר בערימה, אל הפלט. סיבוכיות האלגוריתם היא $O\left(n\log n\right)$. יתרונו לעומת מיון מיזוג הוא שאינו דורש זיכרון נוסף פרט לזיכרון שבו מאוחסן הקלט.
• מיון מהיר (quicksort) הוא אלגוריתם מיון השוואתי אקראי מהיר במיוחד. זהו אלגוריתם רקורסיבי הפועל בשיטת הפרד ומשול. סיבוכיות הזמן הממוצע של האלגוריתם הוא $O\left(n\log n\right)$ פעולות, אך במקרה הגרוע עלול לדרוש $\ O\left(n^{2}\right)$ פעולות.
• מיון מיזוג (mergesort) הוא אלגוריתם מיון רקורסיבי קל למימוש המתבסס על קלות מיזוגם של מערכים ממוינים. סיבוכיות הזמן במקרה הגרוע היא $O\left(n\log n\right)$ פעולות, אך זוהי גם הסיבוכיות במקרה הטוב ביותר. סיבוכיות המקום היא $O\left(n\right)$.
• Shell sort מיון "של" על שמו של הממציא. אלגוריתם ה-Shell Sort פועל בשלבים, בהם הוא ממיין תאי מערך הרחוקים זה מזה מרחק שהולך וקטן בכל שלב, כשהמיון עצמו מתבצע בצורת מיון הכנסה.
• מיון מסרק (comb sort) הוא אלגוריתם מיון שמשפר את מיון בועות. הרעיון הבסיסי הוא להעלים צבים- ערכים קטנים המופיעים לקראת סוף הרשימה, היות שבמיון בועות הללו מאטים מאד את המיון. (ארנבים- ערכים גדולים סביב תחילת הרשימה- לא מהווים בעיה במיון בועות).

מיונים עם הנחות נוספות על הקלט:

• מיון מנייה (counting sort) הוא אלגוריתם למיון מספרים שלמים המתבסס על העובדה שהמספרים נמצאים בטווח חסום כדי לבצע את המיון בזמן מהיר יותר מזה שמסוגלים לו אלגוריתמי המיון מבוססי ההשוואות. בצורה אינטואיטיבית, די למיון לעבור על קבוצת האיברים שרוצים למיין ולמנות את מספר המופעים של כל אחד מהאיברים, ומכאן שמו של האלגוריתם.
• מיון סלים (bucket sort) הוא מיון של קבוצת מספרים ממשיים כאשר ידוע שפיזור האיברים אחיד (קרי, מקיימים התפלגות אחידה).
• מיון בסיס (radix sort) הוא אלגוריתם למיון מספרים, המסתמך על מידע נוסף שאומר שכמות הספרות שבאמצעותן מיוצג כל מספר חסומה על ידי קבוע. (למשל: כמות הספרות של המספר 1234567 היא 7).

במיונים הללו (מנייה, סלים, בסיס) בעזרת מידע נוסף על הקלט סיבוכיות האלגוריתם יורדת אל מתחת לסיבוכיות המינימלית של אלגוריתם מיון מבוסס השוואות עד ל$O\left(n\right)$ במקום $O\left(n\log n\right)$.

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

דוגמה

מיון בועות

מימוש ב-#C למיון בועות (Bubble sort) עבור מערך b:

המחשה: צעדים דיסקרטיים של פעולת מיון בועות על מערך מספרים

for (int i = 0; i < b.Length; i++)
{
   for (int j = i + 1; j < b.Length; j++)
   {
       if (b[i] > b[j])
      {
            t = b[i];
            b[i] = b[j];
            b[j] = t;
      }
   }
}

לקריאה נוספת

• דונלד קנות, Sorting and Searching, כרך 3 בסדרה The Art of Computer Programming.

קישורים חיצוניים

מדיה וקבצים בנושא מיון בוויקישיתוף

• סרטון אנימציה שמסביר את האלגוריתמים מיון מהיר ומיון בועות ומשווה ביניהם
• What different sorting algorithms sound like סרטון אנימציה להמחשת שיטות מיון שונות
• different sorting algorithms סרטון אנימציה נוסף להמחשת שיטות מיון שונות
• מאמר מקיף עם המחשות חזותיות של סוגי המיונים השונים, באתר קוד פרוג'קט