תרגול 6 — Linear-time Sorting

0. תזכורת מהירה

מתי משתמשים במיון לינארי?

אלגוריתמי מיון מבוססי השוואות (Heap/Merge/Quick) הם הטובים ביותר כשאין מידע מוקדם על המערך — \(\Omega(n \log n)\).
אם יש מידע (טווח שלמים, התפלגות אחידה, מספר ספרות קבוע) — ניתן לעיתים \(\Theta(n)\).
חסם הטריוויאלי: כל מיון חייב \(\Omega(n)\) (חייב לקרוא את כל הקלט).

שלושת אלגוריתמי המיון הלינאריים

	תנאי שימוש	Worst	Average	Stable
Counting	שלמים ב-{1..k}	\(\Theta(n + k)\)	\(\Theta(n + k)\)	כן
Bucket	אחיד ב-[0, 1)	\(\Theta(n^2)\)	\(\Theta(n)\)	תלוי במיון פנימי
Radix	d ספרות, stable per digit	\(\Theta(d(n + k))\)	\(\Theta(d(n + k))\)	כן (אם הפנימי יציב)

CountingSort — Pseudocode מ-CLRS

CountingSort(A, n, k):
  let B[1:n] and C[0:k] be new arrays
  for i = 0 to k:
    C[i] = 0
  for j = 1 to n:
    C[A[j]] = C[A[j]] + 1       // C[i] = #elements equal to i
  for i = 1 to k:
    C[i] = C[i] + C[i − 1]      // C[i] = #elements ≤ i
  // Copy A to B, starting from end (לשמירת יציבות):
  for j = n downto 1:
    B[C[A[j]]] = A[j]
    C[A[j]] = C[A[j]] − 1
  return B

סיבוכיות: שני לולאות של \(\Theta(k)\) + שני לולאות של \(\Theta(n)\) = \(\Theta(n + k)\). אם \(k = O(n)\): \(\Theta(n)\).

RadixSort — Pseudocode

RadixSort(A, n, d):
  for i = 1 to d:
    use a stable linear sort (e.g., CountingSort) on A by digit i

סיבוכיות: \(\Theta(d(n + k))\) כאשר \(k\) = הבסיס של הספרה.

1. בסיסים מספריים — Decimal, Binary, ומה שביניהם

הבנה של בסיסים קריטית לפתרון שאלות Radix Sort במבחן. הספרות הן כלי, לא מטרה.

הרעיון

ספרות מציגות מספר כסכום של כפולות של חזקות.

במספרים עשרוניים (בסיס 10):

\[1234 = 1 \cdot 10^3 + 2 \cdot 10^2 + 3 \cdot 10^1 + 4 \cdot 10^0\]

בבינארי (בסיס 2):

\[10011010010_2 = 1 \cdot 2^{10} + 0 \cdot 2^9 + \ldots + 1 \cdot 2^1 + 0 \cdot 2^0 = 1234\]

בסיסים פופולריים

Decimal: בסיס 10 (האנושות 🙂).
Binary: בסיס 2 (המחשבים 💻).
Octal: בסיס 8.
Hexadecimal: בסיס 16 (זיכרון, צבעי RGB).
כל מספר טבעי יכול להיות בסיס. ב-Radix Sort נשתמש לעיתים בבסיס \(n\) (גודל המערך).

2. חישוב ספרות של מספר \(x > 0\) בבסיס \(b\)

הרעיון: Modulo + Division

השיטה

digits = array of size ⌈log_b x⌉, initialized to zeros
i = 0
while x > 0:
  digits[i] = x mod b
  x = ⌊x / b⌋
  i = i + 1

זמן ריצה: \(O(\log_b x)\) — מספר הספרות.

דוגמה: 1234 בבסיס 2

חישוב

x	x mod 2 (=digit)	⌊x/2⌋ (=next x)
1234	0	617
617	1	308
308	0	154
154	0	77
77	1	38
38	0	19
19	1	9
9	1	4
4	0	2
2	0	1
1	1	0

