מיון הכנסה

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

אנימציה המסבירה כיצד פועל מיון הכנסה

זמן הריצה הממוצע של האלגוריתם הוא $\theta \left(n^{2}\right)$ פעולות (בדומה למיון בועות).

תיאור האלגוריתם

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

דוגמה לקוד דמה עבור מערך המתחיל באינדקס 0:

 for j ←1 to length(A)-1
     key ← A[ j ]
     > A[ j ] is added in the sorted sequence A[0, .. j-1]
     i ← j - 1
     while i >= 0 and A [ i ] > key
         A[ i + 1 ] ← A[ i ]
         i ← i - 1
     A [i + 1] ← key

דוגמה למימוש עבור מערך מכל סוג נתונים שהוא (בשפת C):

void insert_sort (void *arr, size_t num, size_t size, int (*cmp) (const void *, const void *))
{
    void *key;
    size_t j;
    int i;
    
    key = malloc (size);
    
    for (j = 1 ; j < num ; j++)
    {
        memcpy (key, (void *) ((char *) arr + size * j), size);
        
        i = j - 1;
        while (i >= 0 && cmp ((char *) arr + size * i, key))
        {
            memcpy ((char *) arr + size * (i + 1), (char *) arr + size * i, size);
            memcpy ((char *) arr + size * i, key, size);
            
            i--;
        }
    }
    
    free (key);
}

חישוב סיבוכיות

אם נגדיר כשלב ראשון את ההסתכלות על מקומות 1 ו 2 (או למען הקיצור עד מקום 2 במערך), אז שלב שני יהיה הסתכלות עד מקום 3, שלב שלישי הסתכלות עד מקום 4, וכן הלאה, ולכן, בסך הכל יהיו n-1 שלבים כדי למיין מערך שמכיל n מקומות. לכן, במקרה הכי גרוע, בשלב הראשון תבוצע פעולת החלפה אחת (שמורכבת ממספר סופי של פעולות) (כלומר, החלפה בין המקום הראשון והמקום השני), בשלב השני יבוצעו 2 פעולות החלפה (שמורכבות ממספר סופי של פעולות) (כלומר החלפה בין המקום השלישי למקום השני ואז בין המקום השני למקום הראשון), בשלב השלישי 3 פעולות החלפה וכן הלאה, עד שבשלב ה n-1 )לפי ההגדרה הוא השלב האחרון במיון( יבוצעו n-1 פעולות החלפה, ולכן מספר הפעולות חסום למעשה על ידי $1+2+3...+n-1$ פעולות החלפה (כאשר כל פעולת החלפה מכילה עד מספר קבוע של פעולות) השווה ל-$n(n-1)/2$ פעולות (לפי הגדרת סכום סדרה חשבונית). ומכאן שסיבוכיות זמן הריצה (במקרה הגרוע) שייכת ל-$O(n^{2})$. סיבוכיות הזיכרון היא $O(1)$ בגלל שמשתמשים במספר קבוע של משתנים נוספים כדי לבצע את המיון.

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

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

• מיון הכנסה בQueue