הצעדים של אלגוריתם.

שלב 1 מתוך 6

צעדים מדויקים

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

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

1. השוו שני שכנים.
2. אם השמאלי גבוה יותר, החליפו ביניהם.
3. עברו לזוג הבא, עד סוף השורה. זה מעבר אחד.
4. חזרו על המעברים עד שמעבר שלם עובר בלי אף החלפה.

צפו בבלוקים: סוגר כחול מסמן השוואה של זוג שכבר בסדר, וסוגר כתום מסמן החלפה. הלוחית מתחת למדף סופרת את ההשוואות ואת ההחלפות.

שלב 2 מתוך 6

מעבר אחד

כדי להשוות אלגוריתמים בלי שעון, סופרים את הצעדים הבסיסיים שלהם. במיון, הצעד הבסיסי הוא השוואה של שני בלוקים: כמה השוואות עושה האלגוריתם עד שהשורה ממוינת.

שלב 3 מתוך 6

הגבוה ביותר נסחף לקצה

השם “מיון בועות” בא ממה שקורה בכל מעבר: הבלוק הגבוה ביותר צף ימינה, כמו בועה שעולה במים. צפו במעבר הראשון וחשבו מה הוא מבטיח.

שלב 4 מתוך 6

כל הזוגות

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

הסכום $1 + 2 + \cdots + (n-1)$⁠ הוא מספר הזוגות שאפשר ליצור מ־$n$⁠ בלוקים:

$1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}$$1 + 2 + \cdots + (n-1) =$$\frac{n(n-1)}{2}$⁠

שלב 5 מתוך 6

לספור החלפות

השוואה היא רק חצי מהעבודה; חלק מההשוואות מסתיימות בהחלפה. קראו לשני בלוקים שהגבוה מביניהם עומד משמאל זוג הפוך. החלפה של שני שכנים מתקנת בדיוק את הזוג שלהם, ולא משנה אף זוג אחר.

שלב 6 מתוך 6

לעצור מוקדם

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