שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2023 - מיון

נתון מערך $A[1..n]$ המקיים את התנאי: אם $A[i] > A[j]$, $i < j$, אזי $j = i+1$ (עבור $1 \leq i, j \leq n$). איזה אלגוריתם ימיין את $A$ בזמן טוב יותר: מיון-הכנסה או מיון-מיזוג? הוכיחו את טענתכם.

רמז: חשבו כמה היפוכים (inversions) יכולים להיות במערך שכזה. אם $A[i] > A[j]$ ו-$i < j$ אז בהכרח $j = i+1$, כלומר כל היפוך הוא בין שכנים בלבד.

פתרון: **טענה:** מיון-הכנסה ימיין את $A$ בזמן טוב יותר. **הוכחה:** נבדוק כמה היפוכים (inversions) יכולים להיות במערך. היפוך הוא זוג $(i,j)$ כך ש-$i < j$ וגם $A[i] > A[j]$. לפי התנאי, אם $A[i] > A[j]$ ו-$i < j$, אז $j = i+1$. כלומר, היפוכים יכולים להתקיים רק בין איברים שכנים. מספר הזוגות השכנים הוא $n-1$, לכן מספר ההיפוכים הוא לכל היותר $n-1$. ידוע שזמן הריצה של **מיון-הכנסה** הוא $\Theta(n + d)$ כאשר $d$ הוא מספר ההיפוכים. במקרה שלנו $d \leq n-1$, ולכן: $$T_{\text{insertion}} = \Theta(n + (n-1)) = \Theta(n)$$ לעומת זאת, **מיון-מיזוג** רץ תמיד בזמן $\Theta(n \log n)$. מכיוון ש-$\Theta(n)$ טוב יותר מ-$\Theta(n \log n)$, מיון-הכנסה עדיף. $\blacksquare$