Mergesort

Neue Frage »

Auf diesen Beitrag antworten »
JROppenheimer Mergesort

ich habe hier einen Mergesort-algorithmus, aber in er mergefunktion gibt es eine zeile, die ich nicht verstehe, ich poste hier mal die merge funktion:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
 
void merge (int links, int mitte, int rechts) {
int i, j, k;
// B ist ein global definiertes integer-Array.
for (i = links; i <= mitte; i++)
B[i] = A [i];
// Das erste Teilarray wird nach B kopiert.
for (i = mitte + 1; i <= rechts; i++)
B [i] = A [rechts - i + mitte + 1];
// Das zweite Teilarray wird in umgekehrter Reihenfolge
// nach B kopiert
i = links, j = rechts;
for (k = links; k <= rechts; k++)
A [k] = (B[i] < B[j])? B[i++] : B[j--];
}


ich weiss leider nicht, was zeile 14 sein soll ... habe dieses konstrukt noch nie gesehn.
kann mir einer verraten, was das macht?

*edit: verzeiht mir,dass das mnicht richtig eingerückt ist, die jeweiligen forschleifen haben im rumpf nur eine zeile jeweils ...
 
Auf diesen Beitrag antworten »
Tobias

Der Ausdruck in der Übsicht:

code:
1:
"boolescher Ausdruck" ? Rückgabewert wenn "true"  : Rückgabewert wenn "false"


A [k] = (B[i] < B[j])? B[i++] : B[j--];
ist also die Kurzform für folgenden äquivalenten Code:

code:
1:
2:
3:
4:
5:
if (B[i] < B[j]) {
  A[k] = B[i++];
} else {
  A[k] = B[j--];
}
Auf diesen Beitrag antworten »
JROppenheimer

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
if (B[i] < B[j]) 
{
  A[k] = B[i++];
}
else
{
  A[k] = B[j--];
}


Wenn das so ist, dann funktioniert das aber nicht, denke ich. Angenommen ich habe ein Array B, das wie folgt aussieht:

B = [2,3,1]

Die for Schleife würde schon bei k=1 einen Fehler machen, wenn das so ist, wie Du sagst.
k=1
i=links (also 1)
j=rechts (in dem Fall also 3)
Immer vorausgesetzt die Indize laufen von 1 bis ... nicht von 0 ... bis

Im Zustand, wie oben beschrieben wäre

A[1] = B[2] = 3 ... somit wäre das Array falsch sortiert ... sehe ich das richtig?

*edit: das hier bestätigt meine meinung, dass das mit dem ausdruck ein bisschen anders geht, wenn ichd as richtig sehe:

aufgetüftelt
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »