Loading AI tools
מוויקיפדיה, האנציקלופדיה החופשית
מיון בועות (באנגלית: Bubble Sort), הידוע גם בכינוי מיון החלפה, הוא מיון השוואתי פשוט הפועל בסיבוכיות של .
יש לשכתב ערך זה. ייתכן שהערך מכיל טעויות, או שהניסוח וצורת הכתיבה שלו אינם מתאימים. | |
השם ״מיון בועות״ מקורו בדרך שבה ״מבעבעים״ הפריטים הגדולים, בעת ביצוע האלגוריתם, כלפי מעלה, בעוד הפריטים הקטנים יותר נשארים בתחתית. [1]
במאמרים משנות ה-50 של המאה ה-20 האלגוריתם מוזכר בשם sorting by exchange (מיון באמצעות חילוף), והאזכור הראשון לשם bubble sort הוא ע״י קנת׳ אייברסון בשנת 1962. במאמרים משנות ה-60 מופיעים גם השמות shuttle sort (מיון מעבורת), push-down sort (מיון דחיפה למטה) וכן sorting by repeated comparison and exchanging (מיון באמצעות השוואה וחילוף חוזרים).[2]
קיימות מספר גירסאות לאלגוריתם עם תוספות לצורך ייעול.
הגירסה הפשוטה ביותר ללא ייעול:
ייעול באמצעות סיום כל מעבר בנקודה מוקדמת יותר, מכיוון שבחלק האחרון של המערך כבר אין מה להחליף:
ייעול נוסף באמצעות הכרזת המערך כממוין ברגע שמעבר מסוים לא ביצע אף חילוף:
מימוש ב-#C:
for (int j = array.Length - 1; j > 0; j--)
{
bool swapped = false;
for (int i = 0; i < j; i++)
{
if (array[i] > array[i + 1])
{
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = true;
}
}
if (!swapped)
{
break;
}
}
הדגל swapped הוא לצורכי אופטימיזציה. הוא מציין האם באיטרציה הנוכחית של הלולאה החיצונית בוצע חילוף מקומות אחד לפחות.
סיבוכיות הזמן של האלגוריתם היא , כיוון שעבור מערך של מספרים דרושים עד מעברים על המערך עם מספר יורד של פעולות השוואה בכל מעבר: השוואות במעבר הראשון, השוואות במעבר השני, וכן הלאה. המקרה הגרוע ביותר הוא כאשר הוא האיבר המינימלי. היות שאיברים יכולים לבעבע אחורה רק מקום אחד בכל מעבר על המערך, יש צורך ב- מעברים על המערך, כלומר השוואות, על מנת להביא את למקום הראשון.
סיבוכיות המקום היא , שכן לא נדרש מקום אחסון למעט מצביעים ומשתנה זמני.
המרחק והכיוון אותו האיברים ברשימה צריכים לעבור משפיעים על הביצועים של האלגוריתם בגלל שאיברים זזים לכיוונים שונים במהירויות שונות. איבר שצריך לזוז לעבר סוף הרשימה יזוז מהר בגלל שהוא יוכל להשתתף בהשוואות רציפות. לדוגמה - האיבר הגדול ביותר ינוע כבר במעבר הראשון לסוף הרשימה בגלל שהוא יזוז בכל השוואה, בעוד שהאיבר הקטן ביותר ינוע רק מקום אחד אחורה בכל סיבוב. אם האיבר הקטן ביותר יהיה בסוף הרשימה, ידרשו n-1 מעברים לפני שהרשימה תהיה מסודרת. בשל הבחנה זו מכנים את האיברים האלו "צבים וארנבים" בהתאם לדמויות במשלו של איזופוס הצב והארנב.
כדי להתגבר על הבעיות בזמן ריצה שגורמים ה״צבים״, פותחו וריאנטים של מיון בועות שמתגברים על הבעיה. מיון שייקר עובר על הרשימה לשני הכיוונים, וכך ה״צבים״ זזים מסוף הרשימה להתחלתה. מיון מסרק עובר על הרשימה בפערים קטנים והולכים, וכך נפטר מה״צבים״ די מהר, ועובר לפערים קטנים יותר כדי לסדר את הרשימה.
כאשר הקלט ארוך, מיון בועות איננו יעיל לעומת אלגוריתמי מיון אחרים, הפועלים בסיבוכיות , כגון מיון מהיר ומיון ערימה. עם זאת, יש לו מספר יתרונות:
חינוך ולימוד: מיון בועות משמש לעיתים קרובות ככלי חינוכי להדגמת עקרונות בסיסיים של מיון, תכנות וסיבוכיות. הוא פשוט להבנה ומאפשר ללומדים להבין את הבסיס של אלגוריתמים למיון לפני שהם עוברים לאלגוריתמים מתקדמים יותר.
מערכים קטנים: עבור מערכים קטנים מאוד, ההבדל בזמן הביצוע בין מיון בועות לאלגוריתמים מתקדמים יותר עשוי להיות זניח.
מערכים כמעט ממוינים: אם המערך ממוין חלקית או כמעט ממוין, מיון בועות עשוי להיות יעיל יותר מאלגוריתמים אחרים, כי האלגוריתם יסיים את המיון בפחות מ- מעברים על המערך.
על אף שמיון בועות הוא המיון בעל סיבוכיות המצוטט ביותר ברשת, יש המבקרים את השימוש בו כחומר לימודי מכיוון שהוא רחוק משיטות העבודה המומלצות. מיון בועות אינו קל יותר למימוש מאלגוריתמי מיון אחרים והביצועים שלו פחותים מאלה של מיון הכנסה, הן במקרים של מערך כמעט ממוין והן במקרים אחרים.[2]
אם אתה יודע מה זה מיון בועות, מחק אותו מהמוח שלך; אם אתה לא יודע, הקפד לא לגלות!
— Press, W. H., Flannery, B. P., Teukolsky, S. A., and Vetterling, W. T. Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, 1988