מיון בועות

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Bubble sort animation.gif
מיון_בועות צבע ערוך

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

פרטי האלגוריתם[עריכת קוד מקור | עריכה]

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

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

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