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.
Vorschlag für Altklausur SS 15 - Aufgabe 7 (Sortieren) - MergeSort
Ich denke mein Code hier löst die Aufgabe komplett, (besteht meine TestCases). Da ich aber generell sehr selbstunsicher bin, stelle ich den Code noch nicht auf der Altklausuren Seite online. D.h. wer sich sicher ist, dass mein Code funktioniert, darf gerne kommentieren bzw. dann die auf der AltklausurenSeite entsprechenden Code Teile online stellen. Ansonsten: Anregungen/Verbessunergsvorschläge sind immer auch gerne willkommen.
PS: Die System.out.println(), habe ich lediglich zur Kontrolle eingebaut, (für die Aufgabe keinen Belang)
public class MergeSortUsing4Lists {
public static void mergeSortExtern(LinkedList b) {
assert b != null;
assert b.size() > 0;
LinkedList<Integer> b0 = new LinkedList<>();
LinkedList<Integer> b1 = new LinkedList<>(b.subList(0, b.size() / 2));
LinkedList<Integer> b2 = new LinkedList<>(b.subList(b.size() / 2, b.size()));
LinkedList<Integer> b3 = new LinkedList<>();
merge(1, b0, b1, b2, b3);
b.clear();
b.addAll(b0);
b.addAll(b1);
}
public static void merge(int len, LinkedList<Integer> b0, LinkedList<Integer> b1, LinkedList<Integer> b2,
LinkedList<Integer> b3) {
LinkedList<Integer> target = b0; // alternating between b0 and b3
do {
System.out.println();
System.out.println(b0);
System.out.println(b1);
System.out.println(b2);
System.out.println(b3);
System.out.println();
int z1 = 0, z2 = 0; // counter for the already stored integers from
// b1/b2 till len
// if possible, store integers from b1 AND b2
while (!b1.isEmpty() && !b2.isEmpty() && z1 < len && z2 < len) {
if (b1.getFirst() <= b2.getFirst()) {
target.addLast(b1.getFirst());
b1.removeFirst();
z1++;
} else {
target.add(b2.getFirst());
b2.removeFirst();
z2++;
}
}
// if there are still integers from b1
while (!b1.isEmpty() && (b2.isEmpty() || z2 == len) && z1 < len) {
target.addLast(b1.getFirst());
b1.removeFirst();
z1++;
}
// if there are still integers from b2
while (!b2.isEmpty() && (b1.isEmpty() || z1 == len) && z2 < len) {
target.addLast(b2.getFirst());
b2.removeFirst();
z2++;
}
target = target == b0 ? b3 : b0;
} while (!b1.isEmpty() || !b2.isEmpty());
// b3 is not empty => recursion call!
if (!b2.isEmpty() || !b3.isEmpty()) {
merge(2 * len, b1, b0, b3, b2);
} else {
System.out.println();
System.out.println(b0);
System.out.println(b1);
System.out.println(b2);
System.out.println(b3);
System.out.println();
}
}
public static void main(String[] args) {
LinkedList<Integer> a = new LinkedList<Integer>(
Arrays.asList(10, 2, 1, 7, 6, 9, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));
// LinkedList<Integer> b = new LinkedList<Integer>(Arrays.asList(5, 8,
// 4, 23, 24, 1, 2, 3, 7, 12, 3));
mergeSortExtern(a);
}
}
Ich habe mich gerade auch an der Aufgabe versucht. Danke für den Code! So konnte ich meine Variante gleich testen 
Ein paar Bedingungen konnte man bei dir einfacher schreiben, zumindest funktioniert es in dieser Form. Siehe Kommentare im Code.
Außerdem habe ich noch zwei weitere Test Cases hinzugefügt. Vor allem der mit einer ungeraden Anzahl von Elementen hinzugefügt hat bei mir noch einen Fehler aufgedeckt
[code=java]public class MergeSortUsing4Lists {
public static void mergeSortExtern(LinkedList b) {
assert b != null;
assert b.size() > 0;
LinkedList<Integer> b0 = new LinkedList<>();
LinkedList<Integer> b1 = new LinkedList<>(b.subList(0, b.size() / 2));
LinkedList<Integer> b2 = new LinkedList<>(b.subList(b.size() / 2, b.size()));
LinkedList<Integer> b3 = new LinkedList<>();
merge(1, b0, b1, b2, b3);
b.clear();
b.addAll(b0);
b.addAll(b1);
}
public static void merge(int len, LinkedList<Integer> b0, LinkedList<Integer> b1, LinkedList<Integer> b2,
LinkedList<Integer> b3) {
LinkedList<Integer> target = b0; // alternating between b0 and b3
do {
System.out.println();
System.out.println(b0);
System.out.println(b1);
System.out.println(b2);
System.out.println(b3);
System.out.println();
int z1 = 0, z2 = 0; // counter for the already stored integers from
// b1/b2 till len
// if possible, store integers from b1 AND b2
while (!b1.isEmpty() && !b2.isEmpty() && z1 < len && z2 < len) {
// Wegen <= ist es stabil (hattest du richtig; nur als Anmkerung für die Leser im Wiki)
if (b1.getFirst() <= b2.getFirst()) {
target.addLast(b1.removeFirst()); // etwas kürzer: removeFirst() gibt das Element auch zurück
z1++;
} else {
target.add(b2.removeFirst());
z2++;
}
}
// if there are still integers from b1
// "!b2.isEmpty() && z2 < len" reicht als Bedingung aus, denn beide können nicht gleichzeitig noch Reste haben,
// denn dann wäre die while-Schleife oben noch ausgeführt worden.
while (!b1.isEmpty() && z1 < len) {
target.addLast(b1.removeFirst());
z1++;
}
// if there are still integers from b2
// Dasselbe Argument wie oben
while (!b2.isEmpty() && z2 < len) {
target.addLast(b2.removeFirst());
z2++;
}
target = target == b0 ? b3 : b0;
} while (!b1.isEmpty() || !b2.isEmpty());
// b3 is not empty => recursion call!
// b2 ist an dieser Stelle sicher leer, sonst wäre obige do-while-Schleife noch ausgeführt worden
if (!b3.isEmpty()) {
merge(2 * len, b1, b0, b3, b2);
} else {
System.out.println();
System.out.println(b0);
System.out.println(b1);
System.out.println(b2);
System.out.println(b3);
System.out.println();
}
}
public static void main(String[] args) {
LinkedList<Integer> a_empty = new LinkedList<Integer>();
mergeSortExtern(a_empty);
LinkedList<Integer> a = new LinkedList<Integer>(
Arrays.asList(10, 2, 1, 7, 6, 9, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));
mergeSortExtern(a);
// odd number of elements (added number 19)
LinkedList<Integer> a_odd = new LinkedList<Integer>(
Arrays.asList(10, 2, 1, 7, 6, 9, 19, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));
mergeSortExtern(a_odd);
}
}[/code]
1 „Gefällt mir“
Fürs generelle Testen von Sorts habe ich mir eine Klasse geschrieben, die mir einen Array durchmischt. Das ist vielleicht auch ganz nützlich. Bei Gelegenheit/Notwendigkeit würde ich meine Klasse noch ausbauen…
PS: Wie fügst du Zeilennummerierung bei Code hinzu? code , /code in []-Klammern ändert bei mir erstaunlich wenig.
import java.util.Random;
public class ArrayShuffler<T> {
public T[] shuffle(T[] t) {
int len = t.length;
Random r = new Random();
for (int i = 0; i < len; i++) {
int j = r.nextInt(len);
swap(t, i, j);
}
return t;
}
private void swap(T[] t, int i, int j) {
T temp = t[i];
t[i] = t[j];
t[j] = temp;
}
}Vielen Dank für deine Bemerkungen im Code!
Dafür soll man im Post nicht einfach nur „code“, sondern „code=java“ (jeweils in eckigen Klammern und ohne Anführungszeichen) verwenden.