mergesort / Komplexität

[jippel]

Moin,
also ich soll ein Programm Mergesort erstellen, bei dem nur die erste Hälfte des Arrays in ein Hilfsarray ausgelagert werden soll, das hab ich sogar hinbekommen und läuft auch :xmas1:

Nun soll eine besere Version geschrieben werden, die nur Zahlen auslagert, die auch ausgelagert werdeb müssen:

z.B. erste Hälfte 1 2 5
zweite Hälfte 4 6 7

1 2 brauchen nicht ausgelagert werden, da sie kleiner sind als das erste Element der zweiten Hälfte.

Siehe mein zweites Posting.

[jippel]

So, nun hab ich es

Nun wird immer geprüft, ob die Zahl überhaupt ausgelagert werden muß.
Wie sieht das nun mit der Komplexität aus ?
Also bei der "normalen" Funktion mergesort wo immer die Hälfte des Arrays ausgelagert werden muß ist die ja 1.5 n * log(n)

Bei meiner neuen Funktion ist die ja im besten Fall 0, wenn die Zahlen schon in der richtigen Reihenfolge sind.
Im schlechtstesn Fall sind es denn ja auch 1.5 n * log(n), wenn die ganze Hälfte ausgelagert werden muß.

Wie ist nun die Komplexität im Durchschnitt ? einfach (Komplexität im besten Fall + Komplexität im schlechtesten Fall) / 2 ??

void merge(int lo, int m, int hi)
	{
		int b[10];					//Hilfsarray
		int i, j, k, verbleib;		// neu: int verbleib, siehe unten

		i = 0; j = lo; verbleib = 0;

		while (a[j] < a[m+1])		// wenn die Zahlen der ersten Hälfte kleiner sind 
									// als die erste Zahl der zweiten Hälfte, müssen sie nicht ausgelagert werden
		{
			j++;
			verbleib++; // verbleib zeigt an, wieviele Zahlen nicht ausgelagert wurden, um sie beim
									// Zurückkopieren nicht zu überschreiben
		}

		while (j <= m)				// restlichen Zahlen in das Hilfsarray auslagern
		{
			b[i] = a[j];
			i++; j++;
			log++;
			schritt++; // Test für Komplexität
		}

		i = 0; k = lo + verbleib; // k + verbleib, damit man die verbliebenen Zahlen im Array nicht überschreibt

		while (k<j && j<=hi)
		{
			if (b[i]<=a[j])
			{
				a[k] = b[i];
				k++; i++;
				log++;
				schritt++; // Test für Komplexität
			}
			else
			{
				a[k]=a[j];
				k++; j++;
				log++;
				schritt++; // Test für Komplexität
			}

		}

		while (k<j)
		{
			a[k] = b[i];
			k++; i++;
			log++;
			schritt++; // Test für Komplexität
		}

	}

Edit:

////////////////////////////////////////////
// Funktion merge
// Jan-Philipp Lux / Matr. 26 46 71
// Hausarbeit Informatik 2/3 WS2006/07
////////////////////////////////////////////

void merge(int lo, int m, int hi)
	{

		int i, j, k, verbleib;

		i = 0; j = lo; verbleib = 0;

		while (a[j] < a[m+1])		// Überlegung: Wenn die Zahlen der ersten Hälfte kleiner sind 
									// als die erste Zahl der zweiten Hälfte, müssen sie nicht ausgelagert werden
		{
			j++;
			verbleib++;				// "verbleib" zeigt an, wieviele Zahlen NICHT ausgelagert wurden, um sie beim
									// Zurückkopieren nicht zu überschreiben
		}

		while (j <= m)				// Die restlichen Zahlen in das Hilfsarray auslagern
		{
			b[i] = a[j];
			i++; j++;
		}

		i = 0; k = lo + verbleib; // k = lo + verbleib, damit man die verbliebenen Zahlen im Array nicht überschreibt

		while (k<j && j<=hi)
		{
			if (b[i]<=a[j])
			{
				a[k] = b[i];
				k++; i++;
			}
			else
			{
				a[k]=a[j];
				k++; j++;
			}

		}

		while (k<j)
		{
			a[k] = b[i];
			k++; i++;
		}

	}