מיון בועות

מיון בועות (באנגלית: Bubble Sort), הידוע גם בכינוי מיון החלפה, הוא מיון השוואתי פשוט הפועל בסיבוכיות של $O(n^{2})$.

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

שם

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

במאמרים משנות ה-50 של המאה ה-20 האלגוריתם מוזכר בשם sorting by exchange (מיון באמצעות חילוף), והאזכור הראשון לשם bubble sort הוא ע״י קנת׳ אייברסון בשנת 1962. במאמרים משנות ה-60 מופיעים גם השמות shuttle sort (מיון מעבורת), push-down sort (מיון דחיפה למטה) וכן sorting by repeated comparison and exchanging (מיון באמצעות השוואה וחילוף חוזרים).

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

קיימות מספר גרסאות לאלגוריתם עם תוספות לצורך ייעול.

הגרסה הפשוטה ביותר ללא ייעול:

1. בצע $n-1$ פעמים:
   1. עבור כל $i$ עולה מ-$1$ עד $n-1$:
      1. אם $a_{i}>a_{i+1}$ (כלומר, אם האיבר ה-$i$ וזה שאחריו לא מצויים בסדר הנכון):
         1. החלף ביניהם.

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

1. עבור כל $j$ יורד מ-$n-1$ עד $0$:
   1. עבור כל $i$ עולה מ-$1$ עד $j$:
      1. אם $a_{i}>a_{i+1}$ (כלומר, אם האיבר ה-$i$ וזה שאחריו לא מצויים בסדר הנכון):
         1. החלף ביניהם.

ייעול נוסף באמצעות הכרזת המערך כממוין ברגע שמעבר מסוים לא ביצע אף חילוף:

1. עבור כל $j$ יורד מ-$n-1$ עד $0$:
   1. עבור כל $i$ עולה מ-$1$ עד $j$:
      1. אם $a_{i}>a_{i+1}$ (כלומר, אם האיבר ה-$i$ וזה שאחריו לא מצויים בסדר הנכון):
         1. החלף ביניהם.
   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;
	}
}

מימוש ב-C עם מימוש של פונקציית החלפה:

#include <stdio.h>
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void bubbleSort(int arr[], int n) {
    int i, j;
    int swapped;
    for (i = 0; i < n - 1; i++) {
        swapped = 0;
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = 1;
            }
        }
        if (swapped == 0)
            break;
    }
}

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

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

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

סיבוכיות הזמן של האלגוריתם היא $O(n^{2})$, כיוון שעבור מערך של $n$ מספרים דרושים עד $n$ מעברים על המערך עם מספר יורד של פעולות השוואה בכל מעבר: $n$ השוואות במעבר הראשון, $n-1$ השוואות במעבר השני, וכן הלאה. המקרה הגרוע ביותר הוא כאשר $a_{n}$ הוא האיבר המינימלי. היות שאיברים יכולים לבעבע אחורה רק מקום אחד בכל מעבר על המערך, יש צורך ב-$n$ מעברים על המערך, כלומר $n^{2}/2$ השוואות, על מנת להביא את $a_{n}$ למקום הראשון.

סיבוכיות המקום היא $O(1)$, שכן לא נדרש מקום אחסון למעט מצביעים ומשתנה זמני.

צבים וארנבים

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

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

יתרונות

כאשר הקלט ארוך, מיון בועות איננו יעיל לעומת אלגוריתמי מיון אחרים, הפועלים בסיבוכיות $\Theta (n\log n)$, כגון מיון מהיר ומיון ערימה. עם זאת, יש לו מספר יתרונות:

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

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

מערכים כמעט ממוינים: אם המערך ממוין חלקית או כמעט ממוין, מיון בועות עשוי להיות יעיל יותר מאלגוריתמים אחרים, כי האלגוריתם יסיים את המיון בפחות מ-$n$ מעברים על המערך.

ביקורת

על אף שמיון בועות הוא המיון בעל סיבוכיות $\Theta (n^{2})$ המצוטט ביותר ברשת, יש המבקרים את השימוש בו כחומר לימודי מכיוון שהוא רחוק משיטות העבודה המומלצות. מיון בועות אינו קל יותר למימוש מאלגוריתמי מיון אחרים והביצועים שלו פחותים מאלה של מיון הכנסה, הן במקרים של מערך כמעט ממוין והן במקרים אחרים.

אם אתה יודע מה זה מיון בועות, מחק אותו מהמוח שלך; אם אתה לא יודע, הקפד לא לגלות!

המקור באנגלית

If you know what bubble sort is, wipe it from your mind; if you don’t know, make a point of never finding out!

— 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

קישורים חיצוניים

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

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