0. תמונה גדולה — איך עוקפים את \(\Omega(n \log n)\)?
בהרצאה הקודמת הוכחנו שכל מיון מבוסס השוואות חייב לפחות \(\Omega(n \log n)\) השוואות. השאלה הגדולה היום: איך לעקוף את החסם?
המפתח
החסם רלוונטי
רק כשהאלגוריתם משתמש בהשוואות בלבד. אם נדע משהו על המבנה של הקלט — למשל שהמספרים שלמים בטווח ידוע, או שהם מתפלגים אחיד — נוכל להשתמש בערך עצמו כ-
אינדקס למערך עזר. זה לא "השוואה" — וזה מאפשר מיון לינארי.
בהרצאה: שלושה אלגוריתמי מיון לינאריים שונים, ואז נושא בלתי-קשור לכאורה אבל קרוב אלגוריתמית — מציאת סטטיסטיקות סדר (חציון, איבר ה-k בגודלו).
המסקנה לקראת המבחן
- אין סתירה בין החסם של הרצאה 5 לבין אלגוריתמי הרצאה 6. החסם מדבר על מודל מסוים, ומיוני הרצאה 6 חיים במודל אחר.
- השאלה במבחן לא תהיה "האם אפשר ב-\(O(n)\)?" אלא "בהינתן מבנה כזה של קלט, איזה אלגוריתם הכי מתאים?".
1. Counting Sort — דוגמה מלאה צעד-אחר-צעד
הנחות
- קלט: \(A[1..n]\) של שלמים בטווח \(\{1, 2, \ldots, k\}\).
- פלט: \(B[1..n]\), פרמוטציה ממוינת של \(A\).
- עזר: \(C[1..k]\).
אלגוריתם (ארבעה שלבים)
CountingSort(A, n, k):
// שלב 1: אתחול C, Θ(k)
for i ← 1 to k:
C[i] ← 0
// שלב 2: ספירה — C[i] = |{j : A[j] = i}|, Θ(n)
for j ← 1 to n:
C[A[j]] ← C[A[j]] + 1
// שלב 3: סכומים מצטברים — C[i] = |{j : A[j] ≤ i}|, Θ(k)
for i ← 2 to k:
C[i] ← C[i] + C[i−1]
// שלב 4: הצבה מהסוף להתחלה, Θ(n)
for j ← n downto 1:
B[C[A[j]]] ← A[j]
C[A[j]] ← C[A[j]] − 1
דוגמה מפורטת: n=5, k=4, \(A = [4, 1, 3, 4, 3]\)
צעד 1: אתחול C
C = [0, 0, 0, 0] (אינדקסים 1..4)
צעד 2: ספירה
- j=1: A[1]=4 ⟹ C[4]++ ⟹ C = [0, 0, 0, 1]
- j=2: A[2]=1 ⟹ C[1]++ ⟹ C = [1, 0, 0, 1]
- j=3: A[3]=3 ⟹ C[3]++ ⟹ C = [1, 0, 1, 1]
- j=4: A[4]=4 ⟹ C[4]++ ⟹ C = [1, 0, 1, 2]
- j=5: A[5]=3 ⟹ C[3]++ ⟹ C = [1, 0, 2, 2]
אינטרפרטציה: יש מופע אחד של 1, שני מופעים של 3, שני מופעים של 4.
צעד 3: סכומים מצטברים
- i=2: C[2] = 0+1 = 1 ⟹ C = [1, 1, 2, 2]
- i=3: C[3] = 2+1 = 3 ⟹ C = [1, 1, 3, 2]
- i=4: C[4] = 2+3 = 5 ⟹ C = [1, 1, 3, 5]
אינטרפרטציה חדשה: יש איבר אחד ≤1, איבר אחד ≤2, שלושה איברים ≤3, חמישה איברים ≤4.
זה הסוד של האלגוריתם: אם A[j]=3, אז ערכו ב-B צריך להיות במיקום שמספרו = "כמה איברים ≤3 יש?" = 3 (זו תהיה הופעה האחרונה של 3).
צעד 4: הצבה מהסוף להתחלה
- j=5: A[5]=3, C[3]=3 ⟹ B[3]=3, C[3]→2 ⟹ B = [_, _, 3, _, _]
- j=4: A[4]=4, C[4]=5 ⟹ B[5]=4, C[4]→4 ⟹ B = [_, _, 3, _, 4]
- j=3: A[3]=3, C[3]=2 ⟹ B[2]=3, C[3]→1 ⟹ B = [_, 3, 3, _, 4]
- j=2: A[2]=1, C[1]=1 ⟹ B[1]=1, C[1]→0 ⟹ B = [1, 3, 3, _, 4]
- j=1: A[1]=4, C[4]=4 ⟹ B[4]=4, C[4]→3 ⟹ B = [1, 3, 3, 4, 4] ✓
מסקנה
סיבוכיות: \(\Theta(n + k)\). כאשר \(k = O(n)\) — לינארי. מקום: \(\Theta(n + k)\).
לא in-place (יש מערך B),
יציב (סעיף הבא).
2. למה Counting Sort יציב — וכיצד
זה נושא חשוב במיוחד כי Radix Sort דורש מיון יציב, וזו הסיבה שמשתמשים ב-Counting Sort בכל שלב של Radix.
תזכורת: מיון יציב
מיון נקרא
יציב אם שני איברים שווי-מפתח שומרים על הסדר היחסי שלהם בין הקלט לפלט.
משפט
Counting Sort הוא יציב — ובלבד שלולאה (4) רצה
מ-n ל-1 (downto), לא 1 ל-n.
למה? הוכחה אינטואיטיבית
נניח \(A[j_1] = A[j_2] = v\) ו-\(j_1 < j_2\) (כלומר \(A[j_1]\) הופיע קודם).
כשרצים מהסוף להתחלה, מטפלים קודם ב-\(A[j_2]\):
- \(B[C[v]] = A[j_2]\) במיקום \(m = C[v]\).
- \(C[v]\) קטן ל-\(m-1\).
- אחר כך מטפלים ב-\(A[j_1]\): \(B[m-1] = A[j_1]\).
תוצאה: \(A[j_1]\) ב-\(B[m-1]\), \(A[j_2]\) ב-\(B[m]\) — \(j_1 < j_2\) → \(A[j_1]\) מופיע ראשון ב-B. ✓
ואם היינו רצים מ-1 ל-n? אז היינו שמים את \(A[j_1]\) ראשון, אחר כך \(C[v]\) קטן, ו-\(A[j_2]\) היה הולך למיקום נמוך יותר. הסדר היה מתהפך — ולא היה יציב. ❌
💡 למה חשוב שיציבות תהיה במיוחד כאן
כשמשתמשים ב-Counting Sort בתוך Radix Sort: כל ספרה ממוינת בנפרד. אם המיון על הספרה הראשונה לא יציב, כל המאמץ על הספרות הקודמות מתפזר.
היציבות זה לא נחמדות — זה הכרחי ל-Radix.
3. Bucket Sort — חלוקה לפי טווח
הנחות
- \(n\) איברים, מספרים ממשיים (לא בהכרח שלמים) בטווח \([0, n)\).
- המפתחות מתפלגים אחיד — הנחה חיונית!
הרעיון
מחלקים את הטווח \([0, n)\) ל-\(n\) דליים בגודל 1 כל אחד. הדלי של המספר \(k\) הוא \(\lfloor k \rfloor\). כל דלי = רשימה מקושרת.
- אם המפתחות מתפלגים אחיד — תוחלת המספר בכל דלי = 1.
- מיון של דלי בודד עם BubbleSort = \(O(\text{גודל הדלי}^2)\) = \(O(1)\) ממוצע.
- סך הכל: \(\Theta(n)\) בממוצע!
BucketSort(A):
n ← length(A)
B ← array of n empty linked lists
for i ← 0 to n−1:
insert A[i] into B[⌊A[i]⌋] // חלוקה
for j ← 0 to n−1:
SortList B[j] // מיון כל דלי
Concatenate B[0], B[1], …, B[n−1] // שרשור
דוגמה: n=20, מפתחות ב-[0, 20)
קלט A
[1.7, 3.2, 3.56, 18.3, 0.87, 1.1, 4.8, 3.1, …, 18.2, 5.1, 0.38, 16.67]
פלט הדליים B (כל דלי = LL)
- B[0] = {0.87, 0.38}
- B[1] = {1.7, 1.1}
- B[3] = {3.2, 3.56, 3.1}
- B[4] = {4.8}
- B[5] = {5.1}
- … (יתר ריקים)
- B[16] = {16.67}
- B[18] = {18.3, 18.2}
אחרי מיון כל דלי
- B[0] = {0.38, 0.87}
- B[1] = {1.1, 1.7}
- B[3] = {3.1, 3.2, 3.56}
- ...
ועכשיו שרשור מ-B[0] עד B[19] → תוצאה ממוינת.
ניתוח Worst case ו-Average
סיבוכיות
- Best/Average: \(\Theta(n)\) (בהנחת התפלגות אחידה).
- Worst case: \(\Theta(n^2)\) — אם כל האיברים נופלים לדלי אחד, ה-BubbleSort בו מבצע \(O(n^2)\).
הוכחה ל-Average Θ(n)
תהי \(n_i\) מספר האיברים בדלי \(i\). זמן כולל:
\[T = \Theta(n) + \sum_i O(n_i^2)\]
צריך להראות שתוחלת הסכום היא \(O(n)\). בהתפלגות אחידה, \(\mathbb{E}[n_i^2] = O(1)\) (זה לא מובן מאליו — דורש הוכחה דרך משתנים אינדיקטוריים), ולכן \(\mathbb{E}\!\left[\sum n_i^2\right] = O(n)\). ∎
הכללה — General Bucket Sort
הטווח \([0, n)\) לא חיוני. ניתן:
- לשנות-קנה-מידה: מפתחות ב-\([l, h)\) → דליים בגודל \((h - l)/n\).
- להשתמש בהתפלגויות לא-אחידות ידועות (גובה, גיל, מהירות נסיעה) — צריך פשוט לחלק נכון.
💡 שיפור worst case
אם משתמשים ב-MergeSort במקום BubbleSort בתוך הדלי: worst case יורד מ-\(\Theta(n^2)\) ל-\(\Theta(n \log n)\) — אבל קבוע גדול יותר. בפועל ב-Average זה לא משנה.
4. Radix Sort + סדר לקסיקוגרפי
הרעיון: כל מפתח מורכב מ-\(d\) שדות (ספרות). ממיינים \(d\) פעמים, פעם לכל שדה, החל מהשדה הפחות משמעותי.
RadixSort(A, d):
for i ← 1 to d:
use a stable linear sort to sort A by field i
שני דברים קריטיים שאנשים שוכחים
- הסדר LSD → MSD (Least → Most Significant Digit). אם נעשה הפוך — לא יעבוד.
- המיון בכל שלב חייב להיות יציב. אחרת הסדר משדה קודם נשבר.
דוגמה: d=3, מספרים תלת-ספרתיים
קלט: 329, 457, 657, 839, 436, 720, 355
| שלב | איזה שדה? | אחרי המיון |
|---|
| 1 | ספרה אחרונה (1s) | 720, 355, 436, 457, 657, 329, 839 |
| 2 | ספרה אמצעית (10s) | 720, 329, 436, 839, 355, 457, 657 |
| 3 | ספרה ראשונה (100s) | 329, 355, 436, 457, 657, 720, 839 ✓ |
למה זה עובד? — אינטואיציה
למה LSD-first עם stable sort עובד
אחרי שלב 1: המספרים ממוינים לפי ספרה אחרונה.
בשלב 2: נמיין לפי הספרה האמצעית. אבל מה קורה למספרים שיש להם אותה ספרה אמצעית? בזכות היציבות, הם נשארים בסדר שלהם משלב 1 — כלומר ממוינים לפי הספרה האחרונה.
אז אחרי שלב 2: מספרים ממוינים קודם לפי הספרה האמצעית, ובמקרה של שוויון — לפי האחרונה.
אחרי שלב 3 (אותו רעיון): ממוינים קודם לפי הספרה הראשונה, ובמקרה של שוויון — לפי הקודמות. זה בדיוק סדר לקסיקוגרפי = הסדר המספרי. ∎
סיבוכיות
Time complexity
יהי \(T_{ss}(n) = O(n)\) זמן המיון היציב על כל שדה (בדרך כלל Counting Sort עם k=10 או k=n).
\[T_{\text{total}}(n) = \Theta(d \cdot T_{ss}(n)) = \Theta(d \cdot n)\]
- אם \(d = O(1)\): \(\Theta(n)\) — לינארי!
- אם המספרים בטווח \([1, n^d]\) ומיוצגים בבסיס \(n\): \(d\) ספרות → סיבוכיות \(\Theta(d n)\), עם \(k = n\) בכל ספרה.
סדר לקסיקוגרפי של מילים
הגדרה
עבור מילים \(x = (x_d \ldots x_1)\) ו-\(y = (y_d \ldots y_1)\):
\[x < y \iff \exists t : x_t < y_t \text{ וגם } x_k = y_k \text{ לכל } k > t\]
למילים באורכים שונים: ממלאים את המילה הקצרה ב-blank \(\_\) (קטן מכל תו רגיל).
דוגמה
\(\text{safe}\_ < \text{sail}\_ < \text{salt}\_ < \text{salty}\)
(שווה ב-s, שווה ב-a, אז משווה בתו השלישי: f < i < l ⟹ safe < sail, salt. בין salt ל-salty: שווה עד "salt", אז blank < y, אז salt < salty.)
💡 שאלת מבחן קלאסית — Radix Sort לבחירה חכמה של בסיס
"נתון מערך של \(n\) מספרים שלמים ב-\([0, n^3 - 1]\). מיין ב-\(O(n)\)."
אחת השאלות הכי שכיחות במבחנים. פתרון: לייצג כל מספר בבסיס \(n\) ⟹ יש \(\log_n(n^3) = 3 = O(1)\) ספרות. Radix Sort עם Counting Sort על כל ספרה: \(\Theta(3 \cdot (n + n)) = \Theta(n)\). ✓
6. Order Statistics — דירוג וחציון
נושא חדש לגמרי — לא מיון, אבל קשור: לפעמים לא צריך לסדר הכל, רק למצוא איבר מסוים.
הגדרות יסודיות
תהי \(S\) קבוצה עם \(n\) איברים, וסידור ממוין \(X(1) \leq X(2) \leq \ldots \leq X(n)\):
- ה-i-th order statistic של \(S\) הוא \(X(i)\).
- ה-rank של \(x \in S\) הוא מיקומו ברשימה הממוינת.
- Minimum: rank = 1. Maximum: rank = n.
- Median: rank = \(\lceil(n+1)/2\rceil\) (אי-זוגי), או שתי חציונים (זוגי): \(n/2\) ו-\(n/2 + 1\).
דוגמה
ב-\(\{8, 2, 7, 5\}\) הסידור הממוין: \(2 < 5 < 7 < 8\).
- rank של 5 = 2 (השני).
- 1-st order stat = 2 (מינ').
- חציון = שני איברים: 5 ו-7.
7. בעיית הסלקציה Select(A, k)
הגדרת הבעיה
בהינתן מערך \(A\) לא ממוין ו-\(k\) (\(1 \leq k \leq n\)), מצא את האיבר עם rank \(k\) ב-\(A\).
שיטה 1 — מיון מלא
- למיין את \(A\) ולגשת ל-\(A[k]\). \(O(n \log n)\). פשוט, אבל מבזבז.
שיטה 2 — k פעמים min
- מצא minimum, השמט אותו. חזור k פעמים. סיבוכיות: \(\Theta(n k)\).
- טוב לזעיר k (\(k = O(1)\)) — \(\Theta(n)\). גרוע לחציון (\(k = n/2\)) — \(\Theta(n^2)\).
שיטה 3 — Min/Max ב-Θ(n) הפשוט ביותר
Minimum(A):
min ← A[1]
for i ← 2 to length(A):
if min > A[i] then min ← A[i]
return min
- סיבוכיות: \(\Theta(n)\), n−1 השוואות.
- אופטימיזציה: מציאת Min ו-Max בו-זמנית — \(3 \lceil n/2 \rceil\) השוואות בלבד (לא \(2n\)). הרעיון: כל זוג איברים → השוואה אחת ביניהם + השוואה לקנדידט min/max מתאים = 3 השוואות לזוג, ולא 4.
השאלה הגדולה
האם ניתן להגיע ל-\(\Theta(n)\)
לכל k, ובמיוחד לחציון?
תשובה: כן! זה QuickSelect (ממוצע) ו-MM-Select (worst-case). הסעיפים הבאים.
8. Quick Select — הוכחה מלאה ל-Average Θ(n)
הרעיון: גרסה של QuickSort שעוצרת מוקדם. אחרי Partition יודעים איפה ה-pivot — אם זה k, מצאנו. אחרת, יודעים באיזה צד k נמצא וממשיכים רק שם.
QuickSelect(A, left, right, k):
if (left == right): return A[left]
q = Partition(A, left, right)
if (q == k): return A[q]
if (k < q): return QuickSelect(A, left, q−1, k)
else: return QuickSelect(A, q+1, right, k)
שימושים
- חציון: QuickSelect(A, 1, n, n/2)
- איבר עם rank k: QuickSelect(A, 1, n, k)
ניתוח Best/Worst
- Best case (partition מאוזן תמיד \(n/2 : n/2\)): \(T(n) = T(n/2) + \Theta(n) = \Theta(n)\) ✓ — לפי משפט Master מקרה 3.
- Worst case (partition תמיד \(0 : n-1\)): \(T(n) = T(n-1) + \Theta(n) = \Theta(n^2)\) — גרוע ממיון!
ניתוח Average — הוכחה רשמית
משפט: T_avg(n) = O(n)
שלב 1. נסחים את ה-recurrence. תחת ההנחה הגרועה ביותר שאיבר rank(k) נופל בצד הגדול:
\[T_{\text{avg}}(n) \leq \frac{1}{n}\sum_{q=1}^{n} T_{\text{avg}}(\max(q-1, n-q)) + an\]
שלב 2. החלפת אינדקס \(q \to q' = q - 1\):
\[T_{\text{avg}}(n) \leq \frac{1}{n}\sum_{q=0}^{n-1} T_{\text{avg}}(\max(q, n-q-1)) + an\]
שלב 3. סימטריה — \(\max(q, n-q-1) = q\) כאשר \(q \geq n/2\), והפונקציה סימטרית סביב \(n/2\). לכן הסכום מ-\(n/2\) ל-\(n-1\) שווה למחצית הסכום הכולל:
\[T_{\text{avg}}(n) \leq \frac{2}{n}\sum_{q=n/2}^{n-1} T_{\text{avg}}(q) + an\]
שלב 4. הצבה של הנחת אינדוקציה \(T_{\text{avg}}(q) \leq cq\):
\[T_{\text{avg}}(n) \leq \frac{2}{n}\sum_{q=n/2}^{n-1} cq + an = \frac{2c}{n} \cdot \frac{(n/2 + n-1)(n/2)}{2} + an\]
(זהו טור אריתמטי עם \(n/2\) איברים, המינימום \(cn/2\), המקסימום \(c(n-1)\).)
שלב 5. פשטה אלגברית:
\[\leq c \cdot \frac{3n - 2}{4} + an = n\!\left(\frac{3c}{4} + a\right) - \frac{c}{2}\]
שלב 6. בחירת \(c\). נצליח להראות \(\leq cn\) אם:
\[\frac{3c}{4} + a \leq c \iff a \leq \frac{c}{4} \iff c \geq 4a\]
בחירה: \(c = \max\{b, 4a\}\) (כאשר \(b = T_{\text{avg}}(1)\), לבסיס האינדוקציה).
סיום:
\[T_{\text{avg}}(n) \leq cn - \frac{c}{2} \leq cn \quad \blacksquare\]
מסקנה
QuickSelect: Best/Avg \(\Theta(n)\), Worst \(\Theta(n^2)\). בפועל מהיר מאוד — קבועים קטנים, פשוט לקודד.
אבל ה-worst case \(\Theta(n^2)\) מטריד כשרוצים ערובה. למשל בקוד שמשרת לקוחות זרים — אסור שיהיה DoS.
9. Median of Medians — אלגוריתם Worst-case Θ(n)
בעיה מפורסמת ב-CS: מציאת חציון ב-worst-case לינארי. הפתרון נקרא BFPRT (Blum-Floyd-Pratt-Rivest-Tarjan, 1973). פלא של ניתוח אלגוריתמי.
הרעיון המרכזי
למה QuickSelect לא מספיק טוב?
כי הוא בוחר pivot שרירותי. אם בכל פעם נבחר pivot שמסומן
קרוב לחציון — אז כל partition יחתוך כמעט חצי, וסיבוכיות = \(\Theta(n)\). הקושי: איך לבחור pivot טוב
בלי לפתור את הבעיה המקורית?
Genius idea: נתפשר על pivot שטוב "מספיק" — מבטיח לפחות חיתוך 30%:70%. מבצעים ב-\(\Theta(n)\) רקורסיבי.
האלגוריתם
MM-Select(A, k):
1. if n < 10: compute median naïvely; return it
2. divide n elements into ⌊n/5⌋ groups Sᵢ of 5 each
3. find median sᵢ of each group Sᵢ naïvely // Θ(1) per group
4. x ← MM-Select({s₁, …, s_{n/5}}, n/10) // median of medians
5. q ← Partition(A) with x as pivot
6. if (q == k): return A[q]
7. if (k < q): return MM-Select(A[1..q−1], k)
else: return MM-Select(A[q+1..n], k − q)
למה pivot x מבטיח 30%/70%?
משפט — ערובת ה-pivot
ה-pivot \(x\) מבטיח לפחות \(3n/10\) איברים \(\leq x\) ולפחות \(3n/10\) איברים \(\geq x\).
הוכחה ויזואלית
- יש \(n/5\) קבוצות של 5 איברים, וחציוני הקבוצות \(s_1, \ldots, s_{n/5}\).
- בחרנו \(x\) כחציון של החציונים. אז חצי מהחציונים (\(n/10\)) קטנים-שווים ל-\(x\), וחצי גדולים-שווים.
- קח קבוצה \(S_i\) שבה \(s_i \leq x\). בקבוצה הזו, \(s_i\) הוא החציון של 5 איברים — אז 3 איברים בה (\(s_i\) ושני איברים קטנים ממנו) הם \(\leq s_i \leq x\).
- סך הכל: לפחות \((n/10) \times 3 = 3n/10\) איברים \(\leq x\).
- סימטרית: לפחות \(3n/10\) איברים \(\geq x\). ∎
מסקנה: ה-partition אחרי שלב 5 מבטיח שכל צד מכיל לכל היותר \(n - 3n/10 = 7n/10\) איברים. הקריאה הרקורסיבית בשלב 7 פועלת על גודל \(\leq 7n/10\).
ניתוח הזמן
משפט — MM-Select בזמן Θ(n)
\[T(n) \leq \begin{cases} T(n/5) + T(7n/10) + \Theta(n) & n \geq 10 \\ b & n < 10 \end{cases}\]
⟹ \(T(n) = O(n)\).
הוכחה (עץ רקורסיה)
הסיבה ש-\(T(n) = O(n)\): \(\frac{1}{5} + \frac{7}{10} = \frac{2 + 7}{10} = \frac{9}{10} < 1\).
בעץ הרקורסיה, בכל רמה \(i\), סך העבודה \(\leq (9/10)^i \cdot n\) (העבודה הלא-רקורסיבית מסכמת לטור גאומטרי).
\[T(n) \leq n \cdot \sum_{i=0}^{\infty} \left(\frac{9}{10}\right)^i = n \cdot \frac{1}{1 - 9/10} = 10n = O(n). \quad \blacksquare\]
למה דווקא קבוצות של 5?
- קבוצות של 3: \(T(n/3) + T(2n/3) + n = T(n) \cdot \log\)... ⟹ \(T(n) = \Theta(n \log n)\). לא מספיק!
- קבוצות של 5: \(\frac{1}{5} + \frac{7}{10} = 0.9 < 1\) ⟹ לינארי.
- קבוצות של 7: גם עובד, אבל הקבוע גדול יותר.
5 זה ה-sweet spot. זו בחירה לא טריוויאלית — המאמר המקורי הקדיש לזה ניתוח שלם.
💡 הקבוע ב-Θ(n) של MM-Select גדול בפועל
\(T(n) \leq 10n\) זה רק החסם העליון. הקבוע האמיתי כולל גם את העבודה של מציאת חציון של 5 איברים (לא חינם), והעבודה הרקורסיבית. בפועל
QuickSelect מהיר פי כמה מ-MM-Select כי הקבועים שלו קטנים.
MM-Select חשוב בעיקר תיאורטית: הוכחה לקיומו של אלגוריתם סלקציה ב-worst-case לינארי. בייצור משתמשים ב-QuickSelect עם בחירת pivot חכמה (random/median-of-three).
10. בונוס — תובנות מעמיקות לכל הפרק
💡 1. למה ה-Counting Sort דורש שלב הסכומים המצטברים?
אחרי שלב 2, יודעים
כמה מכל ערך יש — אבל לא
איפה כל אחד צריך להיכנס ב-B. הסכומים המצטברים נותנים את
המיקום הסופי האחרון של כל ערך. למשל C[3]=3 אומר "האחרון מבין השלשות יילך למיקום 3 ב-B".
בלי הסכומים — היינו צריכים סריקה נוספת לכל ערך, וזה כבר לא Θ(n).
💡 2. הקשר בין Counting Sort ו-Radix Sort
ב-Radix Sort, כל "שלב מיון לפי ספרה" משתמש ב-Counting Sort עם \(k\) קטן (לדוגמה 10 לעשרוני, 2 לבינארי, או \(n\) לבחירה אופטימלית). זה למה
Radix Sort דורש Stable Sort — וזה למה Counting Sort הוא הבחירה הטבעית.
💡 3. למה Bucket Sort לא מספיק?
למרות שהוא Θ(n) ממוצע, ההנחה של "התפלגות אחידה" קשה לקיים. נתונים מהעולם האמיתי כמעט אף פעם לא אחידים. לכן בפועל RadixSort/MergeSort יותר אמינים.
💡 4. QuickSelect vs MM-Select בפועל
| QuickSelect | MM-Select |
|---|
| Worst | \(\Theta(n^2)\) | \(\Theta(n)\) |
| Average | \(\Theta(n)\) | \(\Theta(n)\) |
| קבוע | קטן | גדול (≈ 10×) |
| שימוש | ייצור (random pivot) | גארנטיות תיאורטיות |
ההמלצה: QuickSelect עם random pivot — מעניק worst case \(O(n^2)\)
בהסתברות חסרת משמעות, וקבועים קטנים. זה מה ש-C++'s
std::nth_element משתמש.
💡 5. הקשר העמוק בין Sorting ל-Selection
סלקציה היא לפחות קלה כמו מיון (אפשר תמיד למיין ואז לבחור). השאלה:
האם היא קלה יותר?
- במודל ההשוואות: כן! Sorting דורש \(\Theta(n \log n)\), Selection \(\Theta(n)\).
- אבל: מציאת \(k\) האיברים הקטנים ביותר (לא רק ה-k-בגודלו) דורשת \(\Theta(n \log k)\) — בין סלקציה למיון.
💡 6. שאלת מבחן: למה לא ניתן ל-bound לעולם את QuickSelect ל-O(n) worst-case בלי MM-Select?
כל אלגוריתם שבוחר pivot ב-\(O(1)\) זמן (קצה / אקראי / כל בחירה לא-תלויה בערכי המערך) — יש קלט אדברסרי שגורם לפיצול גרוע. רק
בחירת pivot חכמה שעצמה דורשת \(\Omega(n)\) (כמו median-of-medians) יכולה לערוב partition מאוזן.
זו אבסטרקציה יפה: הזמן הלינארי של MM-Select מגיע "במחיר" עבודה לינארית בבחירת pivot — וזה משתלם רק כי בכל פעם הצמצום בגודל הבעיה הוא גם פקטור קבוע.