מיון הכנסה

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

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

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

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

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

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

 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+3...+n-1 שלבים (כאשר כל שלב מכיל עד מספר קבוע של פעולות) השווה ל-n(n-1)/2 פעולות. ומכאן שסיבוכיות זמן הריצה (במקרה הגרוע) שייכת ל-(o)n^2. סיבוכיות הזיכרון היא (o)1.