יש בעיה מפורסמת במדעי המחשב , והיא מיון מערך בסיבוכיות של n

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

התווים הכחולים יש להצמיד לסוף המערך , התווים האדומים יש להצמיד לתחילת המערך , והתווים הלבנים באמצע

כתבתי קוד כזה :

 public class Test
{
 public static void main(String[] args)
 {

   char[] array= {'r','w','b','r','w','b','r','w','b','r','w','b','r','w','r','w','b'};
   int BlueP=array.length-1 , RedP=0;
  char temp ;
   for (int i=0; i<array.length;i++) 
    {
        if ( array[i]=='b' )
        {
          temp=array[i];
          array[i]=array[BlueP];
          array[BlueP]=temp;
          BlueP--;
        }
          else if ( array[i]=='r' )
          {
          temp=array[i];
          array[i]=array[RedP];
          array[RedP]=temp;
          RedP++; 
  }
}// for lop
for (int i=0 ; i<array.length ;i++)
System.out.print ( array[i]);
}// main
} 

מה לא בסדר בקוד הזה ?

הוא עובר קימפול , אבל לא מבצע את המשימה .

סתם מקריאה של הקוד, כשאתה מחליף את ה 'b' ב IF הראשון, מה קורה אם המיקום שב BlueP הוא כבר 'b' ? (הבנת את הרמז?)

הוא יחליף בכל מקרה את ה 'b'

זה לא מה שלא בסדר בתוכנית , התוכנית שלי גרועה מאוד , כנראה צריך שינוי מסיבי בה .

במקום זה פשוט תחזיק 2 מונים

תעשה לולאה שסופרת כמה כחול יש וכמה אדום יש

מספר הלבנים הוא גודל המערך פחות מספר הכחולים פחות מספר האדומים

ואז פשוט תכתוב לתוך המערך b כמספר הכחולים, r כמספר האדומים ו-w כמספר הלבנים.

פשוט וקל

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

במקום זה פשוט תחזיק 2 מונים

תעשה לולאה שסופרת כמה כחול יש וכמה אדום יש

מספר הלבנים הוא גודל המערך פחות מספר הכחולים פחות מספר האדומים

ואז פשוט תכתוב לתוך המערך b כמספר הכחולים, r כמספר האדומים ו-w כמספר הלבנים.

פשוט וקל

רעיון מעולה פשוט ומצוין וכנראה הוא בסיבוכיות O (n

אבל צריך להיות פתרון לא על ידי דריסת נתונים , כלומר על ידי החלפת האיברים .

אם מישהו יודע את האלגוריתם אשמח לשמוע .

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

אני אבדוק את זה , אבל נראה לי שהאלגוריתם שלי לא בר ביצוע .

ויש לתכנן אלגוריתם שונה לחלוטין , אלא אם כן מישהו הצליח לתקן את הקוד שלי , אז אשמח לראות .

תודה למגיבים

לא בדקתי את זה יותר מדי:

		char[] array= {'r','w','b','r','w','b','r','w','b','r','w','b','r','w','r','w','b'};
		int BlueP=array.length-1 , RedP=0;
		char temp;

		for (int i=0; i<BlueP;i++) 
		{
			if (array[i] == 'b')
			{
				temp=array[i];
				while (array[BlueP] == 'b')
					BlueP--;
				array[i]=array[BlueP];
				array[BlueP]=temp;
				BlueP--;
			}
			if (array[i] == 'r')
			{
				temp=array[i];
				array[i]=array[RedP];
				array[RedP]=temp;
				RedP++; 
			}
		}
		for (int i=0 ; i<array.length ;i++)
			System.out.print ( array[i]);

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

exercise אתה עלית על הבעיה מהרגע הראשון

וזה הקוד הסופי בדוק ומנוסה

 public class Test
{
 public static void main(String[] args)
 {

   char[] array= {'r','w','b','r','w','b','r','w','b','r','w','b','r','w','r','w','b','r','w','b','r','w','b','r','w','b'};
   int BlueP=(array.length-1) , RedP=0;
  char temp ;
   for (int i=0; i<=BlueP;i++) 
    {
        if ( array[i]=='b' )
        {
         if (array[BlueP]=='b')
         BlueP--;
          temp=array[i];
          array[i]=array[BlueP];

	    array[BlueP]=temp;
          BlueP--;
        }
           if ( array[i]=='r' )
          {

           temp=array[i];
           array[i]=array[RedP];

           array[RedP]=temp;
           RedP++; 
  }
}// for lop
for (int i=0 ; i<array.length ;i++)
System.out.print ( array[i]);
System.out.println("");
}// main
}  

הקוד הסופי שלך לא נכון. תנסה להחליף את ה 'w' האחרון במערך ב 'b' ותראה.

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

נראה לי שהפתרון של Holy הוא הכי טוב (ממה שהוצא כאן).

הפתרון של exercise בכלל בסיבוכיות n?

כן אתה צודק יש בקוד למעלה באג

תבדוק את הקוד הזה לעניות דעתי הוא מושלם (מבחינת הביצוע )

 public class Test
{
 public static void main(String[] args)
 {

   char[] array= {'r','w','b','r','w','b','r','w','b','r','w','b','r','w','r','w','b','r','w','b','r','w','b','r','w','b'};
   int BlueP=(array.length-1) , RedP=0;
  char temp ;
   for (int i=0; i<=BlueP;i++) 
    {
        if ( array[i]=='b' )
        {
         while (array[BlueP]=='b')
         BlueP--;
          temp=array[i];
          array[i]=array[BlueP];

	    array[BlueP]=temp;
          BlueP--;
        }
           if ( array[i]=='r' )
          {

           temp=array[i];
           array[i]=array[RedP];

           array[RedP]=temp;
           RedP++; 
  }
}// for lop
for (int i=0 ; i<array.length ;i++)
System.out.print ( array[i]);
System.out.println("");
}// main
}   

כן הוא בעל סיבוכיות n כי אנחנו עוברים על המערך פעם אחת בלוללאת FOR אחת

מבחינה לוגית נראה לי שזה נכון.

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

נסה את הקלט 'w', 'w', 'w', 'r', 'w', 'b' ותראה אם הוא נכון...

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

צודק...

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

ד"א גם האלג' שלך לא מתאים לכל המקרים. אם שמים בו רק אדומים ולבנים, כשיש אדום בסוף, אז יש באג.

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

נמאס לי, אני מחפש פתרון באינטרנט.

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

וד"א הפתרון שלו זה לא העתק מדויק של הפתרון שלי ?

כן זה אותו פתרון כמו שלך , רק בשינוי מזערי

אני כתבתי כך :

while (array[blueP]=='b')

BlueP--;

temp=array;

array=array[blueP];

array[blueP]=temp;

BlueP--;

ואתה כתבת כך :

temp=array;

while (array[blueP] == 'b')

BlueP--;

array=array[blueP];

array[blueP]=temp;

BlueP--;