שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2025 - מיון

נתון מערך $A$ בגודל $n$ של מספרים ממשיים, שבו יכולות להיות כפילויות. נסמן ב-$m$ את מספר הערכים השונים המופיעים במערך $A$ ($m < n$, $m$ לא ידוע מראש). א) (12 נקודות) כתבו שגרה שמעתיקה את איברי מערך $A$ לתוך מערך $B[1..n]$ בסדר הבא: $m$ הערכים המופיעים במערך- עותק אחד מכל ערך בסדר ממוין, כל הערכים המופיעים במערך פעמיים או יותר- עותק אחד מכל ערך בסדר ממוין, כל הערכים המופיעים במערך שלוש פעמים או יותר- עותק אחד מכל ערך בסדר ממוין, וכן הלאה. פתרו בזמן $O(n \log m)$. מותר להקצות מקום נוסף בגודל $O(n)$. דוגמא: בהינתן המערך $A$ הבא- ``` 5 7 3 1 1 5 5 3 1 3 3 2 4 ``` נקבל- ``` 1 2 3 4 5 7 1 3 5 1 3 5 3 ``` ב) (13 נקודות) כתבו שגרה שמעתיקה את איברי מערך $A$ לתוך מערך $B[1..n]$ בסדר הבא: ערכי האיברים ששכיחותם היא הגבוהה ביותר- את כל העותקים ובסדר ממוין, ערכי האיברים ששכיחותם היא השנייה בגודלה- את כל העותקים ובסדר ממוין, ערכי האיברים ששכיחותם היא השלישית בגודלה- את כל העותקים ובסדר ממוין, וכן הלאה. פתרו בזמן $O(n \log n)$. מותר להקצות רק מערך אחד- מערך הפלט $B$ באורך $n$. אבל מותר שכל איבר בו יכיל כמה שדות. דוגמא: בהינתן המערך $A$ הבא- ``` 5 7 3 1 1 5 5 3 1 3 3 2 4 ``` נקבל- ``` 3 3 3 3 1 1 1 5 5 5 2 4 7 ``` הערות: * בשאלות אלגוריתמיות יש להקפיד על כתיבת רעיון, אלגוריתם, נכונות וסיבוכיות. * אלגוריתם = שגרה = סדרת פקודות מוגדרות היטב בעברית או באנגלית. * שימו לב לדייק בנכונות ובחישוב היעילות. * כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.

רמז: לסעיף א', השתמשו במבנה נתונים יעיל (כמו עץ חיפוש מאוזן) כדי למנות את שכיחות האיברים ולאחר מכן לבנות את הפלט. לסעיף ב', בצעו את כל החישובים "במקום" על גבי מערך הפלט B, החל מהעתקה ומיון של הנתונים, דרך כיווץ לזוגות (ערך, שכיחות), מיון הזוגות, והרחבה חזרה.

