סיבוכיות וניתוחבינוני5 דק' קריאה
השוואה בין אלגוריתמי המיון - מי המהיר באמת?
טבלה השוואתית של 6 אלגוריתמי מיון נפוצים, וכיצד לבחור באלגוריתם הנכון.
כל אלגוריתם מיון מציע פשרה שונה בין מהירות, זיכרון, יציבות ופשטות מימוש. בחירת האלגוריתם הנכון תלויה בקלט הצפוי ובסביבה.
טבלת השוואה
| אלגוריתם | ממוצע | גרוע | זיכרון | יציב? |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | כן |
| Selection Sort | O(n²) | O(n²) | O(1) | לא |
| Insertion Sort | O(n²) | O(n²) | O(1) | כן |
| Merge Sort | O(n log n) | O(n log n) | O(n) | כן |
| Quick Sort | O(n log n) | O(n²) | O(log n) | לא |
| Heap Sort | O(n log n) | O(n log n) | O(1) | לא |
מה זה 'יציב' (Stable)?
אלגוריתם מיון יציב שומר על הסדר היחסי המקורי של אלמנטים שווים. זה חשוב כשמבצעים מיון לפי יותר ממפתח אחד (למשל, מיון ראשון לפי שם, ואחר כך לפי גיל).
איזה אלגוריתם לבחור?
- מערך קטן (< 50) או כמעט ממוין → Insertion Sort
- ביצועים יציבים ויציבות → Merge Sort
- מהירות בפועל וזיכרון מוגבל → Quick Sort (עם בחירת ציר חכמה)
- ביצועי O(n log n) מובטחים בלי זיכרון נוסף → Heap Sort
- לימוד והבנה בלבד → Bubble Sort
בפועל: Java משתמש ב-Timsort (היברידי של Merge + Insertion) למיון של אובייקטים, ו-Dual-Pivot Quicksort לפרימיטיבים. פייתון משתמש ב-Timsort בכל המקרים.