מיון הכנסה

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

מיון הכנסה (באנגלית: 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.

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