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

נתון מערך בן N תאים כשבו יש את הספרות 0,1,2. יש לסדר את המערך כך שכל האפסים יהיו בהתחלה, אחריהם יבואו האחדים, ואחריהם יבואו ה-2.
מגבלות:
מותר לעבור בכל תא של המערך אך ורק פעם אחת. אין להשתמש במערך עזר.
רמז: יש להשתמש ב 3 אינדקסים, אינדקס לכל סוג ספרה.

יש לך כיוון התחלתי?
(בכל זאת שיעורי בית )

תומר

תפעול מכשירים, סלולרי וגאדג'טים

"לעבור" הכוונה "לקרוא את תוכנו", כן? ולא להצבה של ערך חדש...

אם כן, צור לעצמך משתנים i, j, k ותציב בהם 0

לולאת for פשוטה מ 0 עד N-1

בכל איטרציה של הלולאה, switch על התא הנוכחי במערך. אם 0, אז i++. אם 1, אז j++, אם 2, אז k++.

לאחר מכן:
הצב l = 0

while על i > 0, שמבצע בלוק שעושה i-- ומציב במערך 0 בתא הנוכחי של המערך [l] ואז עושה l++
while על j > 0, שמבצע בלוק שעושה j-- ומציב במערך 1 בתא הנוכחי של המערך [l] ואז עושה l++
while על k > 0, שמבצע בלוק שעושה k-- ומציב במערך 2 בתא הנוכחי של המערך [l] ואז עושה l++

כל זה בהנחה שההנחה הראשונית שלי נכונה. אחרת העניין לא ברור לי, אבל אולי אני מפספס משהו כי אני ממש עייף.

נמאס לכם לזכור סיסמאות? לחצו כאן!

שזה נקרא לעבור פעמיים על המערך.

(יכול להיות שאני טועה, אבל אז אין טעם לתרגיל, אין פה שום תחכום או משהו מיוחד, פשוט לספור ולדרוס ערכים)

גם אני הבנתי את זה ככה.
ונראה לי שהכיוון הוא לעבור על המערך, וכל פעם לשמור את המקום האחרון של כל אחד מהמספרים, ולהחליף בינהם בהתאם, כך שבכל שלב התאים שעברנו עליהם ממוינים.

תומר

תפעול מכשירים, סלולרי וגאדג'טים

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

וגם לא ברור איך אתה משתמש באינדקסים שרמזו לו להשתמש...

אני חושב שהמטרה שלהם הייתה לאסור עליו להשתמש במיון בועות...

אבל אדרבה, אשמח לראות אלגוריתם שרק קורא, או רק כותב, למערך, והופך אותו לממויין.

נמאס לכם לזכור סיסמאות? לחצו כאן!

התכוונתי שיהיו שלושה אינדקסים שכל אחד מהם יצביע למיקום של האיבר האחרון שראינו בהתאם.
לדוגמה, אינדקס one יצביע למיקום האחרון שהספרה 1 הופיע במערך, כי כל שאר ה1 כבר במקומם.
זה כיוון...

תומר

תפעול מכשירים, סלולרי וגאדג'טים

לפי הרמז זה נראה לי בדיוק הכוונה

תרגיל מוזר

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://fresh.clanteam.com/list.png]

[התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://fresh.clanteam.com/?https://2010-uploaded.fresh.co.il/2010/09/21/52868411.gif,http://www.boredpanda.com/blog/wp-content/themes/mimbo2.2/images/subscribe-panda-605px.png]

עריכה: רק עכשיו שמתי לב שהדרישה היא לעבור על כל תא רק פעם אחת, לא על המערך כולו פעם אחת, כל התשובה שלי לא שווה כלום - משהו בשאלה לא הגיוני, אין אף דרך לדעת איפה מתחיל/נגמר האחד אם לא עוברים על איברים לפני.

אני מנסה לחשוב על כיוון - אפשר לשים אינדקס עולה בתחילת המערך ואינדקס יורד בסופו, נבדוק רק את ה0 וה2 ונתעלם מה1, בהפרש שישאר יהיה אחד.

קוד PHP:

 int i,j,k;
i=0;
j=N-1;
k=i;
while (arr[i]==0 && i<=j)
{
   i++   //נדלג על כל האפסים בהתחלה אם הם קיימים
}
while (arr[j]==2 && j>=0)
{
   j++;  //נדלג על כל ה2 בסוף אם הם קיימים
}

k=i+1;
while (i<j || k<j)
{
   if (arr[i]==0)
   {
       i++;
       if (i==k)
           k++;
   }
   else if (arr[j]==2)
      j--;
   }
   else if(arr[i]==2 && arr[j]==0)
   {  
       switch(arr[i],arr[j]);
       i++;
       if (i==k)
            k++;
       j--;
   }
   else if (arr[i]==1 && arr[k]==0)
   {
      switch (arr[i],arr[k]);
      i++;
      k++;
    }
   else if (arr[j]==1 && arr[k]==2)
   {
      switch (arr[j],arr[k]);
      j--;
      k++;
    }
   else if (arr[j]==0 && arr[i]==1)
   {
      arr[i]=0;
       i++;
      k++;    //we already know that k==1, no need to check,and we keep j on 1
    }
   else if (arr[j]==1 && arr[i]==2)
   {
      arr[j]=2;
       j--;
      n++;    //we already know that k==1, no need to check,and we keep i on 1
    }
} 


אני לא בטוח שאין פה טעויות, זה גם לא ב100% ריצה אחת על המערך אבל זה הכי קרוב שאני יכול לחשוב.

