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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

1[עריכה]

נוכיח את הסופיות והנכונות באינדוקציה על (אורך הקטע), אותו נגדיר כ.


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

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

מש"ל.PNG

2[עריכה]

נתחיל במספר נקודות המשותפות לסעיף זה ולסעיף הבא. נגדיר את זמן הריצה על קלט בגודל כ. הקריאה לפונקציה וביצוע השורות 1-4 עולות , וPartition ב5 עולה .


בסעיף זה, 6 פועלת על מערך בעל אורך , ו7 פועלת על מערך בעל אורך . שורות אלה, על כן, פועלות בזמן . נקבל, לכן, את נוסחת הנסיגה .

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













3[עריכה]

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

בסעיף זה, 6 פועלת על מערך בעל אורך (בהזנחת שגיאות עיגול), ו7 פועלת ג"כ על מערך בעל אורך (שוב, בהזנחת שגיאות עיגול). שורות אלה, על כן, פועלות בזמן .

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