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

אלגוריתם מיון הוא נוהל שמקבל אוסף של ערכים ומחזיר אותם מסודרים לפי יחס סדר כלשהו — בדרך כלל מהקטן לגדול. זו אחת הבעיות הנחקרות ביותר במדעי המחשב, ולא במקרה: מיון הוא שלב הכנה שמאפשר לאלגוריתמים אחרים לעבוד מהר יותר. חיפוש בינארי דורש מערך ממוין, זיהוי כפילויות הופך לסריקה לינארית אחת אחרי מיון, ומיזוג של שתי רשימות ממוינות הוא O(n) במקום O(n·m).

מעבר לשימוש המעשי, אלגוריתמי מיון הם הדרך הנפוצה ביותר ללמד ניתוח סיבוכיות. הם קצרים מספיק כדי להבין אותם במלואם, אבל מציגים הבדלי ביצועים דרמטיים: על מערך של מיליון איברים, מיון בועות מבצע בערך 10¹² השוואות בעוד מיון מיזוג מבצע כ-2·10⁷. זהו פער של פי חמישים אלף, והוא מה שהופך את ההבדל בין O(n²) ל-O(n log n) למוחשי.

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

שלושת אלה חולקים סיבוכיות של O(n²) במקרה הממוצע, אך הם רחוקים מלהיות זהים. מיון בועות (Bubble Sort) עובר על המערך שוב ושוב ומחליף כל זוג סמוך שאינו בסדר הנכון, כך שהערך הגדול ביותר מבעבע לסוף בכל מעבר. עם דגל שמזהה מעבר ללא החלפות הוא מגיע ל-O(n) על מערך שכבר ממוין — יתרון שאין למיון בחירה.

מיון בחירה (Selection Sort) מוצא בכל איטרציה את המינימום מבין האיברים שנותרו ומציב אותו בסוף החלק הממוין. הוא תמיד מבצע בדיוק n(n-1)/2 השוואות — גם על קלט ממוין — אבל לכל היותר n-1 החלפות. זה הופך אותו לבחירה סבירה כשכתיבה לזיכרון יקרה משמעותית מקריאה, למשל בזיכרון פלאש.

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

מיון מיזוג (Merge Sort) מיישם הפרד ומשול: הוא מחלק את המערך לשניים, ממיין כל חצי רקורסיבית, וממזג את שתי התוצאות הממוינות למערך אחד. עומק הרקורסיה הוא log n והמיזוג בכל רמה עולה O(n), ומכאן O(n log n) — במקרה הטוב, הממוצע והגרוע כאחד. המחיר הוא O(n) זיכרון נוסף עבור מערך העזר.

מיון מהיר (Quick Sort) בוחר ציר (pivot), מחלק את המערך לאיברים קטנים ממנו וגדולים ממנו, וממיין כל צד רקורסיבית. בממוצע הוא O(n log n) עם קבועים קטנים מאוד ולוקליות זיכרון מצוינת, ולכן הוא בדרך כלל המהיר ביותר בפועל. אך אם הציר נבחר גרוע בעקביות — למשל האיבר הראשון על מערך שכבר ממוין — החלוקה מתנוונת והסיבוכיות מתדרדרת ל-O(n²).

מיון ערימה (Heap Sort) בונה ערימת מקסימום מהמערך ואז שולף שוב ושוב את המקסימום לסוף. הוא מבטיח O(n log n) גם במקרה הגרוע ומשתמש ב-O(1) זיכרון נוסף — שילוב שאין לאף אחד משני האחרים. בתמורה הוא סובל מלוקליות זיכרון גרועה, ולכן איטי ממיון מהיר בפועל למרות סיבוכיות זהה. אלגוריתם Introsort, המשמש בספריית C++, מתחיל כמיון מהיר ועובר למיון ערימה כשעומק הרקורסיה חורג — וכך מקבל את שני היתרונות.

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

בפועל, שפות תכנות מודרניות כמעט אף פעם לא משתמשות באלגוריתם יחיד. Python ו-Java משתמשות ב-Timsort, הכלאה של מיון מיזוג ומיון הכנסה שמזהה רצפים ממוינים קיימים בקלט ומנצלת אותם. התוצאה היא O(n) על נתונים כמעט-ממוינים — תרחיש נפוץ מאוד בעולם האמיתי — ו-O(n log n) מובטח במקרה הגרוע.

הכלל המעשי: לרשימות קצרות מאוד (עד כ-20 איברים) מיון הכנסה מנצח בזכות תקורה נמוכה. כשנדרשת יציבות או ביצועים צפויים — מיון מיזוג. כשמעוניינים במהירות גולמית וזיכרון מוגבל — מיון מהיר עם בחירת ציר אקראית או חציון-של-שלושה. וכשחייבים ערובה למקרה הגרוע ללא זיכרון נוסף — מיון ערימה.