J
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++;
}
}
