מיון הכנסה (Insertion Sort)

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

עקרון האלגוריתם

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

 

הקוד של האלגוריתם בפסאודו קוד

INSERTION-SORT (A)
for (j <- 2 to length[A]) do
    key <- A[j]
    i <- j-1
    while (i > 0 and A[i] > key) do
        A[i + 1] <- A[i]
        i <- i -1
    A[i + 1] <- key
Insertion Sort Animation

להלן אנימציה (בצד שמאל) של האלגוריתם בפעולה על מערך, כשהמערך ההתחלתי הוא {4 ,2, 7, 8, 1, 3, 5, 6}, והמערך המתקבל בסוף הוא {8, 7, 6, 5, 4, 3, 2, 1}.

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

אלגוריתם זה (מיון הכנסה) די דומה לאלגוריתם מיון בחירה שהצגנו קודם לכן, ובשניהם יש לולאה מקוננת, אך הלולאה השניה באלגוריתם זה הינה לולאת while (ולא for), ז”א שבמידה שזיהינו שהאיבר שאנו בודקים כעת קטן מהאיבר במקום כלשהו (כמו בדוגמא עם האיבר בעל הערך 3) נעצור את הבדיקה ונכניס אותו למקומו הנכון (בכך נחסוך את שאר הבדיקות).

 

הרצה של הקוד לשם המחשה של השלבים המתבצעים

  1. נקבל מערך: { 5, 7, 1, 3 }.
  2. שורה 2: נתחיל לולאת for, מהתא השני עד לתא האחרון ונבצע:
    • שורה 3: נכניס את הערך שבתא מס’ j (כרגע 1) למשתנה בשם key.
    • שורה 4: נכניס למשתנה בשם i את המס’ j-1 (כרגע זה יהיה 1).
    • שורה 5: ניכנס ללולאת while, בתנאי שכל עוד i גדול מ 0 וגם הערך בתא i גדול מהערך במשתנה key, ונבצע:
    • שורה 6: נכניס את הערך בתא i לתא שאחריו ( i+1 ).
    • שורה 7: נחסר את i ב 1 (נלך אחורה במערך, כדי לבדוק את האיבר שלפניו באיטרציה הבאה, עד שנגיע ל i=0 או שהערך בתא i גדול מהערך במשתנה key - תנאי הלולאה). * במעבר הראשון, נראה כי 3 גדול מ 1, ולכן המערך יראה כך: { 5, 7, 3, 3 }. * שורה 8: נשים את המשתנה key במקום הערך שבתא i+1 (ובעצם נקבל תת מערך ממוין בצד השמאלי של המערך).
  3. כרגע המערך יראה כך: { 5, 7, 3, 1 }.
  4. נגיע שוב לשורה 2: הפעם i יעלה ל 3 ונבצע:
    • שורה 3: נכניס את הערך שבתא מס’ j (כרגע 7) למשתנה בשם key.
    • שורה 4: נכניס למשתנה בשם i את המס’ j-1 (כרגע זה יהיה 2).
    • שורה 5: לא ניכנס ללולאת while, כי i גדול מ 0 אבל הערך בתא i (שהוא 3), לאגדול מהערך במשתנה key (שהוא 7).
    • שורה 6: נשים את המשתנה key במקום הערך שבתא i+1 (במקום עצמו).
  5. כרגע המערך יראה כך: { 5, 7, 3, 1 }.
  6. נגיע שוב לשורה 2: הפעם i יעלה ל 4 ונבצע:
    • שורה 3: נכניס את הערך שבתא מס’ j (כרגע 5) למשתנה בשם key.
    • שורה 4: נכניס למשתנה בשם i את המס’ j-1 (כרגע זה יהיה 3).
    • שורה 5: ניכנס ללולאת while, בתנאי שכל עוד i גדול מ 0 (i שווה ל 3), וגם הערך בתא i (שהוא 7) גדול מהערך במשתנה key (שהוא 5), ונבצע:
    • שורה 6: נכניס את הערך בתא i לתא שאחריו ( i+1 ).
    • שורה 7: נחסר את i ב 1 (נלך אחורה במערך, כדי לבדוק את האיבר שלפניו באיטרציה הבאה, נראה ש i שהוא 3 לא גדול מ key שהוא 5 ולכן נצא מהלולאה). * שורה 8: נשים את המשתנה key במקום הערך שבתא i+1 (במקום עצמו).
  7. כרגע המערך יראה כך: { 7, 5, 3, 1 }.
  8. נגיע שוב לשורה 1: הפעם i יעלה ל 5, אך לא ניכנס שוב ללולאה, מכיוון ש n (מס’ התאים במערך) הוא 4, ולפי תנאי הלולאה אנו נכנסים אליה רק כאשר i קטן שווה ל n (שבמקרה שלנו, זה בעצם 4).

סיבוכיות זמן ריצה: (O(n^2 (בהשוואה למיון בחירה, בגלל לולאת ה While, כנראה שנחסוך באלגוריתם זה כמה בדיקות. אך אין אנו יכולים להתחייב כי זמן הריצה שלו יהיה קטן יותר, מכיון שזה תלוי בקלט אותו נקבל, ולכן זמן הריצה במקרה הגרוע נשאר אותו הדבר כמו במיון בחירה).
סיבוכיות מקום: (O(1.

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