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

[wow]

יש לי שאלה, השאלה היא כללית אבל אני רוצה לפתור את זה בג'אווה:

נניח שאני מקבל מערך של מספרים לא שליליים ואני רוצה למיין את המערך ככה שבתחילתו יופיעו רק המספרים שמתחלקים ב-3 ללא שארית, אחריהם אלו המתחלקים ב-3 עם שארית 1 ואח"כ כל השאר, איך אני יכול לחשב את זה בסיבוכיות קטנה ככל הניתן וביעילות גבוהה ככל הניתן ? אני עדיין צריך הרי לרוץ על כל המערך אז מה הכוונה פה כמה שיותר יעיל ומסובך פחות ? פחות חישובים ?

[Gil28]

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

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

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

[wow]

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

[Gil28]

מה מסובך? אתה רוצה לחשב סיבוכיות זמן ריצה או סיבוכיות מקום?

[wow]

זו ההגדרה המדוייקת של מה שאני צריך:

"השיטה צריכה להיות יעילה ככל הניתן.

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

[שניצל]

האם אתה בכלל יודע מה זה אומר סיבוכיות?

[wow]

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

[SaarD]

לפי דעתי אתה פשוט צריך לרוץ על המערך ובכל איבר אתה מבצע בדיקה אם = 0 שים אותו בתחילת המערך, אם גדול מ-1 (או שווה 2 במקרה הזה) שים בסוף המערך.

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

[wow]

הכוונה היא למשהו כזה ? (אני עושה את זה עם חילוק ב-4 והכללים דומים למה שכתבתי - בהתחלה ללא שארית, אח"כ שארית 1, שארית 2 ובסוף שארית 3):

  public static void sortByFour (int[] arr)
  {
   int[] newArr = new int[arr.length];
   int noRemainderLastIndex = 0;
   int remainder1LastIndex;
   int remainder2LastIndex;
   int remainder3LastIndex = (arr.length - 1);

   for (int i = 0; i < arr.length; i++)
   {
     if (arr[i] % 4 == 0)
     {
      newArr[i] = arr[noRemainderLastIndex];
      noRemainderLastIndex++;
     }  
     else if (arr[i] % 4 == 1)
     {

     }
     else if (arr[i] % 4 == 2)
     {

     }
     else if (arr[i] % 4 == 3)
     {
      newArr[i] = arr[remainder3LastIndex];
      remainder3LastIndex--;
     }
   }

[noodle]

לפי מה שהסברת אתה צריך שבתחילת המערך יופיעו המספרים שמתחלקים ב-3 עם שארית 0 ואז עם שארית 1, אבל אצלך בקוד אתה שם את אלו המתחלקים ב-3 עם שארית 0 בתחילת המערך ולא מטפל באלו שמתחלקים ב-3 עם שארית 1.

תסתכל על מה ש-SaarD רשם.

[wow]

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

אולי כדאי להגדיר 2 מערכי עזר ? (אחד לשארית 0 ו-1 ומערך אחד לשארית 2 ו-3)

[neogod]

הסיבוכיות הכי יעילה זה ב zz o(n)zz ובמקום ( אתה לא חייב מערכי עזר)

תיקח את המערך שלך ותשמור מצביעים לשני התאים הראשונים ושניים לתאים האחרונים , כאשר אלה שבהתחלה יצביעו לשארית 0/1 ואלה בסוף לשארית 2/3.

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

עכשיו בגלל שלכל תא יכולים להיות לכל היום 3 החלפות אתה מקבל סיבוכיות של zz o(3n) = o(n)zz

[wow]

רעיון טוב אני אנסה תודה רבה.

[wow]

טיפה הסתבכתי עם זה ואני לא מוצא את הבעיה שלי:

noRemainderIndex - מצביע על האינדקס למקום הפנוי למספר ללא שארית

remainder1Index - מצביע על האינדקס למקום הפנוי למספרים עם שארית 1

remainder2Index - מצביע על האינדקס למקום הפנוי למספרים עם שארית 2

remainder3Index - מצביע על האינדקס למקום הפנוי למספרים עם שארית 3

	public static void sortByFour (int[] arr)
	{
		int temp;
		int noRemainderIndex = 0;
		int remainder1Index = 1;
		int remainder2Index = arr.length - 2;
		int remainder3Index = arr.length - 1;

		for (int i = 0; i < arr.length; i++)
		{
			if (arr[i] % 4 == 0)
			{
				temp = arr[noRemainderIndex];
				arr[noRemainderIndex] = arr[i];
				arr[i] = temp;
				noRemainderIndex++;
				remainder1Index++;
			}
			else if (arr[i] % 4 == 1)
			{
				temp = arr[remainder1Index];
				arr[remainder1Index] = arr[i];
				arr[i] = temp;
				remainder1Index++;
			}
			else if (arr[i] % 4 == 2)
			{
				temp = arr[remainder2Index];
				arr[remainder2Index] = arr[i];
				arr[i] = temp;
				remainder2Index--;
			}
			else if (arr[i] % 4 == 3)
			{	
				temp = arr[remainder3Index];
				arr[remainder3Index] = temp = arr[i];
				arr[i] = temp;
				remainder3Index--;
				remainder2Index--;
			}
		}

[שניצל]

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