אלגוריתמי מיון
הוצג| English | משמעות |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | מיון |
| selection sort/sɪˈlekʃn sɔːt/ | מיון בחירה |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | מיון הכנסה |
| in place/ɪn pleɪs/ | במקום |
סידור דברים
- מינון משנה את סדר האלמנטים לסדר (למשל, מכגון הקטן לגדול).
- הקורס AP מכסה שני סוגים פשוטים: מיון בחירה ו-מיון הכנסה.
- שניהם משתמשים ב-לולאות מושתלות ומחליפים או מזיזים אלמנטים למקומם.
- המיון קודם הוא מה שמאפשר להשתמש בהתאמה בינארית מהירה לאחר מכן.
מיון בחירה
- מצאו את האלמנט הקטן ביותר שנותר והחליפו אותו בקדמת המערך.
- לאחר מכן מצאו את הקטן ביותר מבמה שנותר, החליפו אותו במיקום הבא, וכך הלאה.
- הקדמת המערך גדלה במיון; הסוף מתכווץ ללא מיון.
- החלפה אחת בכל מעבר — אך עדיין סורקים את השאר בכל מעבר.
סידור הכנסה
- לקחו את האלמנט הבא והזיזו אותו אחורה למקומו הנכון בתוך הקדמת המעריכה כבר במיון.
- כמו מיון יד של קלפים: הצביעו כל קלף חדש במקומו.
- אזור המיון גדל באחד בכל מעבר.
- מהיר כאשר הנתונים הם כבר כמעט במיון.
כמה עבודה
- שני סוגי המיון משתמשים בלולאות מושתלות, ולכן מבצעים כ-
n²השוואות במקרה הגרוע. - זה בסדר עבור מערכים קטנים אך איטי עבור גדולים מאוד.
- הם מעריכים בתוך המקום — אין צורך במערך שני.
- הבחינה דורשת ממכם לעקוב אחריהם, לא רק לנקות אותם.
מיון בחירה מחליף את האלמנט הקטן ביותר שנותר לקדמת המערך; מיון הכנסה מזיז כל אלמנט חדש אחורה לתוך החלק המעורכב — אל תבלבו ביניהם. שניהם O(n²) מיון לולאה מושתלת ושניהם מעריכים בתוך המקום. עקבו אחריהם צעד בצעד (הבחינה AP דורשת את מצב המערך לאחר כל מעבר), במקום לזכור שם.
מיון בחירה על [3, 1, 2]:
- מעבר 1: הקטן ביותר הוא
1; החלפה לקדמת המערך →[1, 3, 2]. - מעבר 2: הקטן ביותר מ
[3, 2]הוא2; החלפה →[1, 2, 3]. - מסודר — הקדמה גדלה באחד מהערכים בכל מעבר.
מיון סדר את הערכים. מיון בחירה מחליף שוב ושוב את הערך הנותר הקטן ביותר לקדמת הרשימה; מיון הכנסה מזיז כל ערך חדש אחורה לתוך החלק הממוין. שניהם משתמשים בלולאות תוך-לולאתיות, פועלים במקום (in-place), ומיונים ⟨⟩O(n²). מיון מאפשר ביצוע חיפוש בינארי מהיר לאחר מכן.
מעבר צעד אחר צעד בתהליך המיון
בכל מעבר ממוקם אלמנט נוסס בסדר.
מינון בחירה עובד על ידי...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
מינון בחירה בודק את המינימום והופך אותו לקדימה.
מינון הכנסה עובד על ידי...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
מינון הכנסה מכניס כל אלמנט למיקומו הממוין.
במקרה הגרוע, שתי השיטות מבצעות כ-...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
לולאות מקוננות נותנות O(n²).
גם מינון בחירה וגם מינון הכנסה עובדים באופן מקומי (ללא מערך שני).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
הם מסדרים מחדש את אותו מערך.
סדר את העברות המיון בחירה ב-[3, 1, 2].
Difficulty 3/5 · 200 coins + a small bonus on first completion today
הקדמה גדלה מסודרת, אלמנט אחד בכל עברה.
מיון תחילה הוא שימושי כי מאפשר לך להשתמש... בהמשך
Difficulty 1/5 · 100 coins + a small bonus on first completion today
חיפוש בינארי דורש נתונים מסודרים.