JAVA - סוג של מיון בועות (קוד בפנים)

[BenSalem2]

שלום,

אני צריך לכתוב תוכנית שחתימתה מקבלת מערך לא ממויין

ואני צריך למיין אותה לפי מודולו 4

את כל המספרים שיקבלו שארית 0 בהתחלה

אחריהם המספרים שיקבלו שארית 1

אחריהם שארית 2

וכל השאר אחרי 2

בכל מקרה זה מה שכתבתי ( לא הכי מסודר )

public static int sortByFour(int[] arr)    {
        int count=0;
        for(int y=0;y<3;y++)

        for(int x=0;x<arr.length;x++)
        {

            if(arr[x] % 4 == arr[y] && x<=count)
               {
                arr[x] = arr[count];
                count++;
               }
                     else if(arr[x] % 4 == arr[y])
                     {
                      swap(arr,count,x);
                      count++;
                     }
        }
        return count;
    }
    public static void swap(int array[], int index1, int index2)
    {
       int temp = array[index1]; 
      array[index1] = array[index2];  
      array[index2] = temp;             
    }
   }

עכשיו הקטע שאני כן מבין זה שהשיטה לא תעבוד בטסטר מכיוון שאני מחזיר COUNT והוא באיטרציה השניה מתאפס

הקטע שאני לא מבין זה איך אני שומר את הCOUNT בלי שיתאפס

יש עוד כמה שאלות אבל פרה פרה

תודה מראש בן,

[borsood]

שים לב שלפי ההגדרה הערכים עצמם לא מעניינים.

כאשר אתה משווה שני אברים אתה צריך לעשות זאת כך:

 if (arr[i]%4 < arr[j]%4)

לשאר הקוד תוכל להשתמש באלגוריתם מיון סטנדרטי כמו מיון בועות

[BenSalem2]

שים לב שלפי ההגדרה הערכים עצמם לא מעניינים.

כאשר אתה משווה שני אברים אתה צריך לעשות זאת כך:

 if (arr[i]%4 < arr[j]%4)

לשאר הקוד תוכל להשתמש באלגוריתם מיון סטנדרטי כמו מיון בועות

הבנתי תודה

עכשיו לדבר שבאמת מקשה עליי

חתימת השיטה צריכה להיות VOID כך שאני לא יודע איך להחזיר ערך שישמור על המספר במערך אחרי סידור ראשוני

[שניצל]

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

(כן, יש דרך הרבה יותר יעילה, אבל אז זה לא מיון בועות)

[BenSalem2]

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

(כן, יש דרך הרבה יותר יעילה, אבל אז זה לא מיון בועות)

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

שוב תודה

[Gil28]

קודם תממש את הפיתרון עם מיון בועות. למה count בכלל מעניין אותך?

[BenSalem2]

קודם תממש את הפיתרון עם מיון בועות. למה count בכלל מעניין אותך?

כשאתה אומר קודם תממש מיון בועות אתה מתכוון סטנדרטי? כלומר מספרים מהגדול לקטן?

כי ניסיתי לעשות מיון בועות כשתנאי הוא מודולו 4 וזה לא מסדר טוב...

[שניצל]

כן, תתחיל ממיון בועות סטנדרטי לחלוטין. תוודא שהוא עובד ב-100% (תן לו כל מיני קלטים שונים ותבדוק שהם יוצאים ממוינים).

אחרי זה פשוט צריך להחליף את השורה שמשווה בין שני מספרים.

[BenSalem2]

כן, תתחיל ממיון בועות סטנדרטי לחלוטין. תוודא שהוא עובד ב-100% (תן לו כל מיני קלטים שונים ותבדוק שהם יוצאים ממוינים).

אחרי זה פשוט צריך להחליף את השורה שמשווה בין שני מספרים.

המיון הרגיל עובד טוב

איך שאני משנה את השורה למודולו 4 הוא משנה סדר אבל לא כמו שצריך...

[שניצל]

א. תעלה את הקוד הרלוונטי.

ב. אתה בטוח שהקוד שלך (בלי מודולו) עובד? בדקת אותו על כל מיני מערכים, מקרי קצה וכו'?

[שכיר חרב]

אשמח לשמוע את הדרך היותר מהירה

פשוט תכניס את האיברים של המערך הנתון ל-4 מערכים זמניים, תמזג, וזהו.

אני לא יודע אם זאת הדרך שהוא התכוון אליה (כנראה שכן), אבל אין שום טעם להשתמש במיון בועות לבעיה שלך.

[Gil28]

ובאיזה גודל יהיה כל מערך זמני?

מה ששניצל התכוון זה להשתמש באלגוריתם מיון מהיר יותר ממיון בועות. אחד שעובד בזמן של nlogn ולא n^2

[שניצל]

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

[שכיר חרב]

ובאיזה גודל יהיה כל מערך זמני?-

מה ששניצל התכוון זה להשתמש באלגוריתם מיון מהיר יותר ממיון בועות. אחד שעובד בזמן של nlogn ולא n^2

תלוי אם הוא יכול להשתמש במערכים דינמיים (כנראה שלא). אם לא אז כ"א בגודל n.

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

(אבל אני מודה שהפתרון אכן בעייתי אם דורשים O(1) מקום.)

[Gil28]

השאלה היא בכלל מה הרמה שלו ומה הדרישות.