קוראים את הספרות מלמעלה למטה (LSB ראשון): 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1

קוראים מ-MSB לכיוון LSB: 1234₁₀ = 10011010010₂

בדיקה: \(2^{10} + 2^7 + 2^6 + 2^4 + 2^1 = 1024 + 128 + 64 + 16 + 2 = 1234\) ✓

תרגיל 1: מיון מערך ב-\([0, n^3 - 1]\) — איזה אלגוריתם?

השאלה

נתון מערך של \(n\) שלמים בטווח \([0, n^3 - 1]\). כל שלם נשמר ב-word יחיד (מודל Word-RAM).

הצע שיטה יעילה למיון, ונתח worst-case של:

אלגוריתם מבוסס השוואות (כמו QuickSort/MergeSort)
Counting Sort
Radix Sort

ניתוח של כל אופציה

אופציה 1: מיון מבוסס השוואות

\(\Omega(n \log n)\) (חסם תחתון מתאים גם ל-worst-case).

אופציה 2: Counting Sort

הטווח \(k = n^3\). סיבוכיות: \(\Theta(n + k) = \Theta(n + n^3) = \Theta(n^3)\). גרוע מאוד! מקום הזיכרון גם \(\Theta(n^3)\) — לא ריאלי.

אופציה 3: Radix Sort בבסיס 10

מספר ספרות: \(d = \log_{10}(n^3) = 3 \log_{10} n\). אז:

\[\Theta(d \cdot (n + k)) = \Theta(\log_{10} n \cdot (n + 10)) = \Theta(n \log n)\]

זה רק כמו מיון רגיל — לא משתלם!

אופציה 4 (המנצחת): Radix Sort בבסיס \(n\)

אם נשתמש בבסיס \(k = n\):

כל מספר ב-\([0, n^3 - 1]\) הוא בעל \(d = \log_n(n^3) = 3\) ספרות (קבוע!).
חישוב הספרות לכל מספר: \(O(3) = O(1)\). לכל המערך: \(O(n)\).
כל ספרה ב-\([0, n - 1]\) → Counting Sort בה הוא \(\Theta(n + n) = \Theta(n)\).
סך הכל: \(\Theta(d \cdot (n + k)) = \Theta(3 \cdot 2n) = \Theta(n)\). לינארי! 🎉

איך מבצעים מבחינה טכנית?

נניח \(n\) חזקה של 2 (אחרת לעבוד עם החזקה הקרובה). אז ניצול הייצוג הבינארי של המספרים:

כל מספר מיוצג כ-\(\log_2(n^3) = 3 \log_2 n\) ביטים.
נחלק את הביטים ל-3 בלוקים של \(\log_2 n\) ביטים — כל בלוק מייצג ספרה בבסיס \(n\).
בדוגמה: \(n = 1024 = 2^{10}\), מספרים ב-\([0, 2^{30}]\), כל מספר 30 ביטים, מחולקים ל-3 בלוקים של 10 ביטים כל אחד.

מיון לפי כל בלוק = Counting Sort על n=1024 ערכים אפשריים = \(\Theta(n)\).

💡 התובנה הגדולה

בחירת הבסיס משנה הכל! Radix Sort הוא לא רק על "ספרות עשרוניות". בחירת בסיס נכון יכולה להפוך אלגוריתם של \(\Theta(n \log n)\) לאלגוריתם של \(\Theta(n)\).

הכלל הזהוב: בחר את הבסיס \(b\) כך ש:

הטווח של המספרים \([0, b^d]\) עם \(d\) קבוע. אז \(d = O(1)\).
\(b = O(n)\), כדי שכל ספרה תהיה ניתנת למיון ב-Counting Sort ב-\(\Theta(n)\).

הכלל המעשי: אם הטווח של המספרים הוא \([0, n^c]\) לחזקה קבועה \(c\), הבחירה \(b = n\) נותנת \(\Theta(n)\).

