מיון הכנסה

מיון הכנסה הוא גם סוג של שיטת מיון, שגם סיבוכיות הזמן שלה היא O(n²), אך היא מעט יעילה יותר ממיון בועות.

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

אנחנו חוזרים על התהליך עד שכל האיברים ממוינים.

1. נניח שיש לנו מערך {8,4,1,5}. נחשיב את האיבר הראשון כממויין ואת כל השאר כלא ממוינים. בהתחלה, האיבר באינדקס 0 נחשב לממויין.

2. צרו משתנה זמני ושמרו בו את האיבר ה־(i) (כאן הוא 4). השוו את המשתנה הזמני למערך הממויין הנוכחי, שמכיל כרגע את 8. מכיוון ש־4<8, הזיזו את המערך הממויין ימינה עד ש־4 יגיע למיקום הנכון שלו. במקרה הזה, יש להזיז את 8 פעם אחת. כעת אורך המערך הממויין הוא 2.

3. חזרו על התהליך עד שהמערך כולו ממויין.

for(int i=1;i<n;i++){           //מתחילים מהאיבר הראשון, כי אנו מניחים שהאיבר ה-0 כבר ממוין
    int temp=arr[i];
    
    int j=i-1;                  //כדי לבדוק את כל האיברים שמשמאלו 
    
    while(arr[j]>temp && j>=0){ //מזיזים את האיברים כל עוד הם גדולים מ-temp, עד לאיבר הראשון
      arr[j+1]=arr[j];          //מזיזים את האיבר צעד אחד ימינה
      j--;                      
    }
    
    arr[j+1]=temp;              //מציבים את temp במיקום הנכון
  
}

להמחשת מיון הכנסה

המחשה חזותית של מיון הכנסה