שקול את המספרים הבאים:
50 60 30 10 80 70 20 40
אם רשימה זו ממוינת בסדר עולה, היא תהיה:
10 20 30 40 50 60 70 80
אם זה ממוין בסדר יורד, זה יהיה:
80 70 60 50 40 30 20 10
מיון הכנסה הוא אלגוריתם מיון המשמש למיון הרשימה בסדר עולה או בסדר יורד. מאמר זה עוסק רק במיון בסדר עולה. מיון בסדר יורד פועל לפי אותו היגיון שניתן במסמך זה. מטרת מאמר זה היא להסביר את מיון ההחדרה. התכנות נעשה בדוגמה הבאה ב-C. מיון ההכנסה מוסבר כאן באמצעות מערך אחד.
אלגוריתם למיון הכנסה
ניתנת רשימה לא ממוינת. המטרה היא למיין את הרשימה בסדר עולה באמצעות אותה רשימה. מיון מערך לא ממוין באמצעות אותו מערך אמור להיות מיון במקום. כאן נעשה שימוש באינדקס מבוסס אפס. השלבים הם כדלקמן:
-
- הרשימה נסרקת מההתחלה.
- בזמן שהסריקה נמשכת, כל מספר קטן מקודמו מוחלף עם קודמו.
- ההחלפה הזו נמשכת לאורך הרשימה, עד שלא ניתן עוד להחליף.
- כאשר הסריקה מגיעה לסיומה, המיון הושלם.
איור מיון הכנסה
כאשר מתמודדים עם מורכבות הזמן, זה המקרה הגרוע ביותר שנלקח בדרך כלל בחשבון. הסידור הגרוע ביותר עבור הרשימה הקודמת הוא:
80 70 60 50 40 30 20 10
ישנם שמונה אלמנטים עם אינדקסים מאפס עד 7.
באינדקס אפס, הסריקה עוברת ל-80. זוהי תנועה אחת. התנועה האחת הזו היא מבצע. יש בסך הכל פעולה אחת עד כה (תנועה אחת, ללא השוואה וללא החלפה). התוצאה היא:
| 80 70 60 50 40 30 20 10
במדד הראשון, יש תנועה ל-70. 70 לעומת 80. 70 ו-80 מוחלפים. תנועה אחת היא פעולה אחת. השוואה אחת היא גם פעולה אחת. החלפה אחת היא גם פעולה אחת. חלק זה מספק שלוש פעולות. יש בסך הכל ארבע פעולות עד כה (1 + 3 = 4). התוצאה היא כדלקמן:
70 | 80 60 50 40 30 20 10
במדד שני, יש תנועה ל-60. 60 מושווים ל-80, ואז 60 ו-80 מוחלפים. 60 מושווה ל-70, ואז 60 ו-70 מוחלפים. תנועה אחת היא פעולה אחת. שתי השוואות הן שתי פעולות. שתי החלפות הן שתי פעולות. חלק זה מספק חמש פעולות. יש בסך הכל תשע פעולות עד כה (4 + 5 = 9). התוצאה היא כדלקמן:
60 70 | 80 50 40 30 20 10
במדד שלוש, יש תנועה ל-50. 50 מושווה ל-80, ואז 50 ו-80 מוחלפים. 50 מושווה ל-70, ואז 50 ו-70 מוחלפים. 50 מושווה ל-60, ואז 50 ו-60 מוחלפים. תנועה אחת היא פעולה אחת. שלוש השוואות הן שלוש פעולות. שלוש החלפות הן שלוש פעולות. סעיף זה מספק שבע פעולות. יש בסך הכל שש עשרה ניתוחים עד כה (9 + 7 = 16). התוצאה היא כדלקמן:
50 60 70 | 80 40 30 20 10
במדד ארבע, יש תנועה ל-40. 40 מושווה ל-80, ואז 40 ו-80 מוחלפים. 40 מושווה ל-70, ואז 40 ו-70 מוחלפים. 40 מושווה ל-60, ואז 40 ו-60 מוחלפים. 40 מושווה ל-50, ואז 40 ו-50 מוחלפים. תנועה אחת היא פעולה אחת. ארבע השוואות הן ארבע פעולות. ארבע החלפות הן ארבע פעולות. סעיף זה מספק תשע פעולות. יש בסך הכל עשרים וחמש ניתוחים עד כה (16 + 9 = 25). התוצאה היא כדלקמן:
40 50 60 70 80 | 30 20 10
במדד חמש, יש תנועה ל-30. 30 מושווה ל-80, ואז 30 ו-80 מוחלפים. 30 מושווה ל-70, ואז 30 ו-70 מוחלפים. 30 מושווה ל-60, ואז 30 ו-60 מוחלפים. 30 מושווה ל-50, ואז 30 ו-50 מוחלפים. 30 מושווה ל-40, ואז 30 ו-40 מוחלפים. תנועה אחת היא פעולה אחת. חמש השוואות הן חמש פעולות. חמש החלפות הן חמש פעולות. חלק זה מספק אחת עשרה פעולות. יש בסך הכל שלושים ושש פעולות עד כה (25 + 11 = 36). התוצאה היא כדלקמן:
30 40 50 60 70 80 | 20 10
במדד שש, יש תנועה ל-20. 20 מושווים ל-80, ואז 20 ו-80 מוחלפים. 20 מושווה ל-70, ואז 20 ו-70 מוחלפים. 20 מושווה ל-60, ואז 20 ו-60 מוחלפים. 20 מושווה ל-50, ואז 20 ו-50 מוחלפים. 20 מושווה ל-40, ואז 20 ו-40 מוחלפים. 20 מושווה ל-30, ואז 20 ו-30 מוחלפים. תנועה אחת היא פעולה אחת. שש השוואות הן שש פעולות. שש החלפות הן שש פעולות. סעיף זה מספק שלוש עשרה פעולות. יש בסך הכל ארבעים ותשע פעולות עד כה (36 + 13 = 49). התוצאה היא כדלקמן:
20 30 40 50 60 70 80 | 10
במדד שבע, יש תנועה ל-10. 10 מושווה ל-80, ואז 10 ו-80 מוחלפים. 10 מושווה ל-70, ואז 10 ו-70 מוחלפים. 10 מושווה ל-60, ואז 10 ו-60 מוחלפים. 10 מושווה ל-50, ואז 10 ו-50 מוחלפים. 10 מושווה ל-30, ואז 10 ו-40 מוחלפים. 10 מושווה ל-30, ואז 10 ו-30 מוחלפים. 10 מושווה ל-20, ואז 10 ו-20 מוחלפים. תנועה אחת היא פעולה אחת. שבע השוואות הן שבע פעולות. שבעה החלפות הן שבע פעולות. סעיף זה מספק חמש עשרה פעולות. יש בסך הכל שישים וארבע פעולות עד כה (49 + 15 = 64). התוצאה היא כדלקמן:
10 20 30 40 50 60 70 80 10 |
העבודה הסתיימה! היו מעורבים 64 מבצעים.
64 = 8 x 8 = 8 שתיים
מורכבות זמן עבור מיון הכנסה
אם יש n אלמנטים למיין עם Insertion Sort, המספר המרבי של פעולות אפשריות יהיה n2, כפי שהוכח קודם לכן. המורכבות של זמן מיון ההכנסה היא:
עַל שתיים )
זה משתמש בסימון Big-O. סימון Big-O מתחיל באותיות גדולות ב-O, ואחריו סוגריים. בתוך הסוגריים נמצא הביטוי למספר המקסימלי האפשרי של פעולות.
קידוד ב-C
ממש בתחילת הסריקה, האלמנט הראשון לא יכול לשנות את מיקומו. התוכנית היא בעיקרה הבאה:
#includeהכנסה ריקה מיון ( int A [ ] , אינט נ ) {
ל ( int אני = 0 ; אני < נ; i++ ) {
int j = i;
בזמן ( א [ י ] < א [ j- 1 ] && j- 1 > = 0 ) {
int temp = A [ י ] ; א [ י ] = א [ j- 1 ] ; א [ j- 1 ] = טמפ'; // לְהַחלִיף
j--;
}
}
}
הגדרת הפונקציה insertionSort() משתמשת באלגוריתם כמתואר. שימו לב לתנאים עבור לולאת ה-while. פונקציה עיקרית C מתאימה לתוכנית זו היא:
{
int n = 8 ;
int A [ ] = { חמישים , 60 , 30 , 10 , 80 , 70 , עשרים , 40 } ;
insertionSort ( א, נ ) ;
ל ( int אני = 0 ; אני < n; i++ ) {
printf ( '%אני ' , א [ אני ] ) ;
}
printf ( ' \n ' ) ;
לַחֲזוֹר 0 ;
}
סיכום
מורכבות הזמן עבור מיון הכנסה נתונה כ:
עַל שתיים )
הקורא אולי שמע על מורכבות זמן במקרה גרוע, מורכבות זמן ממוצעת ומורכבות זמן במקרה הטוב ביותר. וריאציות אלו של מורכבות זמן מיון ההכנסה נדונות במאמר הבא באתר שלנו.