הטמעת מיון בועות ב-Java

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

מבוא

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

מיון דרך עיני מכונה ועיניים אנושיות

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

בוצע!

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

• השוו שני אלמנטים;
• החלף או העתק אחד מהם;
• עבור לאלמנט הבא;

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

אלגוריתם מיון בועות

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

• אתה עובר לאלמנט אפס של המערך שלנו (האלמנה השחורה);
• השווה את אלמנט האפס (האלמנה השחורה) עם הראשון (האלק);
• אם האלמנט במיקום אפס גבוה יותר, אתה מחליף אותם;
• אחרת, אם האלמנט במיקום אפס קטן יותר, אתה משאיר אותם במקומם;
• עבור למיקום ימינה וחזור על ההשוואה (השווה את האלק עם הקפטן)

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

יישום מיון בועות ב-Java

כדי להדגים כיצד מיון עובד ב-Java, הנה קוד התוכנית:

• יוצר מערך של 5 אלמנטים;
• מעלה לתוכו את עליית הנוקמים;
• מציג את תוכן המערך;
• מיישם מיון בועות;
• מציג מחדש את המערך הממוין.

אתה יכול להציג את הקוד למטה, ואפילו להוריד אותו אל IntelliJ IDE המועדף עליך. זה ינותח להלן:

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

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

• into- שיטת הכנסת אלמנטים למערך;
• printer- מציג את תוכן המערך שורה אחר שורה;

• toSwap- מסדר מחדש אלמנטים במידת הצורך. לשם כך, נעשה שימוש במשתנה זמני dummy, שבו נכתב ערך המספר הראשון, ובמקום המספר הראשון נכתב הערך מהמספר השני. התוכן מהמשתנה הזמני נכתב למספר השני. זוהי טכניקה סטנדרטית להחלפת שני אלמנטים;

  ולבסוף השיטה העיקרית:

• bubbleSorter- שעושה את העבודה העיקרית וממיין את הנתונים המאוחסנים במערך, נציג אותם שוב בנפרד:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

כאן כדאי לשים לב לשני מונים: חיצוני outופנימי in. המונה החיצוניout מתחיל לספור ערכים מסוף המערך ויורד בהדרגה באחד עם כל מעבר חדש. outעם כל מעבר חדש, המשתנה מוזז עוד יותר שמאלה כדי לא להשפיע על הערכים שכבר ממוינים בצד ימין של המערך. המונה הפנימיin מתחיל לספור ערכים מתחילת המערך ועולה בהדרגה באחד בכל מעבר חדש. העלייה inמתרחשת עד שהיא מגיעה out(האלמנט המנותח האחרון במעבר הנוכחי). הלולאה הפנימית inמשווה בין שני תאים סמוכים inו- in+1. אם inמאוחסן מספר גדול יותר מ- in+1, אז השיטה נקראת toSwap, אשר מחליפה את המקומות של שני המספרים הללו.

סיכום

אלגוריתם מיון הבועות הוא אחד האיטיים ביותר. אם המערך מורכב מ-N אלמנטים, אזי יבוצעו השוואות N-1 במעבר הראשון, N-2 בשנייה, לאחר מכן N-3 וכו'. כלומר, המספר הכולל של מעברים יבוצע: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 לפיכך, בעת המיון, האלגוריתם מבצע השוואות של בערך 0.5x(N ^2). עבור N = 5, מספר ההשוואות יהיה כ-10, עבור N = 10 מספר ההשוואות יגדל ל-45. כך, ככל שמספר האלמנטים גדל, מורכבות המיון עולה משמעותית: מהירות האלגוריתם מושפעת לא רק ממספר המעברים, אלא גם ממספר התמורות שצריך לבצע. עבור נתונים אקראיים, מספר התמורות הוא ממוצע (N^2) / 4, שזה בערך חצי ממספר המעברים. עם זאת, במקרה הגרוע, מספר התמורות יכול להיות גם N^2 / 2 - זה המקרה אם הנתונים ממוינים בתחילה בסדר הפוך. למרות העובדה שמדובר באלגוריתם מיון איטי למדי, די חשוב לדעת ולהבין כיצד הוא עובד, וכאמור, הוא מהווה בסיס לאלגוריתם מורכבים יותר. Jgd!