אלגוריתמי סינון

הסידור שהאיטיות בו מכוונת

• לכל ספרייה רצינית יש אלגוריתם סידור שאין בתיק נסיעה מבקשים ממך לכתוב. סידור בועות וסידור הכנסה הם שניהם $O(n^2)$, ושניהם מובסים על ידי כל סידור סביר ברשימה גדולה.
• הם מופיעים בתיק anyway, ולטובת סיבה טובה: הם קצרים מספיק כדי לעקוב אחריהם ידנית, ועקוב אחרי אחד מהם הוא הדרך ללמוד מה סידור בעצם עושה למערך.
• יש גם טענה אמיתית לסידור הכנסה. ברשימה קטנה או כזו שכבר מסודרת כמעט לחלוטין, זו באמת התוכנית המהירה ביותר שקיימת, וספריות אמיתיות מעבירות אליה בדיוק עבור המקרים האלה.
• שיעור זה עוסק בסידור בועות ובסידור הכנסה: האלגוריתמים, התנהגותם, ואיפה כל אחד מהם מנצח.

בועות (Bubble sort)

FOR pass ← 1 TO n - 1
    swapped ← FALSE
    FOR i ← 1 TO n - pass
        IF A[i] > A[i + 1] THEN
            swap A[i], A[i + 1]
            swapped ← TRUE
        ENDIF
    NEXT i
    IF NOT swapped THEN      // already sorted
        EXIT FOR
    ENDIF
NEXT pass

• בכל מעבר משווים זוגות סמוכים ומחליפים כל זוג שיצא מהסדר, כך שהערך הגדול שנותר "מבועבל" לקצה.
• לאחר מעבר $k$ ה$k$ אלמנטים האחרונים הם סופיים, ולכן הלולאה הפנימית עצומה ב$n - \text{pass}$.
• הדגל swapped מאפשר עצירה מוקדמת: אם במעבר שלם לא נעשתה החלפה, הרשימה מסודרת.

סידור הכנסה

FOR i ← 2 TO n
    key ← A[i]
    j ← i - 1
    WHILE j >= 1 AND A[j] > key DO
        A[j + 1] ← A[j]                 // shift right
        j ← j - 1
    ENDWHILE
    A[j + 1] ← key                      // drop it in
NEXT i

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

החלק השמאלי מסודר, החלק הימני אינו נוגע בו, הגבול זז ימינה

דוגמה פתורה: עקוב מעבר אחד

ביצועים

• בתוך המערך (in place) אומר שהוא דורש רק כמות קבועה של זיכרון נוסף, ומסדר בתוך המערך עצמו. יציב אומר ששתי ערכים שווים שומרים על הסדר היחסי המקורי שלהם, מה שחשוב כאשר רשימה already מסודרת לפי שדה אחר.
• שניהם מגיעים ל$O(n)$ על נתונים שכבר מסודרים, אך רק אם לסידור בועות יש את הדגל swapped. ללאו, הוא מבצע תמיד את כל המעברים.

דוגמה פתורה: איזה סידור, ולמה

מדוע מעבר אחד אינו מספיק

• שתי השיטות מבצעות מעברים חוזרים, והמבחן מבדיל ביניהן לפי מה שמעבר אחד משיג ומתי הן נעצרות.
• במעבר של מינון בועות (bubble sort) משווים זוגות שכנים ומחליפים אותם, כך שמעבר אחד מוביל את האלמנט הגדול הנותר למקומו הסופי. המינון כולו דורש $n - 1$ מעברים.
• במעבר של מינון הכנסה (insertion sort) לוקחים את האלמנט הבא ומזיזים אותו החוצה לתוך החלק שכבר ממוין, כך שע לאחר $k$ מעברים, ה-$k$ אלמנטים הראשונים ממונים בינם עצמם אך עדיין לא במיקום הסופי שלהם.
• מינון בועות ניתן לשפר באמצעות סימן: אם במעבר לא נעשה שום החלפה, הרשימה כבר ממוינת והאלגוריתם נעצר. בנתונים הקרובים למיון זה הופך אותו למעבר אחד.
• ללא הסימן, שתי השיטות הן $n^2$ במקרה הרע, ולכן הן בחירה גרועה לקובץ גדול, ולכן השאלות במבחן עוסקות בקבצים קטנים.

סימונים נופלים מהיד

הבנתך מושלמת