יציבות

בשיעור הזה נבדוק אם אלגוריתם מיון הבועות הוא יציב.

מהי יציבות?

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

לדוגמה, אם עלינו למיין את המערך — [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] , כאן יש לנו שני 8-ים, המסומנים על ידי 8₁ ו-8₂. לאחר המיון, ניתן לקבל שני מערכים אפשריים — [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] ו-[1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>] . שני המערכים האלה ממוינים, אבל בשני הסדר של שני ה-8-ים שונה, ואילו במערך הראשון הוא זהה לסדר במערך הקלט.

עכשיו נבדוק זאת עבור אלגוריתם מיון הבועות.

מעבר ראשון: [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] -> [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>]

מעבר שני: [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>] -> [2,4,6,1,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

לאחר כל המעברים, הפלט הסופי יהיה: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

שימו לב שסדר ה-8-ים זהה במערך הפלט ובמערך הקלט.

לכן, אלגוריתם מיון הבועות הוא יציב!