מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/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 פועלת ג"כ על מערך בעל אורך   (שוב, בהזנחת שגיאות עיגול). שורות אלה, על כן, פועלות בזמן  .

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