מיון בועות

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
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 מעברים על המערך.

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