מיון בועות

Bubble sort animation.gif

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

מיון בועות צבע ערוך

פרטי האלגוריתםעריכה

  1. לכל  , בצע -
    1. אם   (כלומר, אם האיבר ה-  וזה שאחריו לא מצויים בסדר הנכון) החלף ביניהם.
  2. חזור על התהליך עד שלא ימצאו שני מספרים במיקומים עוקבים שאינם לפי הסדר.

דוגמהעריכה

מימוש ב-#C למיון בועות עבור מערך b:

bool swapped = true;
while(swapped)
{
    swapped = false;
    for (int i = 0; i < b.Length - 1; i++)
    {
       if (b[i] > b[i + 1])
       {
            t = b[i];
            b[i] = b[i + 1];
            b[i + 1] = t;
            swapped = true;
       }
    }
}

ניתוח זמן הריצהעריכה

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

צבים וארנביםעריכה

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

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

קישורים חיצונייםעריכה

  מדיה וקבצים בנושא מיון בועות בוויקישיתוף