מיון הכנסה ב-Java

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

מהו מיון הכנסה?

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

• קלט: מערך A עם אלמנטים מספריים לא ממוינים: A[0,1, n, n-2...].
• פלט: מערך המכיל את אותם המספרים אך ממוין במלואו. זה מכונה בדרך כלל B: B[0]B[1]...B[n-1].

ישנן מספר דרכים להשתמש במיון הכנסה - להלן הפופולריות ביותר:

• מיון מספרי (סדר הולך וגדל): [1, 2, 3, 4, 5]
• מיון מספרי (סדר יורד): [5, 4, 3, 2, 1]
• מיון אלפביתי: [a, b, c, d]

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

הבנת Theory of Insertion Sort

לפני שנחקור את הקוד שמאחורי מיון ההוספה, בואו נפרק את האלגוריתם באמצעות שפה לא טכנית. מכיוון שאנו נציג את הקוד למיון בסדר עולה, הגיוני להסביר את האלגוריתם צעד אחר צעד בפוסט זה. שלב 1. איטרציה בין arr[1]והיכן הוא ערך מספרי בדרך כלל פחות מ-10. שלב 2. השווה את האלמנט שבחרת (המכונה ) למספר arr[n]הקודם ברצף באמצעות השיטה . שלב 3. אם כל האלמנטים קטנים מהממשיכים שלהם, חזור על ההשוואה עד שתמצא ערך גדול יותר. שלב 4. החלף ערך גדול יותר בעמדה אחת מעבר לקטן יותר כדי ליצור רצף מסודר. שלב 5. חזור על התהליך עד שתקבל מחרוזת ממוינת של תוויםnkeysort()

מיון מערכים פרימיטיביים

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

1. הכריזו על מערך למיון

בתור התחלה, בואו ניצור מחרוזת ערכים שנציג מאוחר יותר באמצעות Java. כדי להשתמש במיון הכנסה, עליך ליצור מערך. לשם כך, השתמשint[]

int[] arrayA = {10, 14, 20, 30};

2. השתמש ב- sort_arr כדי ליישם את האלגוריתם

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

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. צור לולאה ואיטרטור

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

for(int i=0; i< sort_arr.length; ++i){

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

int j = i;

4. יצירת "while loop"

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

• הערך המוקצה ל-j צריך להיות גדול מ-0
• הערך שהוקצה אליו j-1צריך להיות גדול jמהאינדקס

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

5. מיון המערך

לאחר שתגדיר את לולאת ה-while, ערכי ה- jו j-1יוחלפו עד שאחד או שניהם מהתנאים בלולאת while ייכשלו. באופן דומה, המיון יחזור על עצמו עבור כל ערך בלולאת for עד שתנאי for-לולאה ייכשלו גם כן. כך עובד תהליך מיון ההחדרה בפועל:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

מיון ArrayList

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

1. צור מחלקה חדשה Elementעבור הפריטים השייכים לאוסף.

   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }

2. בתוך אוסף, יש compareTo()שיטה - נשתמש בה כדי להשוות את המזהים של שני אלמנטים.

   public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }

3. החל את האלגוריתם וצור כמה לולאות כדי למיין את האובייקטים ArrayListבמקום להשוות ביניהם.

   public static void insertionSortArrayList(List<element> list) {
       for (int j = 1; j < list.size(); j++) {
           Element current = list.get(j);
           int i = j-1;
           while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
               list.set(i+1, list.get(i));
               i--;
           }
           list.set(i+1, current);
       }
   }

4. אתה יכול להוסיף עוד אלמנטים ArrayListגם, כפי שמוצג להלן:

   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);

5. עכשיו הגיע הזמן למיון:

   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array
   list.forEach(e -> System.out.print(e.getId() + ", "));

6. עכשיו בואו נשווה את הקלט והפלט כדי להבטיח שלא עשינו טעויות. הנה ההשוואה של המחרוזת שבה השתמשנו כדוגמה.

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

בעיות תרגול מיון הכנסה

כעת, לאחר שהבנתם את אלגוריתם המיון הזה, הגיע הזמן להעמיד את הכישורים התיאורטיים והמעשיים שלכם למבחן. חידון תיאוריה מס' 1 אתה מקבל מערך [1, 4, 6, 8] ואתה מוסיף לו אלמנט חדש n = 7. מהו מספר ההשוואות שתצטרך לעשות כדי לקבל רצף ממוין של מספרים? ציין את הערך הסופי של אינדקס n במערך. חידון תיאוריה מס' 2 בראיון עבודה, ראש צוות מבקש ממך להוכיח שהכנסת מיון היא שיטה לא יעילה. בהינתן מחרוזת מספרית של [0, 3, 6, 8, 9], מה צריך להיות סדר רצף הקלט שלך כדי למקסם את זמן הריצה הנדרש למיון? בעיית תרגול מיין את המערך [0, 1, 4, 5, 2, 3, 7, 9, 8] בסדר עולה שלו באמצעות מיון הכנסה עבור Java.

סיכום

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