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