הגלריה שלי בפליקר

לא נופל לי האסימון.. אתה יכול לסביר קצת במילים מה הרעיון?

צריך להיות --j ולא ++j

קוד:

        public static void Switch(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }

        public static void Sort(int[] a)
        {
            int i = 0, j = a.Length - 1, k = -1;
            while (i <= j)
            {
                if (a[i] == 0 && a[j] == 0)
                {
                    if (k > -1)
                    {
                        Switch(ref a[k], ref a[i]);
                        k++;
                    }
                    i++;
                    while (i <= j && a[i] != 2)
                    {
                        if (a[i] == 0)
                        {
                            if (k > -1)
                            {
                                Switch(ref a[k], ref a[i]);
                                k++;
                            }
                        }
                        else if (a[i] == 1)
                        {
                            if (k == -1)
                            {
                                k = i;
                            }
                        }
                        i++;                        
                    }
                    if (i > j)
                    {
                        break;
                    }
                    else
                    {
                        Switch(ref a[i], ref a[j]);
                        if (k > -1)
                        {
                            Switch(ref a[k], ref a[i]);
                            k++;
                        }
                        i++;
                        j--;
                    }
                }
                else if (a[i] == 0 && a[j] == 1)
                {
                    if (k > -1)
                    {
                        Switch(ref a[k], ref a[i]);
                        k++;
                    }
                    i++;
                    while (i <= j && a[i] != 2)
                    {
                        if (a[i] == 0)
                        {
                            if (k > -1)
                            {
                                Switch(ref a[k], ref a[i]);
                                k++;
                            }
                        }
                        else if (a[i] == 1)
                        {
                            if (k == -1)
                            {
                                k = i;
                            }
                        }
                        i++;
                    }
                    if (i > j)
                    {
                        break;
                    }
                    else
                    {
                        Switch(ref a[i], ref a[j]);
                        if (k == -1)
                        {
                            k = i;
                        }
                        i++;
                        j--;
                    }
                }
                else if (a[i] == 0 && a[j] == 2)
                {
                    if (k > -1)
                    {
                        Switch(ref a[k], ref a[i]);
                        k++;
                    }
                    i++;
                    j--;
                }
                else if (a[i] == 1 && a[j] == 0)
                {
                    if (k == -1)
                    {
                        k = i;
                    }                                    
                    i++;
                    while (i <= j && a[i] != 2)
                    {
                        if (a[i] == 0)
                        {
                            if (k > -1)
                            {
                                Switch(ref a[k], ref a[i]);
                                k++;
                            }
                        }
                        else if (a[i] == 1)
                        {
                            if (k == -1)
                            {
                                k = i;
                            }
                        }
                        i++;
                    }
                    if (i > j)
                    {
                        break;
                    }
                    else
                    {
                        Switch(ref a[i], ref a[j]);
                        if (k > -1)
                        {
                            Switch(ref a[k], ref a[i]);
                            k++;
                        }
                        i++;
                        j--;
                    }
                }
                else if (a[i] == 1 && a[j] == 1)
                {
                    if (k == -1)
                    {
                        k = i;
                    }
                    i++;
                    while (i <= j && a[i] != 2)
                    {
                        if (a[i] == 0)
                        {
                            if (k > -1)
                            {
                                Switch(ref a[k], ref a[i]);
                                k++;
                            }
                        }
                        else if (a[i] == 1)
                        {
                            if (k == -1)
                            {
                                k = i;
                            }
                        }
                        i++;
                    }
                    if (i > j)
                    {
                        break;
                    }
                    else
                    {
                        Switch(ref a[i], ref a[j]);
                        if (k == -1)
                        {
                            k = i;
                        }
                        i++;
                        j--;
                    }
                }
                else if (a[i] == 1 && a[j] == 2)
                {
                    if (k == -1)
                    {
                        k = i;
                    }
                    i++;
                    j--;
                }
                else if (a[i] == 2 & a[j] == 0)
                {
                    Switch(ref a[i], ref a[j]);
                    if (k > -1)
                    {
                        Switch(ref a[k], ref a[i]);
                        k++;
                    }
                    i++;
                    j--;
                }
                else if (a[i] == 2 && a[j] == 1)
                {
                    Switch(ref a[i], ref a[j]);
                    if (k == -1)
                    {
                        k = i;
                    }
                    i++;
                    j--;
                }
                else if (a[i] == 2 & a[j] == 2)
                {
                    j--;
                    while (i <= j && a[j] == 2)
                    {
                        j--;
                    }
                    if (i > j)
                    {
                        break;
                    }
                    else
                    {
                        Switch(ref a[i], ref a[j]);
                        if (a[i] == 0)
                        {
                            if (k > -1)
                            {
                                Switch(ref a[k], ref a[i]);
                                k++;
                            }
                        }
                        else if (a[i] == 1)
                        {
                            if (k == -1)
                            {
                                k = i;
                            }
                        }
                        i++;
                        j--;
                    }
                }
            }
        }

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

http://www.csse.monash.edu.au/~lloy...lgDS/Sort/Flag/


NSTRIKE קבל צלש על כל הקוד שכתבת O.O

מה ההבדל בין "על כל ערך במערך פעם אחת" ו-"כל תא במערך פעם אחת"?

שים לב שבפתרון שהבאתי במקרה הכי גרוע (מערך של רק ספרות 2) אני קורא N פעמים את התא הראשון במערך. כלומר אני קורא אותו תא N פעמים, אך עם זאת אני קורא כל ערך רק פעם אחת.