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

[wow]

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

[עוד אחד]

ומאיפה מגיע הכדור הלבן ש"דורס" אותו ?

אם יש לך רעיון - תגדיר במדוייק אלגוריתם (פסאודו קוד/תיאור). בגלל שאתה רושם חצי חפיף קשה לך להבין אח"כ מה יקרה במקרים אחרים.

זה יעזור לך גם בכלל, בחשיבה על בעיות להבא.

[עוד אחד]

ובגלל שאני לא אהיה פה בכמה שעות הקרובות - ואתה תרצה בטח להתקדם -

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

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

סה"כ קצת פחות מ2 ריצות על המערך.

שים לב 2 - אפשר גם בריצה אחת, יש יותר מקרי החלפה.

רמז

- החלפה בין כדור מהאמצע להתחלה

- החלפה בין כדור מהאמצע לסוף

- החלפה בין כדור מההתחלה לסוף.

[wow]

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

	public static void sortByFour (int[] arr)
	{
		int temp;
		int numberOfNoRemainberNumbers = 0;
		int numberOfRemainber1Numbers = 0;
		int numberOfRemainber2Numbers = 0;
		int numberOfRemainber3Numbers = 0;

		for (int i = 0; i < arr.length; i++) //no remainder
		{
			if (arr[i] % 4 == 0)
			{
				temp = arr[numberOfNoRemainberNumbers]; 
				arr[numberOfNoRemainberNumbers] = arr[i];
				arr[i] = temp;
				numberOfNoRemainberNumbers++;
			}
		}

		int start = numberOfNoRemainberNumbers;
		int startPos = numberOfNoRemainberNumbers + numberOfRemainber1Numbers;

		for (int i = start; i < arr.length; i++) //remainder of 1
		{
			if (arr[i] % 4 == 1)
			{
				temp = arr[startPos];
				arr[startPos] = arr[i];
				arr[i] = temp;
				numberOfRemainber1Numbers++;
				startPos++;

			}
		}

		start = numberOfNoRemainberNumbers + numberOfRemainber1Numbers;
		startPos = numberOfNoRemainberNumbers + numberOfRemainber1Numbers;

		for (int i = start; i < arr.length; i++) //remainder of 2
		{
			if (arr[i] % 4 == 2)
			{
				temp = arr[startPos];
				arr[startPos] = arr[i];
				arr[i] = temp;
				numberOfRemainber2Numbers++;
				startPos++;
			}
		}
	}

[Holy Spirit]

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

תשים לב שאתה עושה את הדברים בסדר מסויים: קודם מוצא את כל הערכים עם שארית 0 ומעביר אותם להתחלה, אז עבור כל הערכים עם שארית 1 וכו'.

לכן מספיק לך לעקוב רק אחרי האינדקס של האיבר הבא להחלפה, נקרא לו למשל top, ונשתמש בו במקום המשתנים numberOfRemainber<*>Numbers, start, startPos.

כלומר כל מה שמשמאל ל-top נמצא במקום, וכל מה שמימין צריך עוד למיין.

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

[Gil28]

תלוי איך אתה מגדיר את אורך הקלט, הדרישה למודולו 4 גם יכולה להוות קלט. כשיבקשו מודולו *אורך המערך* זה יהיה שונה...

[עוד אחד]

תלוי איך אתה מגדיר את אורך הקלט, הדרישה למודולו 4 גם יכולה להוות קלט. כשיבקשו מודולו *אורך המערך* זה יהיה שונה...

זה לא נכלל כקלט במקרה הזה, כי זה מקודד לתוך התוכנית.

הוא לא "קולט" בשום מקום מהמשתמש איזה חשבון מודולו למיין.

[Gil28]

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

אגב, גם פיתרון רקורסיבי יהיה אלגנטי להפליא.

[wow]

איזה רקורסיה ? (אני מחפש דרך טובה יותר לפיתרון שלי)

[Holy Spirit]

תממש את ההצעות שנתתי לך קודם ותשים פה את הקוד. זה אמור לצאת קצר ופשוט.

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

וסתם בשביל הכיף, ב-haskell זאת פונקציה של שורה אחת כמובן.

sortByFour = concat . groupWith (`mod` 4)

-- or: (but O(n*log(n)))
sortByFour = sortBy (compare `on` (`mod` 4))

[Gil28]

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

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

void sortByMod4(int arr[])
{
	int s = 0; 	   //points to the first cell of mod 4 == 0
	int e = arr.length(); //points to the last cell of mod 4 == 3
	for (int i=start;i<end;i++)
	{
		if (a[i] % 4 == 0)
		{
			swap(a[s],a[i]);
			s++;
		}
		else if (a[i] % 4 == 3)
		{
			swap(a[e],a[i]);
			e++;
		}
	}
	int s1 = s; //points to the first cell of mod 4 == 1
	int e1 = e; //points to the last cell of mod 4 == 2
	for (i=s;i<=e;i++)
	{
		if (a[i] % 4 == 1)
		{
			swap(a[s1],a[i]);
			s1++;
		}
		else if (a[i] % 4 == 2)
		{
			swap(a[e1],a[i]);
			e1++;
		}
	}
}

[wow]

בסופו של דבר הלכתי על הפיתרון הקודם שלי עם מה ש-Holy Spirit הציע לי

    public static void sortByFour(int[] arr)
    {
      int i;
      int temp;
      int remainderNum = 0;
      int remainderFirstCell = 0;
      int numberOfHandleNubers = 0;

      while (remainderNum < 3)
      {
        for (i = 0; i < arr.Length; i++)
        {
          if (arr[i] % 4 == remainderNum)
          {
            temp = arr[remainderFirstCell];
            arr[remainderFirstCell] = arr[i];
            arr[i] = temp;
            remainderFirstCell++;
            numberOfHandleNubers++;
          }
        }

        i = numberOfHandleNubers;
        remainderNum++;
      }
    }

[Gil28]

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

לולאת ה-while שלך בקלות יכולה להפוך ללולאת for הרי אתה יודע מראש את אורכה (מסודר וברור יותר)

[wow]

לא ממש ירדתי לסוף דעתך

[Gil28]

בנוסף למשתנה remainderFirstCell אתה יכול להוסיף משתנה remainderLastCell ולרוץ מהסוף להתחלה (או נכון יותר עד ל-remainderFirstCell)

ולשים שם את האיברים המתאימים.