מיון בועות

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

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

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

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

פסאודו קוד

procedure bubbleSort( A : list of sortable items ) defined as:
        n := length( A )
        do
                swapped := false
                n := n - 1
                for each i in 1 to n do:
                        if A[ i ] > A[ i + 1 ] then
                                swap( A[ i ], A[ i + 1 ] )
                                swapped := true
                        end if
                end for
        while swapped
end procedure

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

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

צבים וארנבים

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

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

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

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

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