SoSe 14 - Aufgabe 5 (a, b)

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

SoSe 14 - Aufgabe 5 (a, b)
Hi zusammen,

nachdem es leider für die SoSe 14 noch keine vollständige Lösung gibt, wollte ich mal kurz meine Lösung für die 5te Aufgabe vorstellen:

5 a) Meiner Meinung nach müssten man hier ein Kreuz unter der 0 der 5 und der 2 setzen.

Nach dem vertauschen käme dann das hier raus:

6 7 5 3 1 0 2

5 b)

6 3 6 2 1 0 7

3

Hab ich auch so.

Aber ich glaub bei der b hast du dich verschrieben 6 3 5 2 1 0 7 sollte es sein.

4

Hab mal c) und d) gemacht analog zum VL-Code

[code]//c
void reheap(W[] w, Comparator c, int i, int k) {
int leftId = 2 * i + 1;
int rightId = leftId + 1;
int kidId;
if (leftId <= k && rightId > k) {
if (c.compare[w[LeftId],w[i]) > 0) {
swap(w, leftId, i);
}
} else {
if (rightId <= k) {
kidId = c.compare(w[leftId], w[rightId]) > 0 ? leftId : rightId;
if (c.compare(w[kidId], w[i]) > 0) {
swap(w, i, kidId);
reheap(w, c, kidId, k);
}
}
}
}
//d
void heapSort(W[] w, Comparator c) {
int n = w.length;

	for (int i = n / 2; i >= 0; i--) {
		reheap(w, c, i, n - 1);
	}

	for (int i = n - 1; i > 0; i--) {
		swap(w, 0, i);
		reheap(w, c, 0, i - 1);
	}
}

[/code]

5

Im Prinzip richtig, ist ja auch 1:1 der Vorlesungscode.

Beim rekursiven reheap aufruf hast du den Comparator vergessen und in der der Heapsort Methode i und c bzw. 0 und c vertauscht :).
Aber du benutzt den Comparator nicht, der hier extra mitangegeben wurde, siehe Angabe.
Anstatt o1.compareTo(o2) müsste es meiner Meinung nach c.compare(o1, o2) sein,
um die Objekte zu vergleichen, sonst wäre ja der Comparator nutzlos.

6

Klar, war vielleicht etwas zu analog zum VL-Code :stuck_out_tongue: habs mal angepasst

7

Ja man denkt sich ist doch viel zu einfach :smiley: