מירימיון מיזוג ומיון מהיר הפרד ומשול
מיון בועות פשוט, אבל ברשימה של מיליון איברים הוא איטי מאוד. מיון מיזוג ומיון מהיר משתמשים ברעיון אחר: מפרקים את הבעיה לבעיות קטנות, פותרים כל אחת, ומחברים. כאן סופרים השוואות ורואים למה זה משתלם. כדאי להכיר קודם את חיפוש ומיון: מבוא ואת רקורסיה.
הרעיון
הפרד ומשול
בעיה גדולה מחלקים לשתי בעיות קטנות מאותו סוג. ממשיכים לחלק עד שהבעיה קטנה כל כך שהיא כבר פתורה: רשימה של איבר אחד תמיד ממוינת. אחר כך מחברים את הפתרונות. זו רקורסיה.
מיון מיזוג
חוצים את הרשימה לשני חצאים, ממיינים כל חצי (באותה שיטה), וממזגים: משווים את הראשון בכל חצי ולוקחים את הקטן. החלוקה קלה, וכל העבודה היא במיזוג.
מיון מהיר
בוחרים איבר ציר (pivot). שמים משמאלו את כל הקטנים ממנו ומימינו את הגדולים. ממיינים כל צד באותה שיטה. כאן כל העבודה היא בחלוקה, והחיבור קל.
מעבדה: מפרקים וממזגים
בחרו סוג רשימה ואורך. למעלה רואים את החלוקה לחצאים (כחול) ואת המיזוג בחזרה (ורוד), שלב אחרי שלב. מתחת: כמה השוואות עשה כל מיון. התוכנית במעקב היא המיזוג האחרון, של שני החצאים הממוינים.
נסו את אלה:
הריצו בעצמכם
אפשר לשנות את הקוד ולהריץ פייתון אמיתי. בפעם הראשונה הטעינה לוקחת כמה שניות. בתיבה יש את שלושת המיונים עם מוני השוואות, על הרשימה מהמחוונים.
טעויות שכולם עושים
שוכחים את מקרה הבסיס
בלי תנאי עצירה הרקורסיה ממשיכה לחלק לנצח, עד שגיאת RecursionError.
✗ לא נכון
def merge_sort(a):
mid = len(a) // 2
...✓ נכון
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2שוכחים את השאריות במיזוג
כשאחד החצאים נגמר, בחצי השני עוד נשארו איברים. צריך להוסיף אותם לסוף.
✗ לא נכון
return result✓ נכון
return result + left[i:] + right[j:]הציר נכנס פעמיים
במיון מהיר עוברים על כל האיברים חוץ מהציר. אם גם הציר נכנס ל-smaller, הוא יופיע פעמיים, ואולי הרקורסיה לא תיגמר.
✗ לא נכון
for x in a:✓ נכון
for x in a[:-1]:"מהיר" זה תמיד מהיר
מיון מהיר עם הציר האחרון על רשימה ממוינת מחלק כל פעם לחלק ריק ולחלק עם כל השאר. זה המקרה הגרוע: בערך n²/2 השוואות. בדקו במעבדה.
דוגמה פתורה: חלוקה סביב ציר
הצעד הראשון של מיון מהיר על ציוני מבחן. הציר הוא האיבר האחרון, 61. עוברים על כל השאר ומחלקים לשתי רשימות. אחר כך ממיינים כל רשימה באותה דרך, ומחברים: smaller + [pivot] + bigger.
תרגול
שאלות שכולם שואלים
איך עובד מיון מיזוג?
מחלקים את הרשימה לשני חצאים, ממיינים כל חצי באותה שיטה (ברקורסיה), ואז ממזגים: משווים את האיבר הראשון שנשאר בכל חצי ומעבירים את הקטן לתוצאה. רשימה של איבר אחד כבר ממוינת, ושם הרקורסיה עוצרת. נסו במעבדה.
מה ההבדל בין מיון מיזוג למיון מהיר?
במיון מיזוג החלוקה פשוטה (באמצע) והעבודה היא במיזוג. במיון מהיר העבודה היא בחלוקה סביב ציר, והחיבור פשוט. מיון מיזוג תמיד בערך n·log n השוואות. מיון מהיר בדרך כלל מהיר מאוד, אבל עם ציר גרוע הוא עלול להגיע ל-n²/2.
למה n·log n טוב יותר מ-n²?
ברשימה של 1000 איברים, n² הוא מיליון, ו-n·log₂n הוא בערך 10,000. פי מאה פחות עבודה. וככל שהרשימה גדלה, הפער גדל עוד יותר. תרגלו למטה.