מה הדרך הכי טובה למיין מערך חד ממדי לפי סדר עולה בעזרת מערך עזר,

יש לי את הרעיון אני לא מצליח ליישם אותו..

בבקשה הלפ... :s05:

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

פתרון הכי יעיל:

http://en.wikipedia.org/wiki/Quicksort

פתרונות הכי פשוטים (אבל פחות יעילים):

http://en.wikipedia.org/wiki/Selection_sort

http://en.wikipedia.org/wiki/Bubble_sort

בוקר טוב אחי, יפה שאתה ער בשעה כזאת,

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

double sort (double a[N])
{
	int i ,j;
	double temp;
	for (i = 0; i < N-1; i++)
	{
		for (j = 0; j < N - i -1; j++)
		{
			if (a[j] > a[j+1])
			{
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
	}

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

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

האם אפש רליישם את זה בצורה יעילה יותר ממיון בועות?

נתתי לך כבר לינק למיון היעיל ביותר.

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

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

שניצל שאלה לי אליך: האם מיון ערימה (HEAP SORT) לא אמור להיות יעיל יותר? אני יודע ששניהם זה nlogn אבל אם אני לא טועה מיון ערימה יעיל יותר מבחינת מצב גרוע.

ואללה, אין לי מושג.

בשביל מה יש ויקיפדיה?

http://en.wikipedia.org/wiki/Heapsort

Quicksort is typically somewhat faster, due to better cache behavior and other factors, but the worst-case running time for quicksort is O(n2), which is unacceptable for large data sets and can be deliberately triggered given enough knowledge of the implementation, creating a security risk. See quicksort for a detailed discussion of this problem, and possible solutions.

Thus, because of the O(n log n) upper bound on heapsort's running time and constant upper bound on its auxiliary storage, embedded systems with real-time constraints or systems concerned with security often use heapsort.

צדקתי.

הרבה מימושים של std::sort עוברים ל-heapsort כאשר הרקורסיה עמוקה מדי, או ל-insertion sort כאשר N קטן מאוד (נניח 16).

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