import java.util.Arrays; public class MergeSort { private static final int I = 2; /** * Sortiere die Datens�tze von Band t[0] auf eines der B�nder t[i] * * @return Nummer i des Bandes, auf dem sich das Ergebnis * befindet. */ public static int mergesort(Stream[] t) { createInitialRuns(t[0], t[2], t[3]); // von 0 nach 2,3 int in1 = 2, in2 = 3, out1 = 0, out2 = 1; int runLength = I; printTapes(t, 2,3, runLength); while(true) { rewindEverything(t, in1, in2, out1, out2); if (t[in2].eof()) { // t[in1] ist immer l�nger! // Alles hat auf ein Band, in1, gepasst: wir sind fertig return in1; } mergeAllRuns(t, in1, in2, out1, out2, runLength); int tmp1 = in1; in1 = out1; out1 = tmp1; int tmp2 = in2; in2 = out2; out2 = tmp2; runLength = runLength * 2; printTapes(t, in1, in2, runLength); // oben haben wir auf in1/in2 geschrieben } } private static void mergeAllRuns(Stream[] t, int in1, int in2, int out1, int out2, int runLength) { int out = out1; // t[in1] ist das l�ngere von beiden B�ndern! while(! t[in2].eof()) { mergeTwoRuns(t[in1], t[in2], t[out], runLength); if (out == out1) { out = out2; } else { out = out1; } } copyRest(t[in1], t[out]); // kopiere Rest des l�ngeren Bands } private static void rewindEverything(Stream[] t, int ein1, int ein2, int aus1, int aus2) { t[ein1].reset(); t[ein2].reset(); t[aus1].rewrite(); t[aus2].rewrite(); } /** */ private static void mergeTwoRuns(Stream in1, Stream in2, Stream out, int runLength) { // in1 ist l�nger als in2 // weder in1 noch in2 sind EOF if (in1.eof()) { System.out.println(in1.toString()); System.out.println(in2.toString()); } int value1 = in1.read(); int value2 = in2.read(); int remainingReads1 = runLength-1; int remainingReads2 = runLength-1; while(true) { if (value1 <= value2) { out.write(value1); if (canStillRead(remainingReads1, in1)) { value1 = in1.read(); remainingReads1--; } else { // Band 1 ist leer und komplett geschrieben out.write(value2); copyAtMost(in2, out, remainingReads2); return; } } else { out.write(value2); if (canStillRead(remainingReads2, in2)) { value2 = in2.read(); remainingReads2--; } else { // Band 2 ist leer und komplett geschrieben out.write(value1); copyAtMost(in1, out, remainingReads1); return; } } } } private static boolean canStillRead(int nochZuLesen, Stream ein) { return !ein.eof() && nochZuLesen > 0; } private static void copyAtMost(Stream ein, Stream aus, int maxAnzahl) { for(int i=0; i < maxAnzahl; i++) { if (ein.eof()) return; aus.write(ein.read()); } } private static void copyRest(Stream ein, Stream aus) { while(! ein.eof()) { aus.write(ein.read()); } } /** * I Datens�tze einlesen, sortieren und wechselnd auf aus1/aus2 verteilen */ private static void createInitialRuns(Stream in, Stream out1, Stream out2) { in.reset(); out1.rewrite(); out2.rewrite(); int[] mainMemory = new int[I]; Stream aus = out1; while(true) { int size = readIntoMemory(in, mainMemory); Arrays.sort(mainMemory, 0, size); for(int i=0; i < size; i++) { aus.write(mainMemory[i]); } // Alterniere: Verwende anderen Stream zur Ausgabe if (aus == out1) { aus = out2; } else { aus = out1; } } } private static int readIntoMemory(Stream in, int[] mainMemory) { int counter; for(counter = 0; counter < I; counter++) { if (in.eof()) break; mainMemory[counter] = in.read(); } return counter; } //---------------------- Helpers private static void printTapes(Stream[] t, int out1, int out2, int runLength) { System.out.println("Runl�nge: "+runLength); for(int i=0; i "+i+": "+t[i].toString(runLength)); } else { System.out.println(" "+i+": "+t[i].toString(runLength / 2)); } } System.out.println(); } //---------------------- Main public static void main(String[] args) { // Beispiele: // 40, 39, 38, 37, 36, 11, 10, 9, 8, 7, 6, 3, 2 // 7, 6, 5, 4, 3, 2, 1 // 12,5,2,15,13,6,14,1,4,9,10,3,11,7,8 Stream[] tapes = { new Stream(40, 39, 38, 37, 36, 11, 10, 9, 8, 7, 6, 3, 2), new Stream(), new Stream(), new Stream() }; mergesort(tapes); } }