מיון בועות

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

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

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$ מעברים על המערך.

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

• סרטון אנימציה שמסביר את האלגוריתמים מיון מהיר ומיון בועות ומשווה ביניהם