תוכן עניינים:
הגדרה - מה המשמעות של מיין בועה?
מיון בועות הוא אלגוריתם מיון שעובד על ידי דריכה חוזרת ונשנית על רשימות שצריך למיין, השוואה בין כל זוג פריטים סמוכים והחלפתם אם הם בסדר הלא נכון. הליך מעבר זה חוזר על עצמו עד שלא נדרשים החלפות, מה שמצביע על כך שהרשימה ממוינת. סוג הבועה מקבל את שמו מכיוון שרכיבים קטנים יותר מבעבעים בראש הרשימה.
מיון בועות נקרא גם מיון טובע או סוג השוואה.
Techopedia מסביר את Bubble Sort
למין הבועה יש מורכבות במקרה הגרוע והממוצע של O (n2), כאשר n הוא מספר הפריטים הממוינים. שלא כמו אלגוריתמי המיון האחרים, מיון בועות מגלה אם הרשימה הממוינת מובנית ביעילות באלגוריתם. ביצועי מיון בועות לפני רשימה ממוינת כבר הם O (n).
מיקום האלמנטים בסוג הבועה ממלא תפקיד חשוב בקביעת הביצועים. אלמנטים גדולים בהתחלה אינם מהווים בעיה מכיוון שהם מוחלפים בקלות. האלמנטים הקטנים לקראת הסוף עוברים להתחלה לאט. ככאלה, אלמנטים אלה נקראים ארנבים וצבים.
ניתן לייעל את אלגוריתם מיון הבועות על ידי הצבת אלמנטים גדולים יותר במצב הסופי. לאחר כל מעבר, כל המרכיבים לאחר החלפה האחרונה ממוינים ואינם צריכים לבדוק שוב, ובכך לדלג על מעקב אחר משתנים שהוחלפו.
