נתון מערך A בגודל n של מספרים ממשיים, שבו יכולות להיות כפילויות.
נסמן ב-m את מספר הערכים השונים המופיעים במערך A (m<n, m לא ידוע מראש).א) (12 נקודות) כתבו שגרה שמעתיקה את איברי מערך A לתוך מערך B[1..n] בסדר הבא:m הערכים המופיעים במערך- עותק אחד מכל ערך בסדר ממוין,
כל הערכים המופיעים במערך פעמיים או יותר- עותק אחד מכל ערך בסדר ממוין,
כל הערכים המופיעים במערך שלוש פעמים או יותר- עותק אחד מכל ערך בסדר ממוין, וכן הלאה.
פתרו בזמן O(nlogm). מותר להקצות מקום נוסף בגודל 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(nlogn).
מותר להקצות רק מערך אחד- מערך הפלט 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
הערות:- בשאלות אלגוריתמיות יש להקפיד על כתיבת רעיון, אלגוריתם, נכונות וסיבוכיות.
- אלגוריתם = שגרה = סדרת פקודות מוגדרות היטב בעברית או באנגלית.
- שימו לב לדייק בנכונות ובחישוב היעילות.
- כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.