תרגיל 2: Bucket Sort עם שתי התפלגויות

השאלה

נתונים \(n\) מספרים ממשיים:

חצי מהם מתפלגים אחיד ב-\([0, 1)\).
החצי האחר מתפלגים אחיד ב-\([1, 5)\).

איך להשתמש ב-Bucket Sort כדי למיין אותם ביעילות מקסימלית?

פתרון

הבעיה: אם נשתמש ב-\(n\) דליים שווי-גודל על \([0, 5)\) (כל דלי בגודל \(5/n\)):

חצי מהאיברים נופלים ב-\([0, 1)\) — שזה \(n/5\) דליים בלבד.
תוחלת מספר איברים בדלי בחלק זה: \(\frac{n/2}{n/5} = 2.5\). יוצא משוקלל לא טוב.

הרעיון: דליים לא שווי-גודל

נחלק את \([0, 5)\) ל-\(n\) דליים — אבל כל חצי מקבל \(n/2\) דליים שווי-גודל פנימה:

\(n/2\) דליים בגודל \(2/n\) על \([0, 1)\): הדלי \(i\) הוא \(\left[\frac{2i}{n}, \frac{2(i+1)}{n}\right)\) (לא! פשוט יותר):
- תיקון: \(n/2\) דליים בגודל \(1/(n/2) = 2/n\)... רגע, יש פה בלגן.

פתרון מדויק (לפי התרגול)

נחלק את \([0, 5)\) ל-\(n\) דליים לא שווים:

עבור \(0 \leq i < n/2\): דלי \(i\) על \(\left[\frac{2i}{n}, \frac{2(i+1)}{n}\right)\) — \(n/2\) דליים שווי-גודל ב-\([0, 1)\).
עבור \(n/2 \leq i < n\): דלי \(i\) על \(\left[1 + \frac{8(i - n/2)}{n}, 1 + \frac{8(i - n/2 + 1)}{n}\right)\) — \(n/2\) דליים שווי-גודל ב-\([1, 5)\) (גודל 8/n כל אחד).

עכשיו בשני החלקים המפתחות מתפלגים אחיד בתוך הדליים. תוחלת איברים בדלי בכל חלק:

\[\frac{n/2}{n/2} = 1\]

תוצאה: התפלגות אחידה ב-buckets ⟹ Bucket Sort רץ ב-\(\Theta(n)\) ממוצע.

💡 התובנה

Bucket Sort דורש לא הנחה של "התפלגות אחידה על כל הטווח" אלא "כמות צפויה דומה בכל דלי". אם הקלט בא משתי התפלגויות שונות, מתאימים את הדליים — לא הולכים שניהם מאותו גודל.

הרעיון מתרחב: גם להתפלגויות לא-אחידות מורכבות. למשל אם הקלט בא ממכפלת התפלגות עם פונקצית פיצוץ ידועה — בונים דליים לפי המקבלות של הפיצוץ.

תרגיל 3: \(k\) האיברים הקרובים לחציון ב-\(O(n)\)

השאלה

תאר אלגוריתם בזמן \(O(n)\) המקבל כקלט מערך \(A\) של \(n\) מספרים מובחנים ושלם חיובי \(k \leq n\) (נניח \(n\) אי-זוגי).

האלגוריתם מחזיר את \(k\) האיברים ב-\(A\) הקרובים ביותר לחציון של \(A\). המרחק בין שני מספרים \(x, y\) מוגדר \(|x - y|\).

פתרון

מצא את החציון: השתמש ב-MM-Select (Median of Medians) על \(A\) ב-\(O(n)\). תקרא לחציון \(m\).
חשב מרחקים: עבור על \(A\), בנה מערך חדש \(D\) של גודל \(n\): \(D[i] = |A[i] - m|\). זמן: \(\Theta(n)\).
מצא את ה-k-th order stat ב-D: השתמש שוב ב-MM-Select על \(D\) למציאת \(d_k\) = האיבר הקטן ה-k בגודלו ב-\(D\). זמן: \(O(n)\).
הפק את התוצאה: עבור על \(A\) שוב, החזר כל \(A[i]\) שבו \(|A[i] - m| \leq d_k\). זמן: \(\Theta(n)\).

