מהו מיון הכנסה ב-C?
שיטת המיון הנקראת insertion sort מתאימה לכל אלמנט בודד עם אלה סמוכים כשהיא חוזרת על פני מערך. אלמנט קטן יותר מזה שלפני הכנסתו למערך המשנה הממוין במיקום המתאים.
להמחשה נוספת, הדגמתי דוגמה שבה שקלתי מערך של ארבעה אלמנטים במערך כגון arr[]= {5, 4, 60, 9} ואנחנו רוצים למיין את האלמנט הזה בסדר עולה בעזרת מיון הוספה. האינטראקציות הבאות מסבירות את הריצה היבשה המלאה של סוג ההחדרה:
איטרציה 1
| 5 | 4 | 60 | 9 |
יש לנו מערך כמו arr[5, 4, 60, 9] כעת, באיטרציה הראשונה של מיון ההכנסה אנו משווים תחילה את שני האלמנטים הראשונים כגון 5 ו-4, כפי שה-arr[5] הוא > arr[4] כך אנחנו מחליפים אותם כדי למיין את המערך בסדר עולה. כעת, המערך יהיה:
| 4 | 5 | 60 | 9 |
איטרציה 2
| 4 | 5 | 60 | 9 |
באיטרציה השנייה, אנו משווים את שני האלמנטים הבאים, כגון arr[5] עם arr[60].
כמו arr[5] < arr[60] כך ההחלפה לא מתרחשת מכיוון שהיא כבר ממוינת בסדר עולה. כעת, המערך הופך ל:
| 4 | 5 | 60 | 9 |
איטרציה 3
| 4 | 5 | 60 | 9 |
כמו באיטרציה השלישית, אנו מתאימים את האלמנט השלישי והרביעי כמו arr[60] עם arr[9].
כעת, אנו רואים שה-arr[60] > arr[9] כך שההחלפה מתרחשת, ואז המערך ימיין בסדר עולה.
| 4 | 5 | 9 | 60 |
כך פועל מיון הכנסה ב-C הממיין אלמנט מערך בקלות בסדר עולה או יורד.
תרשים זרימה של מיון הכנסה
להלן תרשים הזרימה של האלגוריתם של מיון ההכנסה:
יישום דוגמה של מיון הכנסה ב-C
ראשית, אנו דורשים אוסף של אלמנטים שיש למיין בסדר יורד ועולה כדי לבנות את שיטת מיון ההוספה ב-C. נניח לצורך דוגמה זו שאנו עוסקים במערך של מספרים {5, 4, 60, 9} :
#includeבָּטֵל insertionsort_ascending ( int arr1 [ ] , int נ ) {
int אני , י , שלי_מפתח ;
//for loop משמש לחזרת ערכי i מ-1 ל-i
ל ( אני = 1 ; אני < נ ; אני ++ ) {
שלי_מפתח = arr1 [ אני ] ;
י = אני - 1 ;
בזמן ( י >= 0 && arr1 [ י ] > שלי_מפתח ) {
arr1 [ י + 1 ] = arr1 [ י ] ;
י = י - 1 ;
}
arr1 [ י + 1 ] = שלי_מפתח ;
}
}
בָּטֵל insertionsort_descending ( int arr2 [ ] , int M ) {
int אני , י , שלי_מפתח ;
//לופ אחר עבור לולאה נוצר כדי לחזור על ערכי i מ-1 ל-i
ל ( אני = 1 ; אני < M ; אני ++ ) {
שלי_מפתח = arr2 [ אני ] ;
י = אני - 1 ;
בזמן ( י >= 0 && arr2 [ י ] < שלי_מפתח ) {
arr2 [ י + 1 ] = arr2 [ י ] ;
י = י - 1 ;
}
arr2 [ י + 1 ] = שלי_מפתח ;
}
}
int רָאשִׁי ( ) {
//הכנסה-מיון בסדר יורד
int my_arr [ ] = { 5 , 4 , 60 , 9 } ; //initialize my_arr[] בעל ארבעה ערכים
int M = מידה של ( my_arr ) / מידה של ( my_arr [ 0 ] ) ;
insertionsort_descending ( my_arr , M ) ;
printf ( 'המערך ממוין בסדר יורד:' ) ;
ל ( int אני = 0 ; אני < M ; אני ++ )
printf ( '%d' , my_arr [ אני ] ) ;
printf ( ' \n ' ) ;
//הכנסה-מיון בסדר עולה
int נ = מידה של ( my_arr ) / מידה של ( my_arr [ 0 ] ) ;
insertionsort_ascending ( arr2 , נ ) ;
printf ( 'המערך ממוין בסדר עולה:' ) ;
ל ( int אני = 0 ; אני < נ ; אני ++ )
printf ( '%d' , my_arr [ אני ] ) ;
printf ( ' \n ' ) ;
לַחֲזוֹר 0 ;
}
בקוד זה, שתי שיטות insertionsort_descending() , ו insertionsort_ascending() קח את ערכי המערך של my_arr[] . לאחר מכן הקוד משתמש ב-a עבור לולאה לחזור על האלמנטים של המערך.
אנו קוראים לשתי הפונקציות בפונקציה הראשית לאחר שהן מיינו את המערכים בסדר יורד ועולה. לאחר מכן, לולאות for משמשות להדפסת המערך הממוין.
כאשר אנו מפעילים תוכנית זו, הפלט הצפוי ממוקם להלן:
סיכום
מיון ההכנסה הוא דרך מהירה וקלה למיין מערך ברצף יורד או עולה. עבור מערכי נתונים קטנים, טכניקת מיון זו מתפקדת היטב. כפי שניתן לראות במדריך למעלה, קל ליישם דוגמה של תוכנית C כדי להבין בקלות את מיון ההוספה בסדר יורד וגם בסדר עולה.