0. תמונה גדולה — למה צריך עוד מיון?
עד עכשיו הכרנו: InsertionSort (\(\Theta(n^2)\)), HeapSort (\(\Theta(n \log n)\)) ו-MergeSort (\(\Theta(n \log n)\)).
אז למה QuickSort?
- HeapSort מהיר אסימפטוטית, אבל לא יציב, ובפועל יש לו קבועים גדולים בגלל ה-percolate-down.
- MergeSort יציב ו-\(\Theta(n \log n)\) אפילו ב-worst case — אבל דורש \(\Theta(n)\) מקום עזר. זה בעיה במערכים ענקיים.
- QuickSort — בממוצע \(\Theta(n \log n)\), in-place (\(\Theta(\log n)\) מקום עזר בלבד), קבוע קטן בפועל, ובפרקטיקה המהיר ביותר ברוב המקרים. החיסרון: worst case \(\Theta(n^2)\), אבל זה נדיר.
מסקנת ההרצאה
QuickSort הוא ה-default sort של רוב השפות (Java's
Arrays.sort לפרימיטיביים, C's
qsort, Python's TimSort הוא היברידי). ההרצאה גם מוכיחה למה
אי אפשר לסדר מהר מ-\(\Theta(n \log n)\) אם מותר רק להשוות איברים — חסם תחתון יסודי בתורת האלגוריתמים.
1. QuickSort — האלגוריתם הרקורסיבי
אלגוריתם Divide-and-Conquer. השוני המרכזי מ-MergeSort: כל העבודה נעשית ב-Divide, וה-Combine ריק לחלוטין.
שלבי האלגוריתם
- Divide: בוחרים איבר מהמערך — ה-pivot. מסדרים מחדש כך ש: איברים \(\leq\) pivot משמאל, איברים \(>\) pivot מימין. ה-pivot עצמו "במקומו הסופי" במערך הממוין.
- Conquer: קוראים רקורסיבית על שני תת-המערכים.
- Combine: שום דבר! המערך כבר ממוין במקום. זה היתרון הגדול על MergeSort.
- Base case: תת-מערך באורך 0 או 1 — ממוין טריוויאלית.
Pseudocode
Quicksort(A, p, r):
if r − p > 0 then // יותר מאיבר אחד
q ← Partition(A, p, r) // q = המיקום של ה-pivot אחרי החלוקה
Quicksort(A, p, q − 1) // ממיין את הצד השמאלי
Quicksort(A, q + 1, r) // ממיין את הצד הימני
Return
// קריאה ראשונית:
Quicksort(A, 1, length(A))
למה אין Combine?
כי אחרי Partition כל איבר משמאל \(\leq\) pivot, וכל איבר מימין \(>\) pivot. אם נמיין את שני הצדדים — המערך הסופי ממוין באופן אוטומטי. ב-MergeSort, לעומת זאת, אחרי שני המיונים הרקורסיביים יש שני תת-מערכים ממוינים, אבל לא ידוע איזה איבר משמאל קטן מאיזה איבר מימין — לכן צריך Merge.
דוגמה מהירה: [2, 8, 7, 1, 3, 5, 6, 4]
נבחר pivot = 4 (האחרון). אחרי Partition:
[2, 1, 3, 4, 7, 5, 6, 8]
ה-4 במקום ה-4 (אינדקס q=4). עכשיו נקרא רקורסיבית:
- שמאל: Quicksort על [2, 1, 3]
- ימין: Quicksort על [7, 5, 6, 8]
ה-4 לא מטופל שוב — הוא
נעול במקומו.
2. Partition — הלב של QuickSort
זה השלב היחיד שעושה עבודה אמיתית. רוב הטעויות במבחנים קורות כאן — שווה להבין לעומק.
הרעיון: 3 אזורים במערך
חלוקה לוגית של המערך תוך כדי ריצה
עבור
Partition(A, l, r): בוחרים
x = A[r] (האיבר האחרון) כ-pivot. מנהלים שני מצביעים
i,
j:
- אזור "Less than pivot":
A[l..i] — כל איברים \(\leq x\).
- אזור "Greater than pivot":
A[i+1..j−1] — כל איברים \(> x\).
- אזור "Waiting":
A[j..r−1] — עוד לא בדוק.
A[r] = ה-pivot עצמו.
Pseudocode
Partition(A, l, r):
x = A[r] // pivot = האיבר האחרון
i = l − 1 // i מצביע על סוף האזור הקטן
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] // מעבירים את ה-pivot למקומו הסופי
return i + 1 // מיקום ה-pivot
דוגמה מלאה (פלט אחרי כל איטרציה): [2, 8, 7, 1, 3, 5, 6, 4], pivot=4
| j | A[j] | ≤4? | i (אחרי) | המערך |
|---|
| — | — | — | 0 | [2, 8, 7, 1, 3, 5, 6, 4] |
| 1 | 2 | כן | 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 | [2, 1, 7, 8, 3, 5, 6, 4] |
| 5 | 3 | כן | 3 | [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\).
שים לב: 4 במקום ה-4. שמאל = {2,1,3} (כולם \(\leq 4\)). ימין = {7,5,6,8} (כולם \(>4\)). ✓
משפט (אינווריאנט הלולאה)
לכל j, אחרי האיטרציה ה-j:
A[l..i] \leq xA[i+1..j] > xA[j+1..r−1] עוד לא בדוקA[r] = x (pivot)
ניתן להוכיח באינדוקציה על j. ההוכחה נדרשת במבחנים לעיתים.
סיבוכיות של Partition
הלולאה רצה מ-l ל-r-1, כלומר עוברים על \(n\) איברים (כאשר \(n = r-l+1\)). כל איטרציה: \(O(1)\). סה"כ: \(\Theta(n)\).
3. ניתוח Best Case
"Best case" של QuickSort הוא כאשר ה-pivot בכל קריאה הוא החציון של תת-המערך — חלוקה מאוזנת לחלוטין \(n/2 : n/2\).
רקורסיה במקרה הטוב
\[T(n) = 2T(n/2) + \Theta(n)\]
לפי משפט Master (מקרה 2): \(T(n) = \Theta(n \log n)\).
למה זה כמו MergeSort?
כי המבנה הרקורסיבי זהה: \(2T(n/2) + \Theta(n)\). ההבדל הוא
איפה נעשית העבודה הלינארית: ב-MergeSort ב-Merge (אחרי הקריאות), ב-QuickSort ב-Partition (לפני).
למה זה "Best" ולא "Average"?
הבחנה חשובה
הביטוי "best case" קצת מטעה: כל חלוקה
קבועה (לא בהכרח חציון, אפילו 1%:99%) נותנת בסופו של דבר \(\Theta(n \log n)\)! זה כי גם 99%·1% מוביל לעץ רקורסיה בעומק \(\log_{100/99} n = \Theta(\log n)\). הגרוע באמת זה רק כש-pivot הוא קצה אחד (1:n−1).
4. ניתוח Worst Case
קורה כשבכל קריאה ה-pivot הוא הקצה — חלוקה \(0 : n-1\). שום שאלה רקורסיבית לא מתבצעת בצד השמאלי (ריק), והצד הימני בגודל \(n-1\).
רקורסיה במקרה הגרוע
\[T(n) = T(n-1) + \Theta(n) = \Theta(n) + \Theta(n-1) + \ldots + \Theta(1) = \Theta(n^2)\]
(טור אריתמטי).
מתי זה קורה בפועל?
- מערך כבר ממוין בסדר עולה. כי pivot = האיבר האחרון = המקסימום.
- מערך כבר ממוין בסדר יורד. pivot = המינימום.
- כל האיברים שווים. כל איבר \(\leq\) pivot, אז ה-pivot סוף תמיד באינדקס האחרון.
פתרון מעשי
כדי להימנע מ-\(O(n^2)\) על מערכים ממוינים (שכיחים מאוד!): בוחרים pivot
אקראי, או בשיטה
median-of-three (חציון של A[l], A[r], A[(l+r)/2]). זה לא משנה את ה-worst case אסימפטוטית — אבל הופך אותו לסבירות אסטרונומית.
5. ניתוח Average Case — הוכחה רשמית מלאה
זה החלק הקשה בהרצאה — לעיתים קרובות מבקשים אותו במבחן. שווה ללמוד את ההצבות.
משפט
ההנחה: כל פרמוטציה של הקלט שכיחה באותה הסתברות. אז:
\[T_{\text{avg}}(n) = O(n \log n)\]
שלב 1 — נסחים את הרקורסיה הממוצעת
אם ה-pivot הוא האיבר ה-p בגודלו (rank p), אזי החלוקה היא \(p-1\) משמאל ו-\(n-p\) מימין. p אקראי אחיד מ-1 ל-n:
\[T_{\text{avg}}(n) = \Theta(n) + \frac{1}{n}\sum_{p=1}^{n} \bigl[T_{\text{avg}}(p-1) + T_{\text{avg}}(n-p)\bigr]\]
לפי סימטריה (כל סכום מופיע פעמיים):
\[T_{\text{avg}}(n) = \Theta(n) + \frac{2}{n}\sum_{k=0}^{n-1} T_{\text{avg}}(k)\]
שלב 2 — הצבת ההמרה (חוכמה מתמטית)
נגדיר \(S(n) = \dfrac{T_{\text{avg}}(n)}{n+1}\). אז \(T_{\text{avg}}(n) = (n+1)S(n)\). הצבה ב-recurrence ופישוט נותנת:
\[S(n) \leq S(n-1) + \frac{2d}{n+1}\]
כאשר \(d\) קבוע (מהמקדם של \(\Theta(n)\)).
שלב 3 — פותרים את S(n) הלינאריזציה
שורה אחר שורה:
\[S(n) \leq S(0) + 2d \sum_{k=1}^{n} \frac{1}{k+1} \leq 2d \cdot H_n\]
כאשר \(H_n = 1 + \tfrac{1}{2} + \tfrac{1}{3} + \ldots + \tfrac{1}{n}\) הוא
המספר ההרמוני ה-n-י.
ידוע ש- \(H_n = \ln n + \gamma + O(1/n) = O(\log n)\).
לכן: \(S(n) = O(\log n)\), ובהמשך:
\[T_{\text{avg}}(n) = (n+1) \cdot S(n) = (n+1) \cdot O(\log n) = O(n \log n). \quad \blacksquare\]
💡 בונוס — למה ההמרה ל-S(n) עובדת?
הרעיון: ה-recurrence המקורי כולל סכום של תוצאות קודמות. אם נחלק ב-\(n+1\) (בערך מספר ה-recursive calls), נקבל סדרה שמסכימה לטור הרמוני — וזה
טור גדל לאט מאוד. הטריק נקרא
telescoping: כל \(S(n)\) מבטא את ההפרש בין מצבים, ומחק את האיברים האמצעיים.
אותו טריק עובד גם בניתוח QuickSelect (הרצאה 6)!
6. תכונות QuickSort
| תכונה | QuickSort | הסבר |
|---|
| In-place? | כן ✓ | Partition מבצע swap-im במקום, ללא מערך עזר. |
| מקום עזר ממוצע | \(\Theta(\log n)\) | עומק מחסנית הרקורסיה. |
| מקום עזר Worst-case | \(\Theta(n)\) | עומק רקורסיה במקרה הגרוע = \(n\). פתרון: tail recursion על הצד הקטן. |
| Stable? | לא ✗ | ה-swap-im בתוך Partition משנים סדר של איברים שווים. |
| גרסה איטרטיבית? | אין טבעית | בלי רקורסיה צריך מחסנית מפורשת. |
| מקבילי? | טבעי ✓ | שני תת-המערכים בלתי תלויים — אפשר למיין בו-זמנית בליבות שונות. |
💡 בונוס — למה Stable חשוב?
כשממיינים אובייקטים עם מספר שדות (לדוגמה: שם + ציון),
stable sort מאפשר מיון רב-שלבי. נמיין קודם לפי שם, ואז לפי ציון — והאיברים שווי-ציון יישארו ממוינים לפי שם.
QuickSort לא יציב, אז הוא לא מתאים לסיטואציה הזו — אלא MergeSort/CountingSort.
7. אופטימיזציה מעשית — SimpleSort
בפועל, QuickSort נתקל בתופעה מעניינת: בתת-מערכים קטנים מאוד (10–20 איברים), ה-overhead של הרקורסיה גדול יותר מ-\(n^2\) של InsertionSort.
השיפור
Quicksort(A, p, r):
if r − p ≤ 20: // סף קטן
SimpleSort(A, p, r) // לרוב InsertionSort
else
q ← Partition(A, p, r)
Quicksort(A, p, q − 1)
Quicksort(A, q + 1, r)
הסיבוכיות האסימפטוטית לא משתנה — נשארה \(\Theta(n \log n)\) — אבל הקבועים בפועל קטנים יותר משמעותית. std::sort ב-C++ ו-Java's Arrays.sort משתמשים בטריק הזה.
8. משפט Master
כלי כללי לפתרון נוסחאות רקורסיביות מהצורה הסטנדרטית — מאוד שכיח במבחנים.
משפט Master
עבור \(T(n) = a \cdot T(n/b) + \Theta(n^k)\) כאשר \(a \geq 1, b > 1, k \geq 0\):
- אם \(a > b^k\): \(T(n) = \Theta(n^{\log_b a})\)
- אם \(a = b^k\): \(T(n) = \Theta(n^k \log n)\)
- אם \(a < b^k\): \(T(n) = \Theta(n^k)\)
כיצד לזכור את שלושת המקרים?
אינטואיציה — איפה רוב העבודה?
- מקרה 1 (\(a > b^k\)): רוב העבודה בעלים של עץ הרקורסיה — הרבה תתי-בעיות. הסיבוכיות נשלטת על-ידי מספר העלים.
- מקרה 2 (\(a = b^k\)): איזון — כל רמה תורמת אותו דבר. סך הכל = רמה אחת × מספר הרמות = \(n^k \cdot \log n\).
- מקרה 3 (\(a < b^k\)): רוב העבודה בשורש — הצמצום מהיר מהריבוי.
דוגמאות לכל מקרה
מקרה 1: \(T(n) = 4T(n/2) + n\)
\(a=4, b=2, k=1\). \(b^k = 2 < a = 4\) ⟹ מקרה 1. \(\log_b a = \log_2 4 = 2\). ⟹ \(T(n) = \Theta(n^2)\).
מקרה 2: \(T(n) = 2T(n/2) + n\)
(זה MergeSort/QuickSort בייסט-קייס). \(a=2, b=2, k=1\). \(b^k = 2 = a\) ⟹ מקרה 2. ⟹ \(T(n) = \Theta(n \log n)\). ✓
מקרה 3: \(T(n) = T(n/2) + n\)
(זה Binary Search על דברים שצריך לבדוק לינארית). \(a=1, b=2, k=1\). \(b^k = 2 > a = 1\) ⟹ מקרה 3. ⟹ \(T(n) = \Theta(n)\).
מתי המשפט לא חל?
- אם החלוקה לא שווה: \(T(n) = T(n-1) + n\) — אין \(n/b\). פותרים בעץ רקורסיה ידני.
- אם החלק הלא-רקורסיבי לא פולינומי: \(T(n) = 2T(n/2) + n \log n\) — צריך גרסה מורחבת של המשפט.
9. חסם תחתון למיון מבוסס השוואות
השאלה הגדולה: האם ניתן למיין מהר מ-\(\Theta(n \log n)\)? התשובה תלויה במודל החישוב.
מודל ההשוואות
אלגוריתם מיון "מבוסס השוואות" יכול לגשת לאיברים
רק דרך השוואות (\(<, =, >\)) ולהעתקות. לא יכול להשתמש בערך כאינדקס, בייצוג הבינארי, וכו'.
InsertionSort, HeapSort, MergeSort, QuickSort — כולם מבוססי השוואות. CountingSort (הרצאה 6) — לא.
הכלי: עץ ההחלטה
Decision Tree
- כל קודקוד פנימי = השוואה בין שני איברים (לדוגמה: "האם \(a_2 < a_5\)?").
- שני בנים = "כן" / "לא".
- כל עלה = פרמוטציה אפשרית של הקלט.
הריצה של האלגוריתם על קלט מסוים = מסלול מהשורש לעלה כלשהו.
מספר ההשוואות = עומק העלה.
הוכחת \(\Omega(n \log n)\) — Worst Case
משפט
כל אלגוריתם מיון מבוסס השוואות מבצע \(\Omega(n \log n)\) השוואות במקרה הגרוע.
הוכחה
- קלט של \(n\) איברים מובחנים → יש \(n!\) פרמוטציות אפשריות. עץ ההחלטה חייב להכיל לפחות \(n!\) עלים (אחד לכל פרמוטציה — חייב להבחין ביניהם).
- עץ בינארי בעומק \(h\) יכול לכלול לכל היותר \(2^h\) עלים. לכן: \(2^h \geq n! \;\Rightarrow\; h \geq \log_2(n!)\).
- נוסחת סטירלינג: \(\log(n!) = n \log n - n + O(\log n) = \Theta(n \log n)\).
- זמן הריצה במקרה הגרוע = עומק העץ = מספר ההשוואות במסלול הארוך ביותר ≥ \(\log_2(n!) = \Omega(n \log n)\). ∎
הוכחה ש-\(\log(n!) = \Theta(n \log n)\)
חישוב יסודי שהמרצה מצפה לראות במבחן
חצי תחתון:
\[\log(n!) = \log 1 + \log 2 + \ldots + \log n \geq \sum_{k=n/2+1}^{n} \log k \geq \frac{n}{2}\log\frac{n}{2} = \Omega(n \log n)\]
חצי עליון:
\[\log(n!) \leq \sum_{k=1}^{n} \log n = n \log n = O(n \log n)\]
לכן \(\log(n!) = \Theta(n \log n)\).
חסם תחתון גם ב-Average
החסם תקף גם במקרה הממוצע: עומק ממוצע של עלים בעץ בינארי full עם \(k\) עלים הוא לפחות \(\log k - O(1)\). מינימום מתקבל בעץ מאוזן.
מסקנה חשובה
HeapSort, MergeSort ו-QuickSort הם אופטימליים אסימפטוטית במודל מיון מבוסס השוואות. אי אפשר לבנות אלגוריתם מבוסס-השוואות שטוב מהם.
מי שרוצה שיפור (לינארי) חייב לוותר על מודל ההשוואות — מה שמוביל ל-CountingSort, BucketSort, RadixSort בהרצאה הבאה.
10. בונוס — תובנות נוספות שצריך לדעת
💡 1. למה דווקא pivot אחרון?
הבחירה של
A[r] שרירותית. אפשר גם
A[l] או אקראי. שלוש אופציות פופולריות:
- Last element: פשוט, אבל פגיע למערכים ממוינים.
- Random: מבטיח average \(\Theta(n \log n)\) על כל קלט (האקראיות בבחירת ה-pivot, לא בקלט).
- Median-of-three: חציון של
A[l], A[r], A[(l+r)/2] — מאזן יותר טוב בפועל, במיוחד על נתונים מסודרים-חלקית.
💡 2. Dutch National Flag — Partition משופר
כשיש הרבה כפילויות, פיצול ל-3 אזורים: \(<\) pivot, \(=\) pivot, \(>\) pivot. מבטיח שגם פיצולים גרועים לא מובילים ל-\(O(n^2)\) כשיש איברים שווים. שיטה זו נמצאת ב-Java's
Arrays.sort.
💡 3. הקשר ל-QuickSelect
ניתן להשתמש ב-Partition כדי לפתור Selection (מציאת איבר ה-k בגודלו) ב-\(\Theta(n)\) ממוצע! זה
QuickSelect — נלמד אותו בהרצאה הבאה. כל QuickSort הוא בעצם n recursive applications של QuickSelect.
💡 4. למה לא כל מערכת משתמשת ב-QuickSort?
- Linux kernel משתמש ב-HeapSort — כי אסור לאפשר ל-attacker לבחור קלט שגורם ל-\(O(n^2)\) ולתקוף את המכונה (DoS).
- Python משתמש ב-TimSort — היברידי MergeSort+InsertionSort, יציב, חזק על נתונים חצי-מסודרים שכיחים בפרקטיקה.
- Java משתמש ב-DualPivot QuickSort (Yaroslavskiy 2009) — גרסה משופרת.
💡 5. הקשר בין QuickSort ל-BST
הרצף של החלוקות ב-QuickSort מקביל לבנייה של עץ חיפוש בינארי (BST) רנדומלי: כל pivot הופך לשורש של תת-עץ.
זה אומר שאותה אנליזה ממוצעת תופסת גם ל-BST! הסיבה: גובה ממוצע של BST רנדומלי = \(\Theta(\log n)\).
11. סיכום וטבלת השוואה
| HeapSort | MergeSort | QuickSort |
|---|
| Worst-case | \(\Theta(n \log n)\) | \(\Theta(n \log n)\) | \(\Theta(n^2)\) |
| Best/Average | \(\Theta(n \log n)\) | \(\Theta(n \log n)\) | \(\Theta(n \log n)\) |
| In-place | כן | לא (\(\Theta(n)\) עזר) | כן (\(\Theta(\log n)\) עזר ממוצע) |
| Stable | לא | כן | לא |
| בפועל מהיר? | בינוני | טוב | הכי טוב |
מה הכי חשוב לזכור?
- QuickSort: Partition + 2 recursive calls. Best/Avg \(\Theta(n \log n)\), Worst \(\Theta(n^2)\), in-place, לא יציב.
- ניתוח Average: הצבה \(S(n) = T(n)/(n+1)\) ⟹ \(S(n) \leq 2d \cdot H_n = O(\log n)\) ⟹ \(T(n) = O(n \log n)\).
- משפט Master: \(T(n) = aT(n/b) + \Theta(n^k)\) — 3 מקרים לפי \(a\) מול \(b^k\).
- Lower bound: כל מיון מבוסס השוואות חייב \(\Omega(n \log n)\) (worst & average). הוכחה דרך עץ החלטה: \(2^h \geq n! \Rightarrow h \geq \log(n!) = \Omega(n \log n)\).
ההרצאה הבאה: איך לעקוף את החסם של \(\Omega(n \log n)\) — מיון לינארי (CountingSort, BucketSort, RadixSort) ובעיית הסלקציה.