סיבוכיות כוללת: \(O(n) + \Theta(n) + O(n) + \Theta(n) = O(n)\). ✓

💡 תבנית פתרון: "מצא k איברים שמקיימים תכונה X" בזמן O(n)

כשמבקשים "מצא k איברים" בזמן \(O(n)\), השלבים תמיד דומים:

הגדר ערך עזר לכל איבר (כאן: מרחק לחציון).
מצא את הסף — האיבר ה-k בגודלו של ערך העזר — בזמן \(O(n)\) באמצעות Selection.
סנן את האיברים שמתחת לסף ב-\(O(n)\).

הסוד: אסור למיין הכל (זה \(\Omega(n \log n)\)). שימוש ב-Select הוא הכרחי.

תרגיל 4: מבנה נתונים מיוחד למולטיסט

השאלה

עצב מבנה נתונים שמייצג multiset של \(n\) מספרים תחת הפעולות הבאות:

Build: \(\Theta(n)\)
Return median: \(\Theta(1)\)
Delete median: \(\Theta(\log n)\)

פתרון — שני heaps

הרעיון

נשמור שני heaps:

Max-Heap \(H_1\): \(\lceil n/2 \rceil\) הקטנים ביותר (השורש = הגדול ביותר מהקטנים → חציון).
Min-Heap \(H_2\): \(\lfloor n/2 \rfloor\) הגדולים ביותר (השורש = הקטן ביותר מהגדולים).

אינווריאנט: כל איבר ב-\(H_1\) \(\leq\) כל איבר ב-\(H_2\).

Build (\(\Theta(n)\))

מצא את החציון בשיטת MM-Select: \(\Theta(n)\).
בצע partition סביב החציון (כמו ב-QuickSort): \(\Theta(n)\). שתי חצאים: קטנים-שווים לחציון, וגדולים-שווים.
בנה Max-Heap על החצי הקטן: \(\Theta(n/2) = \Theta(n)\) (BuildHeap לינארי).
בנה Min-Heap על החצי הגדול: \(\Theta(n)\).

סך הכל: \(\Theta(n)\). ✓

Return median (\(\Theta(1)\))

אם \(n\) אי-זוגי: החציון הוא השורש של ה-heap הגדול יותר (\(H_1\) או \(H_2\)). \(O(1)\) גישה.
אם \(n\) זוגי: שני חציונים, השורשים של שני ה-heaps.

Delete median (\(\Theta(\log n)\))

אם \(n\) אי-זוגי: extract-max מ-\(H_1\) (ה-heap הגדול יותר). זמן: \(\Theta(\log n)\). אחרי המחיקה, ה-heaps שווים.
אם \(n\) זוגי: extract-min מ-\(H_2\) (כדי לאזן — אחרת ה-Max-Heap יישאר גדול יותר). זמן: \(\Theta(\log n)\).

הסוד: אחרי כל מחיקה, האינווריאנט נשמר (כל \(H_1\) ≤ כל \(H_2\)), והגודלים נשארים מאוזנים (הפרש לכל היותר 1).

💡 הרחבה — Two-Heaps Streaming Median

המבנה הזה מורחב לאלגוריתם streaming median: בכל זמן, ניתן להוסיף איבר חדש ולהחזיר את החציון העדכני. פעולה Insert ב-\(\Theta(\log n)\):

אם האיבר \(\leq\) חציון הנוכחי: הוסף ל-\(H_1\) (Max-Heap).
אחרת: הוסף ל-\(H_2\) (Min-Heap).
אם ההפרש בגדלים יותר מ-1: העבר את השורש מה-heap הגדול ל-heap הקטן.

שאלה קלאסית ב-coding interviews ב-Google/Facebook.

5. טיפים לקראת המבחן

