מיון (מדעי המחשב)

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

אלגוריתמי מיון מבוססי השוואות[עריכת קוד מקור | עריכה]

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

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

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


רשימת אלגוריתמי מיון[עריכת קוד מקור | עריכה]

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

  • מיון בועות (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 פועל בשלבים, בהם הוא ממיין תאי מערך הרחוקים זה מזה מרחק שהולך וקטן בכל שלב, כשהמיון עצמו מתבצע בצורת מיון הכנסה.

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

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

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

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


דוגמה[עריכת קוד מקור | עריכה]

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

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.

קישורים חיצוניים[עריכת קוד מקור | עריכה]