יעילות - אני צריך ללמוד את כל הנושא הזה... עריכה: או שלא?

[ktbnus]

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

הרי אתה בודק אחר כך אם size <=1 ואם כן משחרר. עדיף תבדוק ואם לא, תקצא.

2. את arr2s אתה לא באמת צריך.

size-(size/2) 

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

3. בלולאה את תמיד מבצע את ה IF למרות שהוא אף פעם לא יכנס עליו עד החצי, עדיף ב 2 לולאות נפרדות, לפי דעתי.

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

אבל בשביל זה אתה צריך כמה שינויים קטנים.

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

(טכנית את מקצאה אותה כמות של זכרון)

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

[SweeT_EviL]

טוב נראה לי סידרתי את כל מה שאמרתם.

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

אני חושב שאני כן צריך, קח דוגמא

arr1: 3, 5

arr2: 2, 6

a: 2, 3, 5, 6 לאחר מיון

אם ARR1 וARR2 היו מצביעים על מקומות שוים בA אז למשל לאחר העתקת הערך הראשון (2) לתחילת המערך הערך הבא אחריו היה נמחק(3)...

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

[ktbnus]

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

[SweeT_EviL]

איך אני מתיחס לערך שאליו המצביע מצביע?

&/*/כלום

כשניסית לשנות שמתי לב שהוא ממיין לפי הכתובות(כאילו הם הערכים). כשאני מנסה לשים לפני * הוא לא נותן לי לעשות דברים(השוואות) ואם אני לא שם כלום אז זה בודק את הכתובות.. אותו דבר עם &

[ktbnus]

אפשר קוד?

[SweeT_EviL]

SORT

/* Sorting the arrey */
void sort(int *a,int size)
{
	int i;

	if(size<=1)
		return;

	sort(a,size/2);
	sort(a+(size/2),size-(size/2));

	combine(a, a, a+(size/2), size, size/2, size-(size/2));

	return;
}

combine:

תבחר אחד, זה לא משנה...

void combine(int *a, int *arr1, int *arr2, int size, int sArr1, int sArr2)
{
	int tmp;
	if(size==0)
   	return;
	if(sArr1==0 || arr2 < arr1 && sArr2>0)
	{
		tmp=*arr1;
		a=arr2;
		arr2=tmp;
		combine(a+1, arr1,arr2+1, size-1, sArr1, sArr2-1);	
		return;
	}
	combine(a+1, arr1+1,arr2, size-1, sArr1-1, sArr2);
	return;
}

void combine(int *a, int *arr1, int *arr2, int size, int sArr1, int sArr2)
{
	int i;
	int *x=(int*)malloc(size*sizeof(int));

	if(!x)
	{
		printf("error");
		return;
	}
	for(i=0;i<size;i++)
	{
		if(sArr2==0 || arr1<arr2 && sArr1>0)
		{
			x[i]=arr1++;
			--sArr1;
			continue;
		}
		x[i]=arr2++;
		--sArr2;
	}

	for(i=0;i<size;i++)
		a[i]=x[i];
	return;
}

[ktbnus]

הכוונה שלי הייתה למשהו טיפה שונה

int* combine( int* A1, int n1, int* A2, int n2)
{
	int *res;

	int i1, i2;
	int writeIndex;

	// alloc size fro new array
	res = (int*)malloc(sizeof(int)*(n1+n2));

	i1 = i2 = writeIndex = 0;

	/// merge
	while( (i1 < n1) && (i2 < n2) )
	{
		if( A1[i1] < A2[i2] )
		{
			res[writeIndex] = A1[i1];
			i1++;
		}
		else
		{
			res[writeIndex] = A2[i2];
			i2++;
		}
		writeIndex++;
	}

	while ( i1 < n1 )
	{
		res[writeIndex] = A1[i1];
		i1++;
		writeIndex++;
	}

	while ( i2 < n2 )
	{
		res[writeIndex] = A2[i2];
		i2++;
		writeIndex++;
	}

	return res;

בתוך merge תגדיר עוד פויינטר

int*sorted;

לאחר ההפעלה של הפונקציות הרקורסיביות

sorted = combine(a, size/2, a+(size/2), size- (size/2))

for( i = 0; i <size; i ++)
a[i] = sorted[i];

free((void*)sorted);

הcombine השני שלך מעתיק ממקומות שונים במערך לתוך אותו מערך, הוא דורס ערכים.

תקצה מערך ב combine , תחחזיר אותו ל merge וב merge תעתיק למערך המקורי.

[Ghosthunter]

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

[SweeT_EviL]

הכוונה שלי הייתה למשהו טיפה שונה

int* combine( int* A1, int n1, int* A2, int n2)
{
	int *res;

	int i1, i2;
	int writeIndex;

	// alloc size fro new array
	res = (int*)malloc(sizeof(int)*(n1+n2));

	i1 = i2 = writeIndex = 0;

	/// merge
	while( (i1 < n1) && (i2 < n2) )
	{
		if( A1[i1] < A2[i2] )
		{
			res[writeIndex] = A1[i1];
			i1++;
		}
		else
		{
			res[writeIndex] = A2[i2];
			i2++;
		}
		writeIndex++;
	}

	while ( i1 < n1 )
	{
		res[writeIndex] = A1[i1];
		i1++;
		writeIndex++;
	}

	while ( i2 < n2 )
	{
		res[writeIndex] = A2[i2];
		i2++;
		writeIndex++;
	}

	return res;

בתוך merge תגדיר עוד פויינטר

int*sorted;

לאחר ההפעלה של הפונקציות הרקורסיביות

sorted = combine(a, size/2, a+(size/2), size- (size/2))

for( i = 0; i <size; i ++)
a[i] = sorted[i];

free((void*)sorted);

הcombine השני שלך מעתיק ממקומות שונים במערך לתוך אותו מערך, הוא דורס ערכים.

תקצה מערך ב combine , תחחזיר אותו ל merge וב merge תעתיק למערך המקורי.

ממה שאני רואה התוכנית שלך והשניה שלי עושות בדיוק אותו דבר, איך שלך מעתיקה בלי דריסה ושלי כן?

שתי התוכניות שלנו עושות בדיוק אותו דבר בצורה אחרת... חוץ מששלך מחזירה את המערך ורק אז מעתיקה אותו...

דרך אגב למה פשוט לא רשמת:

a = combine(a, size/2, a+(size/2), size- (size/2))

[ktbnus]

כי אני לא רוצה לשנות את הכובת ששמורה ב a.

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

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

x[i]=arr1++;

מנסה להעתיק את הכתובת של arr1 לתוך התא i ב X. זה לא מעתיק את הערך. זה מופיע גם בהעתקה מ arr2

x[i]=*arr1++;

זה יעתיק את הערך.

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

[Zelig]

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

או תקצו מראש, כמובן.