מיון בועות

מתוך ויקיפדיה, האנציקלופדיה החופשית


שגיאות פרמטריות בתבנית:לשכתב

פרמטרי חובה [ נושא ] חסרים

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

מיון בועותאנגלית: 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 מעברים לפני שהרשימה תהיה מסודרת. בשל הבחנה זו מכנים את האיברים האלו "צבים וארנבים" בהתאם לדמויות במשלו של איזופוס הצב והארנב.

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

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