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

just2click

New member
עזרה בפתרון הבעיה הבאה (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

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

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

just2click

New member
כמובן

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

DNile

New member
למעשה,

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