0. תזכורת מהירה — QuickSort בקצרה
High-Level Idea
- Divide: בוחרים pivot, מעבירים איברים \(\leq\) pivot שמאלה, \(>\) pivot ימינה.
- Conquer: מיון רקורסיבי של שני הצדדים.
- Base case: איבר בודד (או קבוע קטן של איברים).
Pseudocode (גרסת CLRS)
Quicksort(A, l, r):
if r − l > 2:
p ← Partition(A, l, r)
Quicksort(A, l, p − 1)
Quicksort(A, p + 1, r)
else:
Simplesort(A, l, r) // לדוגמה InsertionSort על מספר קבוע איברים
Partition(A, l, r):
x = A[r] // pivot = last element
i = l − 1
for j = l to r − 1:
if A[j] ≤ x:
i = i + 1
exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1
סיבוכיות בקצרה
| זמן | הערה |
|---|
| Best / Average | \(O(n \log n)\) | בהנחת קלט "טיפוסי" |
| Worst | \(\Theta(n^2)\) | קלט מסודר, או כל האיברים שווים, או partition גרוע מתמשך |
| Space | \(O(\log n)\) ממוצע | עומק רקורסיה. עדיף מ-MergeSort's O(n). |
חוזקות וחולשות
חוזקות: מהיר בפועל (קבוע קטן), in-place, מקבילי טבעי (שני תת-מערכים בלתי תלויים).
חולשות: Worst case \(O(n^2)\) (לא יציב, לא בטוח מול adversarial input — Linux Kernel דווקא משתמש ב-HeapSort).
1. Partition מלא צעד-אחר-צעד
שאלות על Partition שכיחות במבחנים. שווה מאוד להתאמן.
דוגמה
קלט: A = [2, 8, 7, 1, 3, 5, 6, 4],
pivot = A[r] = 4.
הראה את מצב המערך אחרי כל איטרציה של הלולאה ב-Partition.
פתרון מלא — אלגוריתם הסטנדרטי
אתחול: x = 4, i = 0 (כשהוא \(l - 1\)).
| j | A[j] | A[j] ≤ 4? | i (אחרי) | פעולה | המערך |
|---|
| — | — | — | 0 | אתחול | [2, 8, 7, 1, 3, 5, 6, 4] |
| 1 | 2 | ✓ | 1 | swap A[1]↔A[1] (אותו מקום) | [2, 8, 7, 1, 3, 5, 6, 4] |
| 2 | 8 | ✗ | 1 | שום פעולה | [2, 8, 7, 1, 3, 5, 6, 4] |
| 3 | 7 | ✗ | 1 | שום פעולה | [2, 8, 7, 1, 3, 5, 6, 4] |
| 4 | 1 | ✓ | 2 | swap A[2]↔A[4] | [2, 1, 7, 8, 3, 5, 6, 4] |
| 5 | 3 | ✓ | 3 | swap A[3]↔A[5] | [2, 1, 3, 8, 7, 5, 6, 4] |
| 6 | 5 | ✗ | 3 | שום פעולה | [2, 1, 3, 8, 7, 5, 6, 4] |
| 7 | 6 | ✗ | 3 | שום פעולה | [2, 1, 3, 8, 7, 5, 6, 4] |
סיום הלולאה: swap A[i+1]=A[4]=8 ↔ A[r]=A[8]=4.
תוצאה סופית: [2, 1, 3, 4, 7, 5, 6, 8]
החזרה: \(i + 1 = 4\) (המיקום של ה-pivot).
חוקים שצריך לזכור
i תמיד מצביע על סוף האזור "קטן או שווה ל-pivot".j סורק מהשמאל לימין.- כל "כן" → swap + i++.
- בסוף → swap בין A[i+1] ל-pivot עצמו.
תרגיל 1: QuickSort כשכל האיברים שווים
השאלה
מה זמן הריצה של QuickSort כשכל האיברים במערך שווים?
פתרון
נחשוב על Partition עם pivot שווה לכל האיברים: התנאי A[j] ≤ x מתקיים תמיד (כי \(x = x\)). אז i מתקדם בכל איטרציה. סוף הלולאה: i = r-1, ה-swap הסופי הוא A[r] ↔ A[r] (שום שינוי), והחזרה: q = r.
כלומר: ה-partition שם את ה-pivot בקצה הימני, וכל היתר מצד שמאל. זה מקרה גרוע! חלוקה \(n-1 : 0\).
רקורסיה: \(T(n) = T(n-1) + \Theta(n) = \Theta(n^2)\).
💡 למה זה מטריד?
כל-איברים-שווים נראה תרחיש "קל" אינטואיטיבית — לכאורה אין מה למיין! אבל QuickSort הקלאסי
לא מזהה את התרחיש, ועושה \(\Theta(n^2)\) עבודה לחינם.
הפתרון בעולם האמיתי: 3-way Partition (Dutch National Flag) — מחלקים ל-3 אזורים: \(<\), \(=\), \(>\) pivot. אחרי Partition, האזור של \(=\) pivot נעול במקומו, ואין רקורסיה עליו. תוצאה: \(\Theta(n)\) על מערך של איברים שווים.
תרגיל 2: זיהוי ה-pivot מ-array אחרי Partition
השאלה
לפניך מערך אחרי שלב הראשון של Partition:
[3, 0, 2, 4, 6, 8, 7, 9, 7].
אילו מהמספרים יכולים להיות ה-pivot של ה-partition?
פתרון
איך מזהים pivot חוקי? איבר במיקום \(p\) הוא pivot אפשרי אם:
- כל \(A[i]\) עם \(i < p\) הוא \(\leq A[p]\).
- כל \(A[j]\) עם \(j > p\) הוא \(> A[p]\).
בודקים כל איבר במערך:
| אינדקס | ערך | שמאל ≤? | ימין >? | pivot? |
|---|
| 1 | 3 | — (ריק, ✓) | 0, 2 לא > 3 → ✗ | לא |
| 2 | 0 | 3 לא ≤ 0 → ✗ | — | לא |
| 3 | 2 | 3 לא ≤ 2 → ✗ | — | לא |
| 4 | 4 | 3, 0, 2 ≤ 4 ✓ | 6, 8, 7, 9, 7 > 4 ✓ | כן |
| 5 | 6 | 3, 0, 2, 4 ≤ 6 ✓ | 8, 7, 9, 7 > 6 ✓ | כן |
| 6 | 8 | ... | 7 לא > 8 → ✗ | לא |
| 7 | 7 | 8 לא ≤ 7 → ✗ | — | לא |
| 8 | 9 | ... | 7 לא > 9 → ✗ | לא |
| 9 | 7 | 9 לא ≤ 7 → ✗ | — | לא |
תשובה: 4 ו-6.
המהות
ה-pivot ב-QuickSort נמצא תמיד
במקום הסופי שלו במערך הממוין. כל מה שצריך זה לבדוק את התנאי הזה לכל אינדקס.
2. תיאוריית חסמים — Upper vs Lower Bound
חסם עליון (Upper bound)
מוכיחים על-ידי
הצגת אלגוריתם וניתוח שלו. דוגמה: "Merge Sort עובד ב-\(O(n \log n)\)" — לכן \(O(n \log n)\) הוא חסם עליון לבעיית המיון.
חסם תחתון (Lower bound)
מוכיחים על-ידי
הוכחה שתקפה לכל אלגוריתם אפשרי. דוגמה: "כל מיון מבוסס השוואות חייב \(\Omega(n \log n)\)".
חסם תחתון \(L(n)\) → אלגוריתם חייב \(\Omega(L(n))\)
אם החסם התחתון לבעיה הוא \(L(n)\), אז כל אלגוריתם שפותר את הבעיה חייב לבזבז זמן של לפחות \(\Omega(L(n))\) (worst/avg/best — בהתאם למה שהחסם הוגדר).
טענה: כל אלגוריתם מיון חייב לקרוא את כל הקלט
הוכחה
- נניח בשלילה שיש אלגוריתם מיון שלא קורא את כל הקלט.
- אז יש אינדקס \(i\) שהאלגוריתם לעולם לא קורא.
- עכשיו נבנה שני קלטים שזהים בכל מקום פרט ל-\(i\):
- קלט \(A\): \(A[i]\) = הכי גדול.
- קלט \(B\): \(B[i]\) = הכי קטן.
- האלגוריתם רואה שני קלטים זהים מנקודת מבטו (הוא לא קרא את \(i\)), אז יחזיר אותו פלט.
- אבל הפלטים הממוינים שונים — סתירה!
מסקנה: כל מיון דורש \(\Omega(n)\). זה החסם הטריוויאלי.
החסם הלא-טריוויאלי: \(\Omega(n \log n)\) למיון מבוסס השוואות
- מודלים את האלגוריתם כעץ החלטה בינארי (כל קודקוד = השוואה, כל עלה = פרמוטציה).
- צריך \(n!\) עלים.
- עץ בינארי בעומק \(h\) מכיל לכל היותר \(2^h\) עלים ⟹ \(h \geq \log(n!) = \Theta(n \log n)\).
תרגיל 3: משחק הניחושים של Alice ו-Bob (חסם Ω(log n))
השאלה
Alice בוחרת מספר בין 1 ל-\(n\), ו-Bob צריך לנחש אותו על-ידי שאלות כן/לא ("האם המספר גדול מ-10?"). Alice עונה באמת. הוכח שאסטרטגית Bob חייבת לדרוש \(\Omega(\log n)\) שאלות במקרה הגרוע.
פתרון
שלב 1 — מודלים את האסטרטגיה כעץ החלטה
- כל קודקוד = שאלה ש-Bob שואל.
- שני ילדים: "כן" / "לא".
- כל עלה = ניחוש סופי.
שלב 2 — חייבים לפחות n עלים
כי Bob חייב להיות מסוגל לנחש כל אחד מ-n המספרים — לכן חייב להיות עלה לכל אפשרות.
שלב 3 — קושרים בין עלים לגובה
- עץ בינארי בגובה \(h\) מכיל לכל היותר \(2^h\) עלים.
- צריך \(\geq n\) עלים: \(2^h \geq n \;\Rightarrow\; h \geq \log_2 n\).
- הגובה הוא מספר השאלות במסלול הארוך ביותר.
שלב 4 — Alice יכולה לבחור את "העמוק ביותר"
בכל אסטרטגיה של Bob, יש לפחות עלה אחד בעומק \(\lceil \log_2 n \rceil\). Alice יכולה לבחור את המספר שמתאים לעלה הזה, ולכן Bob יצטרך לפחות כל כך הרבה שאלות.
מסקנה: \(\Omega(\log n)\) שאלות במקרה הגרוע. ∎
דוגמה ל-n=8
אסטרטגיה אופטימלית (binary search): "האם > 4?" → "האם > 2/6?" → "האם > 1/3/5/7?".
עץ עם 8 עלים בעומק 3 = \(\log_2 8\). Alice יכולה לבחור 5 → Bob חייב 3 שאלות.
💡 התובנה הגדולה: זו אותה הוכחה!
ההוכחה ש-\(n!\) עלים → \(\Omega(\log n!) = \Omega(n \log n)\) למיון, וההוכחה ש-\(n\) עלים → \(\Omega(\log n)\) למשחק ניחושים — שתיהן ב
אותה תבנית:
- מודלים אלגוריתם כעץ החלטה בינארי.
- סופרים כמה עלים נדרשים (= מספר הפלטים האפשריים).
- גובה ≥ log(מספר עלים).
זה patten — תלמדו לזהות אותו במבחן!
תרגיל 4: מציאת ה-Peak במערך — אופטימלי
השאלה
נתון מערך \(A\) של \(n\) שלמים מובחנים שיש בו אינדקס \(i\) כך ש:
- \(A[1] < A[2] < \ldots < A[i]\) (עליה ממש)
- \(A[i] > A[i+1] > \ldots > A[n]\) (ירידה ממש)
דוגמה: \(A = [-5, 7, 10, 19, 32, 31, 30, 1, -1]\), \(i = 5\).
מצא את \(i\) באופן אופטימלי. כלומר:
- Upper bound: תן אלגוריתם בזמן הכי טוב שתוכל.
- Lower bound: הוכח שאי אפשר לעשות מהר יותר.
חלק א — Upper Bound: Binary Search
פתרון
בהינתן אינדקס \(i\), נוכל לקבוע אם הפיק לפני/ב-/אחרי \(i\) ע"י בדיקת המגמה ב-\(A[i-1], A[i], A[i+1]\):
- אם \(A[i-1] < A[i] < A[i+1]\) → עליה. הפיק אחרי \(i\).
- אם \(A[i-1] > A[i] > A[i+1]\) → ירידה. הפיק לפני \(i\).
- אם \(A[i-1] < A[i] > A[i+1]\) → הפיק הוא \(i\)!
בכל איטרציה, הטווח של מועמדי הפיק מתחלק לחצי. סיבוכיות: \(O(\log n)\).
חלק ב — Lower Bound: רדוקציה מ-Binary Search
פתרון
נטען שמציאת פיק קשה לפחות כמו חיפוש בינארי, שיודעים שהוא \(\Omega(\log n)\). שיטה: רדוקציה.
הרעיון
חיפוש בינארי: נתון \(A\) ממוין ו-target \(x\), מצא \(k\) כך ש-\(A[k] = x\).
נבנה מערך \(B\) שיש לו פיק בדיוק במיקום \(k\):
\[B[i] = -|x - A[i]|\]
למה \(B\) יש פיק?
- \(|x - A[i]|\) = המרחק בין \(x\) ל-\(A[i]\).
- \(A\) ממוין → כש-\(i\) גדל, \(A[i]\) קרב ל-\(x\), מגיע ל-\(x\), ואז מתרחק.
- אז \(|x - A[i]|\) יורד עד שהוא 0 (כש-\(A[i] = x\)), ואז עולה.
- \(B[i] = -|x - A[i]|\) עולה עד 0, ואז יורד — צורה של פיק!
- הפיק (B[i] = 0) בדיוק במיקום שבו \(A[i] = x\). זה ה-\(k\) שמחפשים.
למה זה לא linear-time waste?
בעיה: לבנות את \(B\) עצמו דורש \(\Theta(n)\). אם נבנה אותו, אז כבר ביזבזנו \(n\), והוכחנו \(\Omega(n)\), לא \(\Omega(\log n)\). פתרון: לא נבנה את \(B\) במפורש. במקום זאת, כל פעם שאלגוריתם הפיק קורא ל-\(B[i]\), נחשב את הערך מ-\(A[i]\) ב-\(O(1)\).
סוף ההוכחה
אם אלגוריתם פיק רץ ב-\(o(\log n)\), אז ניתן לפתור חיפוש ממוין ב-\(o(\log n)\) (קוראים את אותם איברים מ-\(A\) במקום מ-\(B\)). זו סתירה לחסם התחתון של חיפוש בינארי. ∎
💡 הטריק המרכזי — Implicit Construction
זו טכניקה כללית בתורת האלגוריתמים: ברדוקציות, אם הבניה של הקלט החדש לוקחת זמן רב, מחשבים אותו "לפי דרישה" (on-demand) במקום מראש. זה מה שנקרא
reduction with implicit input.
💡 הקשר ל-quicksort
כל ההוכחות כאן (חסם תחתון לחיפוש, לפיק, למיון) מבוססות על אותה ארכיטקטורה:
עץ החלטה. זה הכלי המרכזי בתורת חסמי-תחתון.
5. טיפים לקראת המבחן
💡 טיפ 1 — חזרה על Partition
תכין סימולציה חזותית של Partition על שני קלטים שונים (קצר ובינוני). שאלות Partition שכיחות מאוד — תרגיל 2 הוא דוגמה.
💡 טיפ 2 — זיהוי מקרים גרועים של QuickSort
יש 3 מקרים שתמיד יביאו ל-\(\Theta(n^2)\):
- מערך ממוין בסדר עולה.
- מערך ממוין בסדר יורד.
- כל האיברים שווים.
כולם נובעים מאותה סיבה: partition נותן חלוקה \(0 : n-1\). זכור את זה!
💡 טיפ 3 — תבנית חסם תחתון בעץ החלטה
- מודלים את האלגוריתם כעץ החלטה בינארי.
- סופרים את מספר הפלטים האפשריים = מספר העלים הנדרשים.
- מקבלים: גובה העץ \(\geq \log(\text{מספר עלים})\).
- זמן ריצה = גובה העץ (במקרה הגרוע) או עומק ממוצע (במקרה הממוצע).
כל שאלת חסם תחתון במבחן נופלת לפתרון לפי התבנית הזו.
💡 טיפ 4 — רדוקציות
כדי להוכיח חסם תחתון לבעיה X: למצוא בעיה Y שכבר יודעים שדורשת זמן \(T\), ולהראות שאלגוריתם ל-X יוכל לפתור Y באותו זמן (פלוס overhead קטן). זה הוכיח שגם X דורש \(T\).
הטריק: אם הרדוקציה מהירה (לא משנה את האסימפטוטה), זה תקף. אם היא איטית — נצטרך implicit input.
💡 טיפ 5 — שאלות "אילו מקרים גרועים?"
במבחן יבקשו לעיתים: "תאר תרחיש שבו QuickSort רץ ב-\(\Theta(n^2)\)" / "נדרש לפחות \(\Omega(n)\)".
תוכן את התשובות מראש:
- QuickSort \(\Theta(n^2)\): מערך ממוין, או partition שמחזיר תמיד את הקצה.
- QuickSelect \(\Theta(n^2)\): כנ"ל.
- BucketSort \(\Theta(n^2)\): כל האיברים באותו דלי.
- חסם \(\Omega(n)\) למיון: ההוכחה בקריאת כל הקלט.
- חסם \(\Omega(n \log n)\) למיון מבוסס השוואות: עץ החלטה עם \(n!\) עלים.