עזרה בפתרון הבעיה הבאה (Java)

[just2click]

עזרה בפתרון הבעיה הבאה (Java)

יש לי רשימה שמכילה n איברים, ערכו של כל איבר הוא אקראי ויכול להיות 1 או 2 או 3 למשל: 1 3 3 2 1 1 2 3 1 2 1 ... בנוסף יש לי שתי פונקציות: הראשונה (getValue(i מחזירה לי האם בתא i יש 1 או 2 או 3. השניה (switch(i, j שמחליפה בין האיברים במיקומים i ו j. צריך למיין את הרשימה כך שתהיה מסודרת בצורה הבאה: 1 1 1 1 ... 1 2 2 2 2 ... 2 3 3 3 3 ... 3 מותר להפעיל כל פונקציה נתונה (getValue ו switch) מקסימום n פעמים. כמו כן חובה שהפתרון לא יסתמך על גודל הרשימה המקורית, כלומר, כמות הזכרון שהפתרון ישתמש בה צריכה להיות קבועה ובלתי תלויה ברשימה. בתודה מראש

 

[yaakov77]

האם מותר להקצות משתנים?

כמו כן לא הבנתי את הדרישה האחרונה. נא לפרט.

 

[just2click]

כמובן

מותר להקצות משתנים. המגבלה האחרונה באה להבטיח שלא תיצור למשל שלוש רשימות חדשות ותחבר אותן או שלא תיצור מערך בגודל הרשימה ותעביר איברים אליו. כמו שזה נראה לי יש לקרוא ל getValue לפחות פעם אחת עבור על תא ברשימה (אולי בלי התא האחרון) ולפונקציה שמחליפה את התאים אפילו פחות מזה. ושוב תודה.

 

[DNile]

למעשה,

כל אלגוריתם מיון המתבסס על החלפות איברים יכול להתאים. לדוגמה? bubble sort. חוץ מזה, אתה יכול להתאים אלגוריתם מיוחד לצרכים שלך.דוגמה? אפשר לעשות אלגוריתם שרץ פעמיים על המערך, בפעם הראשונה הוא ממקם את כל האחדות במקומם המתאים(על ידי החלפות בין האחדות בקדמת הרשימה לאיברים בסוף הרשימה), ובפעם השניה למקם את השתיימים(

) במקומם, שוב פעם, על ידי החלפות עם השלושים.