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

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

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

למיון ההכנסה יש יתרונות שונים כגון -

• יישום פשוט
• יעיל עבור מערכי נתונים קטנים
• אדפטיבית, כלומר, זה מתאים למערכות נתונים שכבר ממוינות באופן מהותי.

עכשיו, בואו נראה את האלגוריתם של מיון ההכנסה.

אַלגוֹרִיתְם

השלבים הפשוטים להשגת מיון ההוספה מפורטים כדלקמן -

שלב 1 - אם האלמנט הוא האלמנט הראשון, נניח שהוא כבר ממוין. חזרה 1.

צומת רשימה ב-java

שלב 2 - בחר את האלמנט הבא, ואחסן אותו בנפרד ב-a מַפְתֵחַ.

שלב 3 - עכשיו, השווה את מַפְתֵחַ עם כל הרכיבים במערך הממוין.

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

שלב 5 - הכנס את הערך.

שלב 6 - חזור עד שהמערך ממוין.

עבודה של אלגוריתם מיון הכנסה

כעת, בואו נראה את פעולתו של אלגוריתם מיון ההוספה.

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

תן לרכיבי המערך להיות -

בתחילה, שני האלמנטים הראשונים מושווים במיון הוספה.

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

כעת, עברו לשני האלמנטים הבאים והשוו ביניהם.

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

לעת עתה, למערך הממוין יש רק אלמנט אחד, כלומר 12. לכן, 25 גדול מ-12. לפיכך, המערך הממוין נשאר ממוין לאחר ההחלפה.

כעת, שני אלמנטים במערך הממוין הם 12 ו-25. עברו קדימה לאלמנטים הבאים שהם 31 ו-8.

גם 31 וגם 8 לא ממוינים. אז, החליפו אותם.

לאחר ההחלפה, הרכיבים 25 ו-8 אינם ממוינים.

אז, החליפו אותם.

כעת, רכיבים 12 ו-8 אינם ממוינים.

אז, החליפו גם אותם.

כעת, למערך הממוין יש שלושה פריטים שהם 8, 12 ו-25. עבור לפריטים הבאים שהם 31 ו-32.

לפיכך, הם כבר ממוינים. כעת, המערך הממוין כולל 8, 12, 25 ו-31.

עבור לרכיבים הבאים שהם 32 ו-17.

17 קטן מ-32. אז, החליפו אותם.

החלפה הופכת את 31 ו-17 ללא מיון. אז, החליפו גם אותם.

כעת, החלפה הופכת את 25 ו-17 ללא מיון. אז, בצע שוב החלפה.

כעת, המערך ממוין לחלוטין.

מורכבות מיון ההוספה

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

1. מורכבות זמן

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

2. מורכבות החלל

• מורכבות החלל של מיון ההכנסה היא O(1). הסיבה לכך היא שבמיון ההוספה, נדרש משתנה נוסף להחלפה.

יישום מיון הכנסה

כעת, בואו נראה את תוכניות ההכנסה ממוינות בשפות תכנות שונות.

תכנית: כתוב תוכנית ליישום מיון הכנסה בשפת C.

 #include void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 &amp;&amp; temp <= 17 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting are - 
'); printarr(a, n); insert(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-18.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in python.</p> <pre> def insertionSort(a): # Function to implement insertion sort for i in range(1, len(a)): temp = a[i] # Move the elements greater than temp to one position #ahead from their current position j = i-1 while j &gt;= 0 and temp <a[j] : a[j + 1]="a[j]" j="j-1" def printarr(a): # function to print the array for i in range(len(a)): (a[i], end=" " ) a="[70," 15, 2, 51, 60] print('before sorting elements are - ') printarr(a) insertionsort(a) print('
after < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-19.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C++ language.</p> <pre> #include using namespace std; void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 &amp;&amp; temp <= 2 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) cout << a[i] <<' '; main() a[]="{" 89, 45, 35, 8, 12, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting are - '<<endl; printarr(a, n); insert(a, cout<<'
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-20.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C# language.</p> <pre> using System; class Insertion { static void insert(int[] a) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.Length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 &amp;&amp; temp <= 12 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } static void printarr(int[] a) function print array int i; n="a.Length;" for (i="0;" i < n; i++) console.write(a[i] + ' '); main() int[] a="{" 98, 54, 53, 18, 21, }; console.write('before sorting are - 
'); printarr(a); insert(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-21.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in Java.</p> <pre> public class Insert { void insert(int a[]) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 &amp;&amp; temp <= 22 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[]) function print array int i; n="a.length;" for (i="0;" i < n; i++) system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 92, 50, 5, 20, 11, }; insert i1="new" insert(); system.out.println('
before sorting are - i1.printarr(a); i1.insert(a); system.out.println('

after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-22.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in PHP.</p> <pre> <?php $a = array( 92, 50, 5, 20, 11, 22 ); function printArray($a) { for($i = 0; $i < 6; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>&apos;; printArray($a); for ($i = 1; $i = 0 &amp;&amp; $temp <= $a[$j]) * move the elements greater than temp to one position ahead from their current position* { $a[$j+1]="$a[$j];" $j="$j-1;" } echo ' <br> After sorting array elements are - <br>&apos;; printArray($a); ?&gt; </=></pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-23.webp" alt="Insertion Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm&apos;s complexity, working, and implementation in different programming languages.</p> <hr></=></n;></pre></=></n;></pre></=></n;></pre></a[j]></pre></=></n;>

תְפוּקָה:

אז, זה הכל לגבי המאמר. מקווה שהמאמר יהיה מועיל ואינפורמטיבי עבורך.

מאמר זה לא היה מוגבל רק לאלגוריתם. דנו גם במורכבות האלגוריתם, העבודה והיישום שלו בשפות תכנות שונות.