💡 טיפ 1 — זיהוי "Linear Time" במבחן

כשנותנים לך טווח של מספרים מסוים, תמיד שאל את עצמך:

שלמים? → Counting Sort או Radix Sort.
טווח קטן (\(k = O(n)\))? → Counting Sort.
טווח גדול (\(k = n^c\))? → Radix Sort בבסיס \(n\).
מספרים ממשיים עם התפלגות ידועה? → Bucket Sort.

💡 טיפ 2 — איך לבחור את הבסיס ב-Radix Sort?

טווח המספרים = \([0, M]\)?
בסיס \(b\) → מספר ספרות \(d = \lceil \log_b M \rceil\).
סיבוכיות = \(\Theta(d(n + b))\).
אופטימום: \(b = O(n)\) → \(d(n + n) = 2dn\) → אם \(d = O(1)\), זה \(\Theta(n)\).
מתי \(d = O(1)\)? כאשר \(M \leq n^c\) לחזקה קבועה \(c\). אז בסיס \(n\) נותן \(d = c = O(1)\).

💡 טיפ 3 — Order Statistics לחיים

כל בעיה שמבקשת "מצא k איברים שעונים על תכונה" או "מצא איבר במיקום מסוים":

הגדר ערך עזר \(D[i] = f(A[i])\) (כאן ה-f מבוסס על "התכונה").
השתמש ב-Select למציאת הערך ה-k-בגודלו ב-D.
סנן ב-O(n).

אל תמיין הכל — זה \(\Omega(n \log n)\).

💡 טיפ 4 — שאלות עם hybrid data structures

כשמבקשים מבנה נתונים עם הרבה דרישות (Build O(n) + Median O(1) + Delete O(log n)):

חשוב על שתי מבני נתונים שונים שכל אחד תורם משהו (כאן: Max-Heap + Min-Heap).
הקפד על אינווריאנט בין שני המבנים (כאן: כל H1 ≤ כל H2).
הסבר איך כל פעולה מקיימת את האינווריאנט.

תבניות נוספות: סיגריס + Hash Table (BST + Hash for fast both ordered and unordered lookup), Stack + Min-Stack (לתחזק מינימום ב-O(1)).

💡 טיפ 5 — סדר אלגוריתמי המיון לזכרון

אלגוריתם	Worst	תזכור
Insertion	n²	פשוט, in-place, יציב
Heap	n log n	in-place, לא יציב
Merge	n log n	O(n) זיכרון, יציב
Quick	n²	אך average n log n, in-place
Counting	n+k	שלמים ב-{1..k}
Bucket	n²	אך average n, אחיד
Radix	d(n+k)	d ספרות

תרגול 6 — Linear-time Sorting

תוכן עניינים

0. תזכורת מהירה

שלושת אלגוריתמי המיון הלינאריים

CountingSort — Pseudocode מ-CLRS

RadixSort — Pseudocode

1. בסיסים מספריים — Decimal, Binary, ומה שביניהם

בסיסים פופולריים

2. חישוב ספרות של מספר \(x > 0\) בבסיס \(b\)

הרעיון: Modulo + Division

דוגמה: 1234 בבסיס 2

תרגיל 1: מיון מערך ב-\([0, n^3 - 1]\) — איזה אלגוריתם?

אופציה 1: מיון מבוסס השוואות

אופציה 2: Counting Sort

אופציה 3: Radix Sort בבסיס 10

אופציה 4 (המנצחת): Radix Sort בבסיס \(n\)

תרגיל 2: Bucket Sort עם שתי התפלגויות

הרעיון: דליים לא שווי-גודל

פתרון מדויק (לפי התרגול)

תרגיל 3: \(k\) האיברים הקרובים לחציון ב-\(O(n)\)

תרגיל 4: מבנה נתונים מיוחד למולטיסט

הרעיון

Build (\(\Theta(n)\))

Return median (\(\Theta(1)\))

Delete median (\(\Theta(\log n)\))

5. טיפים לקראת המבחן