מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/Quicksort/תרגילים/Quicksort מודרך/תשובה

1

נוכיח את הסופיות והנכונות באינדוקציה על $\displaystyle b-e+1$ (אורך הקטע), אותו נגדיר כ$\displaystyle n$.

הוכחה: (בסיס האינדוקציה) כאשר $\displaystyle n=0$ (הקטע ריק) או $\displaystyle n=1$ (קטע בעל איבר יחד), אז הפונקציה חוזרת ישר בלי לשנות את המערך (רואים זאת מ1-2). הפונקציה סופית ונכונה במקרים אלה, לכן.

(מעבר האינדוקציה) נניח סופיות ונכונות עד $\displaystyle n-1$ (לא כולל). נניח שמכניסים מערך בעל גודל $\displaystyle n$. שורה 5 קוראת לPartition, אשר מחלקת את המערך לשני חלקים: Values[b, ..., p] וValues[p + 1, ..., e], כך ש$\displaystyle b\leq p<e$, וכל איבר בחלק הראשון קטן או שווה לכל איבר בחלק השני (בשאלה נאמר שמותר להניח זאת, אך אפשר גם לוודא זאת מהתבוננות בPartition). שימו לב שהיות ש$\displaystyle b\leq p<e$, אז אורך כל אחד משני החלקים קטן ממש מ$\displaystyle n$. עפ"י הנחת האינדוקציה, 6-7 ימיינו כל אחד משני החלקים (ואף בזמן סופי). אם שני החלקים ממויינים, וכל איבר בחלק השמאלי קטן או שווה לכל אחד מאיברי החלק הימני, אז בהכרח כל המערך ממויין.

2

נתחיל במספר נקודות המשותפות לסעיף זה ולסעיף הבא. נגדיר את זמן הריצה על קלט בגודל $\displaystyle n$ כ$\displaystyle T(n)$. הקריאה לפונקציה וביצוע השורות 1-4 עולות $\displaystyle O(1)$, וPartition ב5 עולה $\displaystyle \Theta (n)$.

בסעיף זה, 6 פועלת על מערך בעל אורך $\displaystyle 1$, ו7 פועלת על מערך בעל אורך $\displaystyle n-1$. שורות אלה, על כן, פועלות בזמן $\displaystyle T(1)+T(n-1)$. נקבל, לכן, את נוסחת הנסיגה $\displaystyle T(n)=\Theta (n)+T(1)+T(n-1)$.

נפתור נוסחה זו בעזרת פרישה:

$\displaystyle T(n)=$
$\displaystyle \Theta (n)+T(1)+T(n-1)=$
$\displaystyle \Theta (n)+T(1)+\Theta (n-1)+T(1)+T(n-2)=$
$\displaystyle \Theta (n)+T(1)+\Theta (n-1)+T(1)+\Theta (n-2)+T(1)+T(n-3)=$

$\displaystyle \cdots$

$\displaystyle \Theta (n)+T(1)+\Theta (n-1)+T(1)+\Theta (n-2)+T(1)+\Theta (n-3)+T(1)+...T(1)+T(1)=$
$\displaystyle \sum _{i=1}^{n}[\Theta (i)+T(1)]=$
$\displaystyle \sum _{i=1}^{n}[\Theta (i)]+\sum _{i=1}^{n}[]T(1)]=$
$\displaystyle \Theta (n^{2})+n\cdot \Theta (1)=$
$\displaystyle \Theta (n^{2}).$

3

נשתמש בנקודות שצויינו בסעיף הקודם כמשותפות לשני הסעיפים.

בסעיף זה, 6 פועלת על מערך בעל אורך $\displaystyle n/2$ (בהזנחת שגיאות עיגול), ו7 פועלת ג"כ על מערך בעל אורך $\displaystyle n/2$ (שוב, בהזנחת שגיאות עיגול). שורות אלה, על כן, פועלות בזמן $\displaystyle 2\cdot T(n/2)$.

נקבל, לכן, את נוסחת הנסיגה $\displaystyle T(n)=\Theta (n)+2\cdot T(n/2)$. יש דרכים רבות לפתור נוסחת נסיגה זו - הפשוטה ביותר היא לזהות שזו נוסחת הנסיגה של מיון מיזוג, ולכן פתרונה $\displaystyle T(n)=\Theta (n\cdot \log(n))$.