פתרון: ### סעיף א) **רעיון** הרעיון הוא להשתמש במבנה נתונים יעיל כדי למנות את השכיחויות של כל האיברים השונים במערך $A$. **עץ חיפוש בינארי מאוזן (Balanced BST)**, כגון עץ אדום-שחור, מתאים למטרה זו. נאחסן בעץ זוגות של (ערך, שכיחות). לאחר סריקה של כל מערך $A$ ובניית העץ, יהיו לנו $m$ צמתים בעץ, כאשר כל צומת מייצג ערך ייחודי ואת מספר הפעמים שהוא מופיע. לאחר מכן, ניצור מערך של רשימות, כאשר הרשימה במקום ה-$k$ תחזיק את כל הערכים המופיעים במערך $A$ לפחות $k$ פעמים, בסדר ממוין. נוכל לאכלס רשימות אלו ביעילות על ידי סריקה סדורה (in-order traversal) של עץ החיפוש. סריקה כזו תיתן לנו את הערכים השונים בסדר ממוין. עבור כל ערך $v$ עם שכיחות $c$, נוסיף את $v$ לרשימות $1, 2, \dots, c$. לבסוף, נשרשר את כל הרשימות לפי הסדר (רשימה 1, אחריה רשימה 2, וכן הלאה) כדי לקבל את מערך הפלט $B$. **אלגוריתם** 1. צור עץ חיפוש בינארי מאוזן ריק, $T$, שיאחסן זוגות (ערך, שכיחות). 2. עבור על כל איבר $x$ במערך $A$: א. חפש את $x$ ב-$T$. ב. אם $x$ נמצא עם שכיחות $c$, עדכן את שכיחותו ל-$c+1$. ג. אם $x$ לא נמצא, הכנס צומת חדש $(x, 1)$ ל-$T$. 3. צור מערך $L$ בגודל $n+1$ של רשימות מקושרות ריקות. 4. בצע סריקה סדורה (in-order) על העץ $T$. עבור כל צומת $(v, c)$ שפוגשים: א. עבור $k$ מ-$1$ עד $c$, הוסף את הערך $v$ לסוף הרשימה $L[k]$. 5. צור מערך פלט $B$ בגודל $n$. אתחל אינדקס $i_B = 0$. 6. עבור $k$ מ-$1$ עד $n$: א. עבור כל איבר $x$ ברשימה $L[k]$ (לפי סדר הופעתם): i. קבע $B[i_B] = x$. ii. קדם את $i_B$ ב-1. 7. החזר את $B$. **הוכחת נכונות** שלבים 1-2 מונים נכונה את שכיחות כל אחד מ-$m$ הערכים השונים ב-$A$ ומאחסנים אותם ב-$T$. מאחר ש-$T$ הוא עץ חיפוש, ערכיו ייחודיים. שלב 4 מבצע סריקה סדורה על $T$, ולכן הערכים $v$ מעובדים בסדר עולה. עבור כל ערך $v$ עם שכיחות $c$, האלגוריתם מוסיף את $v$ לרשימות $L[1], L[2], \dots, L[c]$. כתוצאה מכך, בסוף שלב זה, כל רשימה $L[k]$ מכילה בדיוק את כל הערכים ששכיחותם היא לפחות $k$. מכיוון שהערכים מוספים לרשימות לפי סדר הסריקה הסדורה, כל רשימה $L[k]$ תהיה ממוינת. שלבים 5-7 בונים את מערך הפלט $B$ על ידי שרשור הרשימות $L[1], L[2], \dots$ לפי הסדר. זה בדיוק המבנה הנדרש בשאלה: תחילה כל הערכים המופיעים לפחות פעם אחת (ממוינים), לאחר מכן כל הערכים המופיעים לפחות פעמיים (ממוינים), וכן הלאה. סך כל האיברים שיוכנסו ל-$B$ הוא $\sum_{v} \text{count}(v) = n$, ולכן המערך $B$ יתמלא במלואו. $\blacksquare$ **ניתוח סיבוכיות** * **זמן ריצה:** * שלב 2: מבצע $n$ פעולות על עץ חיפוש מאוזן המכיל לכל היותר $m$ איברים. כל פעולה (חיפוש, הכנסה, עדכון) לוקחת $O(\log m)$ זמן. סה"כ: $O(n \log m)$. * שלב 3: אתחול מערך של רשימות לוקח $O(n)$. * שלב 4: סריקה סדורה של עץ עם $m$ צמתים לוקחת $O(m)$. מספר פעולות ההוספה הכולל לכל הרשימות הוא $\sum_{i=1}^{m} c_i = n$. כל הוספה לסוף רשימה מקושרת לוקחת $O(1)$. סה"כ: $O(m+n) = O(n)$. * שלב 6: מעבר על כל האיברים בכל הרשימות. סך האיברים הוא $n$, לכן שלב זה לוקח $O(n)$. * **סה"כ זמן ריצה:** $O(n \log m) + O(n) + O(n) = O(n \log m)$. * **סיבוכיות מקום:** * עץ החיפוש $T$ דורש $O(m)$ מקום. * מערך הרשימות $L$ מאחסן בסך הכל $n$ איברים. לכן דורש $O(n)$ מקום. * מערך הפלט $B$ דורש $O(n)$ מקום. * **סה"כ מקום נוסף:** $O(m) + O(n) = O(n)$. הפתרון עומד בדרישות הזמן והמקום. ### סעיף ב) **רעיון** בסעיף זה, מגבלת המקום הדוקה יותר ומתירה שימוש במערך הפלט $B$ בלבד. הרעיון הוא להשתמש ב-$B$ לכל שלבי החישוב. נאפשר לכל איבר ב-$B$ להכיל שני שדות: (ערך, שכיחות). 1. ראשית, נעתיק את איברי $A$ לתוך שדה ה'ערך' של איברי $B$, ואז נמיין את $B$ לפי ערך. המיון יקבץ יחד את כל המופעים של כל מספר. 2. לאחר מכן, נסרוק את $B$ הממוין ונכווץ אותו: נחשב את השכיחות של כל ערך ייחודי ונשמור את זוגות ה-(ערך, שכיחות) בתחילת המערך $B$. לאחר שלב זה, $B[0..m-1]$ יכיל את $m$ הזוגות הייחודיים. 3. כעת, נמיין את $m$ הזוגות הללו (שנמצאים ב-$B[0..m-1]$) לפי מפתח מיון מורכב: מפתח ראשי הוא **השכיחות** (בסדר יורד), ומפתח משני הוא **הערך** (בסדר עולה). 4. לבסוף, נרחיב את המערך המכווץ והממוין בחזרה למערך בגודל $n$. נעשה זאת על ידי סריקת $m$ הזוגות מהסוף להתחלה, וכתיבת האיברים למערך $B$ מהסוף ($B[n-1]$) להתחלה. טכניקה זו מונעת דריסה של נתונים שטרם קראנו. **אלגוריתם** 1. הקצה מערך $B$ בגודל $n$, כאשר כל תא ב-$B$ הוא מבנה (או זוג) היכול להכיל `value` ו-`count`. 2. העתק את המערך $A$ ל-$B$: עבור $i=0$ עד $n-1$, קבע $B[i].\text{value} = A[i]$. 3. מיין את המערך $B$ בסדר עולה לפי שדה ה-`value` של איבריו. השתמש באלגוריתם מיון בסיבוכיות $O(n \log n)$ (למשל, מיון מיזוג). 4. כווץ את $B$: אתחל אינדקס כתיבה $write\_idx = 0$ ואינדקס קריאה $read\_idx = 0$. א. כל עוד $read\_idx < n$: i. שמור $v = B[read\_idx].\text{value}$. ii. אתחל $c = 0$. iii. כל עוד $read\_idx < n$ וגם $B[read\_idx].\text{value} == v$: קדם את $read\_idx$ ו- $c$. iv. קבע $B[write\_idx].\text{value} = v$ ו- $B[write\_idx].\text{count} = c$. v. קדם את $write\_idx$. ב. שמור את מספר האיברים הייחודיים: $m = write\_idx$. 5. מיין את $m$ האיברים הראשונים של $B$, כלומר את התת-מערך $B[0..m-1]$. פונקציית ההשוואה בין שני זוגות $p_1=(v_1, c_1)$ ו-$p_2=(v_2, c_2)$ תהיה: א. אם $c_1 \neq c_2$, החזר את תוצאת ההשוואה $c_2 - c_1$ (מיון בסדר יורד לפי שכיחות). ב. אחרת (אם $c_1=c_2$), החזר את תוצאת ההשוואה $v_1 - v_2$ (מיון בסדר עולה לפי ערך). 6. הרחב את $B$ לפורמט הסופי: אתחל אינדקס כתיבה $write\_idx = n-1$. א. עבור $i$ מ-$m-1$ עד $0$ (בסדר יורד): i. שמור $v = B[i].\text{value}$ ו- $c = B[i].\text{count}$. ii. עבור $j$ מ-$1$ עד $c$: - קבע $B[write\_idx].\text{value} = v$. - הקטן את $write\_idx$ ב-1. 7. החזר את $B$ (ליתר דיוק, את הערכים שבשדה ה-`value` של איבריו). **הוכחת נכונות** שלבים 2-3 יוצרים עותק של $A$ ב-$B$ וממיינים אותו, מה שמקבץ איברים זהים יחדיו. שלב 4 סורק את $B$ הממוין ומונה נכונה את שכיחות כל ערך, ושומר את $m$ הזוגות (ערך, שכיחות) בתחילת המערך $B$. שלב 5 ממיין את הזוגות הללו לפי הכלל הנדרש: תחילה לפי שכיחות יורדת, ובתוך כל קבוצת שכיחות, לפי ערך עולה. שלב 6 בונה את הפלט. הוא רץ על הזוגות הממוינים מהסוף להתחלה וכותב ל-$B$ מהאינדקס $n-1$ אחורה. מאחר ש-$m<n$, אינדקס הכתיבה $write\_idx$ תמיד יהיה גדול מאינדקס הקריאה $i$, ולכן לא תהיה דריסת מידע לפני השימוש בו. התוצאה הסופית ב-$B$ תהיה רשימת כל המופעים של האיברים, מסודרים לפי קבוצות שכיחות יורדות, ובתוך כל קבוצה לפי ערך עולה. $\blacksquare$ **ניתוח סיבוכיות** * **זמן ריצה:** * שלב 2 (העתקה): $O(n)$. * שלב 3 (מיון ראשוני): $O(n \log n)$. * שלב 4 (כיווץ): סריקה לינארית אחת של המערך $B$. $O(n)$. * שלב 5 (מיון זוגות): מיון $m$ איברים. $O(m \log m)$. * שלב 6 (הרחבה): סך כל האיברים הנכתבים הוא $n$. $O(n)$. * **סה"כ זמן ריצה:** מאחר ש-$m < n$, הביטוי הדומיננטי הוא $O(n \log n)$. * **סיבוכיות מקום:** * האלגוריתם משתמש אך ורק במערך $B$ בגודל $n$ שהוקצה עבור הפלט. אין שימוש במערכי עזר נוספים שתלויים בגודל הקלט. המקום הנוסף הנדרש הוא $O(1)$ (או $O(\log n)$ עבור ערימת הקריאות של המיון הרקורסיבי). הפתרון עומד בדרישות הזמן והמקום.