מיון בועות
![]() |
||
יש לשכתב ערך זה. ייתכן שהערך מכיל טעויות, או שהניסוח וצורת הכתיבה שלו אינם מתאימים. | |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/83/Bubblesort-edited-color.svg/220px-Bubblesort-edited-color.svg.png)
מיון בועות (באנגלית: 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 הוא לצורכי אופטימיזציה. הוא מציין האם באיטרציה הנוכחית של הלולאה החיצונית בוצע חילוף מקומות אחד לפחות.
ניתוח זמן הריצה
[עריכת קוד מקור | עריכה]![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Bubble_sort_animation.gif/250px-Bubble_sort_animation.gif)
סיבוכיות הזמן של האלגוריתם היא , כיוון שעבור מערך של מספרים דרושים עד מעברים על המערך עם מספר יורד של פעולות השוואה בכל מעבר: השוואות במעבר הראשון, השוואות במעבר השני, וכן הלאה. המקרה הגרוע ביותר הוא כאשר הוא האיבר המינימלי. היות שאיברים יכולים לבעבע אחורה רק מקום אחד בכל מעבר על המערך, יש צורך ב- מעברים על המערך, כלומר השוואות, על מנת להביא את למקום הראשון.
סיבוכיות המקום היא , שכן לא נדרש מקום אחסון למעט מצביעים ומשתנה זמני.
צבים וארנבים
[עריכת קוד מקור | עריכה]המרחק והכיוון אותו האיברים ברשימה צריכים לעבור משפיעים על הביצועים של האלגוריתם בגלל שאיברים זזים לכיוונים שונים במהירויות שונות. איבר שצריך לזוז לעבר סוף הרשימה יזוז מהר בגלל שהוא יוכל להשתתף בהשוואות רציפות. לדוגמה - האיבר הגדול ביותר ינוע כבר במעבר הראשון לסוף הרשימה בגלל שהוא יזוז בכל השוואה, בעוד שהאיבר הקטן ביותר ינוע רק מקום אחד אחורה בכל סיבוב. אם האיבר הקטן ביותר יהיה בסוף הרשימה, ידרשו 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
קישורים חיצוניים
[עריכת קוד מקור | עריכה]אנימציה, כתוביות בעברית, ללא קריינות, סרטון באתר יוטיוב: מיון בועות ומיון מהיר, הסבר והשואה
דומה לקודם, סרטון באתר יוטיוב: אך באיכות גבוהה, כולל קריינות, עם מעט כתוביות, הכל באנגלית.
אלגוריתמי מיון | ||
---|---|---|
רקע תאורטי | תורת הסיבוכיות • סימון אסימפטוטי • סדר מלא • רשימה • אלגוריתם תוך-מקומי • מיון יציב | |
אלגוריתמי מיון | אקראי • בועות • בחירה • בסיס • הכנסה • מהיר • מיזוג • מנייה • מסרק • סלים • ערימה • רשת מיון • שייקר • של | |
שונות | מיון טופולוגי • בעיית סידור הפנקייקים של גודמן |
הערות שוליים
[עריכת קוד מקור | עריכה]- ^ דוד הראל, אלגוריתמיקה : יסודות מדעי המחשב, רעננה: האוניברסיטה הפתוחה, 2001, עמ' 23
- ^ 1 2 Owen Astrachan, Bubble sort: an archaeological algorithmic analysis, SIGCSE Bull. 35, 2003-01-11, עמ' 1–5 doi: 10.1145/792548.611918