מיון בועות

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

[עריכה] פרטי האלגוריתם

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

[עריכה] ניתוח זמן הריצה

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