מיון בועות
מתוך ויקיפדיה, האנציקלופדיה החופשית
מיון בועות (באנגלית: Bubble Sort), הידוע גם בכינוי מיון החלפה הוא מיון השוואתי פשוט הפועל בסיבוכיות של 
. המיון קיבל את שמו מהדרך בה מבעבעים אלמנטים במערך.
[עריכה] פרטי האלגוריתם
- לכל
, בצע -
- אם
(כלומר, אם האיבר ה-
וזה שאחריו לא מצויים בסדר הנכון) החלף ביניהם. - חזור על התהליך עד שלא ימצאו שני מספרים עוקבים שאינם לפי הסדר.
- אם
[עריכה] פסאודו קוד
procedure bubbleSort( A : list of sortable items ) defined as:
n := length( A )
do
swapped := false
n := n - 1
for each i in 0 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
[עריכה] ניתוח זמן הריצה
סיבוכיות הזמן של האלגוריתם היא , (כיוון שעבור קבוצה של 
מספרים דרושים עד מעברים על הקבוצה, ויהיה צורך לבצע מעברים במקרה ש-
הוא המספר הקטן ביותר בסדרה) דבר שהופך אותו ללא יעיל עבור נתונים רבים. לעומת זאת, עבור נתונים מעטים מאוד זהו המיון היעיל ביותר בשל פשטותו.
