בהינתן מערך A בגודל \(n\) שכל איבר בו הוא אחד מהערכים: 0, 1, או 2, נדון בדרכים שונות למיין את המערך.

א. מה המקרה הגרוע ביותר ומה המקרה הטוב ביותר של מיון הכנסה על קלט מסוג זה? הסבירו.

ב. מיינו את המערך A באמצעות שתי קריאות ל-Partition(A,p,r). לפני כל קריאה מותר לכם לבצע מעבר יחיד על הקלט כדי להחליט על איבר שיוצב במקום האחרון במערך (באינדקס r). קבעו מהם האינדקסים p ו-r שעליכם לשלוח בכל פעם. הסבירו בקצרה את תשובתכם.

ג. השתמשו במיון מניה. מה גודל מערכי העזר (B ו-C) בהם תשתמשו? מה זמן הריצה המתקבל?

ד. איזה מבין המיונים שלעיל יציב?

הערות:

• שגרת Partition מופיעה בספר הלימוד בעמוד 122.
• האינדקס הראשון של המערך A הוא 1.
• בכל הסעיפים, מערך הקלט הוא מערך בו כל מספר הוא 0, 1, או 2.