מיון הכנסה

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

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

אפשר לתאר את הפעולה כך: עבור כל אינדקס j לוקחים את ה"מפתח" (key) A[j], משווים אותו לאיברים משמאלו ומזזים כל איבר גדול ימינה, ואז שמים את ה"מפתח" במקום הפנוי. זהו רעיון פשוט שעובד היטב על רשימות שכבר כמעט מסודרות.

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

מיון הכנסה הוא דרך פשוטה לסדר רשימה של פריטים. אלגוריתם פירושו סדרת צעדים ברורה לביצוע.

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

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