import java.io.File;_x000D_
import java.io.FileWriter;_x000D_
import java.io.IOException;_x000D_
import java.util.ArrayList;_x000D_
import java.util.Arrays;_x000D_
_x000D_
/**_x000D_
 * Dateiname    : Mergesort.java_x000D_
 * Beschreibung : Einsendeaufgabe 2 für den Kurs Algorithmen_x000D_
 *_x000D_
 * @author Tobias Wagner (s79080@beuth-hochschule.de)_x000D_
 * @version 1.00, 02.12.2019_x000D_
 */_x000D_
_x000D_
// Klasse Mergesort zum Sortieren von Arrays und zum Testen der gegebenen Dateien Rand... und Sort..._x000D_
// Jeweils mit Anfangs- und Endzeit_x000D_
public class Mergesort_x000D_
{_x000D_
_x000D_
	private static String[] testDaten = {"Rand10_1", "Rand10_2", "Rand20_1", "Rand20_2",_x000D_
			"Rand50_1", "Rand50_2", "Rand100_1", "Rand100_2",_x000D_
			"Rand200_1", "Rand200_2", "Rand500_1", "Rand500_1",_x000D_
			"Rand1000_1", "Rand1000_2", "Rand10000_1", "Rand10000_2",_x000D_
			"Rand100000_1", "Rand100000_2", "Sort10_1", "Sort20_1", "Sort50_1", "Sort100_1", "Sort200_1",_x000D_
			"Sort500_1", "Sort1000_1", "Sort10000_1", "Sort100000_1"};_x000D_
_x000D_
	//Deklaration der main Methode_x000D_
	public static void main(String[] args) throws IOException_x000D_
	{_x000D_
		ArrayList<TestErgebnis> ergebnisListe = new ArrayList<>();_x000D_
_x000D_
		for (String testFilename : testDaten) {_x000D_
			// Einlesen des zu bearbeitenden Arrays - Auswahl der Datei mit dem Array_x000D_
			int[] testDatensatz = FileIntArray.FileToIntArray(testFilename);_x000D_
_x000D_
			// Ausgeben des unsortierten Arrays_x000D_
			System.out.println(Arrays.toString(testDatensatz));_x000D_
_x000D_
			// Erfassen der Anfangszeit_x000D_
			double anfangszeit = System.nanoTime();_x000D_
_x000D_
			// Ausführen von mergeSort_x000D_
			mergeSort(testDatensatz, 0, testDatensatz.length - 1);_x000D_
_x000D_
			// Erfassen der Endzeit_x000D_
			double endzeit = System.nanoTime();_x000D_
_x000D_
			// Ausgabe des sortierten Arrays_x000D_
			System.out.println(Arrays.toString(testDatensatz));_x000D_
_x000D_
			// Ausgabe der benötigten Dauer für den Durchlauf von mergeSort_x000D_
			double dauer = endzeit - anfangszeit;_x000D_
			System.out.println("Die benötigte Zeit betraegt: " + dauer + " Nanosekunden");_x000D_
_x000D_
			// Speichern des Testergebnisses in unsere ergebnissliste_x000D_
			TestErgebnis testErgebnis = new TestErgebnis(testFilename, dauer);_x000D_
			ergebnisListe.add(testErgebnis);_x000D_
		}_x000D_
_x000D_
		File datei = new File("Testlaufergebnis.csv");_x000D_
		FileWriter schreiber = new FileWriter(datei);_x000D_
_x000D_
		// CSV Kopzeile_x000D_
		schreiber.write("Testlauf;Zeit\n");_x000D_
_x000D_
		for (TestErgebnis testErg : ergebnisListe) {_x000D_
			schreiber.write(testErg.getTestDataname() + ";" + testErg.getTime() + "\n");_x000D_
		}_x000D_
		schreiber.close();_x000D_
	}_x000D_
_x000D_
	// Rekursive Funktion Mergesort_x000D_
	// Initialisierung Mergesort mit dem eingelesenen Array, dem linken Index, dem rechten Index_x000D_
	private static void mergeSort(int[] datensatz, int indexLinks, int indexRechts)_x000D_
	{_x000D_
		if (indexLinks < indexRechts) {_x000D_
			int mitte = (indexLinks + indexRechts) / 2;_x000D_
			mergeSort(datensatz, indexLinks, mitte);_x000D_
			mergeSort(datensatz, mitte + 1, indexRechts);_x000D_
			merge(datensatz, indexLinks, mitte, indexRechts);_x000D_
		}_x000D_
	}_x000D_
_x000D_
	//Merge - Methode, die in Mergesort aufgerufen wird_x000D_
	private static void merge(int[] datensatz, int l, int m, int r)_x000D_
	{_x000D_
		// H = Hilfsarray, zum Zwischenspeichern, mit der Länge des Arrays A_x000D_
		int hilfsArray[] = new int[datensatz.length];_x000D_
_x000D_
		// definiere i = linker Index, solange i kleiner gleich rechter Index, führe aus und erhöhe i_x000D_
		for (int i = l; i <= r; i++) {_x000D_
			// Zwischenspeichern von Array datensatz[i] nach hilfsarray[i]_x000D_
			hilfsArray[i] = datensatz[i];_x000D_
		}_x000D_
		// Laufzeitvariablen i, j und k für die while - Schleifendurchläufe_x000D_
		int i = l;_x000D_
		int j = m + 1;_x000D_
		int k = l;_x000D_
		// solange i kleiner gleich mittlerer Index UND j kleiner gleich rechter Index,_x000D_
		while (i <= m && j <= r) {_x000D_
_x000D_
			// Kopiere kleineren aktuellen Wert hilfsArray[j] -> datensatz[k] bzw. hilfsArray[i] -> datensatz[k]_x000D_
			// Erhöhe aktuellen Index von Teilarray mit kleinerem Wert_x000D_
			// Erhöhe aktuellen Index von H_x000D_
_x000D_
			// Wenn H an der Stelle i kleiner gleich H an der Stelle J, dann setze H[i] auf A[k] erhöhe i um eins_x000D_
			if (hilfsArray[i] <= hilfsArray[j]) {_x000D_
				datensatz[k] = hilfsArray[i];_x000D_
				i++;_x000D_
				// ansonsten setze H an der Stelle j auf A[k] und erhöhe j um 1_x000D_
			} else {_x000D_
				datensatz[k] = hilfsArray[j];_x000D_
				j++;_x000D_
			}_x000D_
			// Erhöhe k, die Zählvariable des Arrays A um eins,_x000D_
			// um die nächste Position im Array A im kommenden Durchlauf einzufügen_x000D_
			k++;_x000D_
		}_x000D_
_x000D_
		// übertrage Werte des noch nicht vollständig durchlaufenen Teilarrays nach H_x000D_
		// Kopiere H nach A (von Index l bis Index r)_x000D_
		while (i <= m) {_x000D_
			datensatz[k] = hilfsArray[i];_x000D_
			k++;_x000D_
			i++;_x000D_
		}_x000D_
_x000D_
		while (j <= r) {_x000D_
			datensatz[k] = hilfsArray[j];_x000D_
			k++;_x000D_
			j++;_x000D_
_x000D_
		}_x000D_
	}_x000D_
_x000D_
_x000D_
	// Hilfsklasse zum speichern von Testergebnissen_x000D_
	private static class TestErgebnis_x000D_
	{_x000D_
		private final String testDataname;_x000D_
		private final Double time;_x000D_
_x000D_
		public TestErgebnis(String testDataname, Double time)_x000D_
		{_x000D_
			this.testDataname = testDataname;_x000D_
			this.time = time;_x000D_
		}_x000D_
_x000D_
		public String getTestDataname()_x000D_
		{_x000D_
			return testDataname;_x000D_
		}_x000D_
_x000D_
		public Double getTime()_x000D_
		{_x000D_
			return time;_x000D_
		}_x000D_
	}_x000D_
}_x000D_

//Deklaration der main Methode_x000D_
import java.io.File;_x000D_
import java.io.FileWriter;_x000D_
import java.io.IOException;_x000D_
import java.util.ArrayList;_x000D_
import java.util.Arrays;_x000D_
_x000D_
/**_x000D_
 * Dateiname    : Mergesort.java_x000D_
 * Beschreibung : Einsendeaufgabe 2 für den Kurs Algorithmen_x000D_
 *_x000D_
 * @author Tobias Wagner (s79080@beuth-hochschule.de)_x000D_
 * @version 1.00, 02.12.2019_x000D_
 */_x000D_
_x000D_
// Klasse Mergesort zum Sortieren von Arrays und zum Testen der gegebenen Dateien Rand... und Sort..._x000D_
// Jeweils mit Anfangs- und Endzeit_x000D_
public class Mergesort_x000D_
{_x000D_
_x000D_
	private static String[] testDaten = {"Rand10_1", "Rand10_2", "Rand20_1", "Rand20_2",_x000D_
			"Rand50_1", "Rand50_2", "Rand100_1", "Rand100_2",_x000D_
			"Rand200_1", "Rand200_2", "Rand500_1", "Rand500_1",_x000D_
			"Rand1000_1", "Rand1000_2", "Rand10000_1", "Rand10000_2",_x000D_
			"Rand100000_1", "Rand100000_2", "Sort10_1", "Sort20_1", "Sort50_1", "Sort100_1", "Sort200_1",_x000D_
			"Sort500_1", "Sort1000_1", "Sort10000_1", "Sort100000_1"};_x000D_
_x000D_
	//Deklaration der<SUF>
	public static void main(String[] args) throws IOException_x000D_
	{_x000D_
		ArrayList<TestErgebnis> ergebnisListe = new ArrayList<>();_x000D_
_x000D_
		for (String testFilename : testDaten) {_x000D_
			// Einlesen des zu bearbeitenden Arrays - Auswahl der Datei mit dem Array_x000D_
			int[] testDatensatz = FileIntArray.FileToIntArray(testFilename);_x000D_
_x000D_
			// Ausgeben des unsortierten Arrays_x000D_
			System.out.println(Arrays.toString(testDatensatz));_x000D_
_x000D_
			// Erfassen der Anfangszeit_x000D_
			double anfangszeit = System.nanoTime();_x000D_
_x000D_
			// Ausführen von mergeSort_x000D_
			mergeSort(testDatensatz, 0, testDatensatz.length - 1);_x000D_
_x000D_
			// Erfassen der Endzeit_x000D_
			double endzeit = System.nanoTime();_x000D_
_x000D_
			// Ausgabe des sortierten Arrays_x000D_
			System.out.println(Arrays.toString(testDatensatz));_x000D_
_x000D_
			// Ausgabe der benötigten Dauer für den Durchlauf von mergeSort_x000D_
			double dauer = endzeit - anfangszeit;_x000D_
			System.out.println("Die benötigte Zeit betraegt: " + dauer + " Nanosekunden");_x000D_
_x000D_
			// Speichern des Testergebnisses in unsere ergebnissliste_x000D_
			TestErgebnis testErgebnis = new TestErgebnis(testFilename, dauer);_x000D_
			ergebnisListe.add(testErgebnis);_x000D_
		}_x000D_
_x000D_
		File datei = new File("Testlaufergebnis.csv");_x000D_
		FileWriter schreiber = new FileWriter(datei);_x000D_
_x000D_
		// CSV Kopzeile_x000D_
		schreiber.write("Testlauf;Zeit\n");_x000D_
_x000D_
		for (TestErgebnis testErg : ergebnisListe) {_x000D_
			schreiber.write(testErg.getTestDataname() + ";" + testErg.getTime() + "\n");_x000D_
		}_x000D_
		schreiber.close();_x000D_
	}_x000D_
_x000D_
	// Rekursive Funktion Mergesort_x000D_
	// Initialisierung Mergesort mit dem eingelesenen Array, dem linken Index, dem rechten Index_x000D_
	private static void mergeSort(int[] datensatz, int indexLinks, int indexRechts)_x000D_
	{_x000D_
		if (indexLinks < indexRechts) {_x000D_
			int mitte = (indexLinks + indexRechts) / 2;_x000D_
			mergeSort(datensatz, indexLinks, mitte);_x000D_
			mergeSort(datensatz, mitte + 1, indexRechts);_x000D_
			merge(datensatz, indexLinks, mitte, indexRechts);_x000D_
		}_x000D_
	}_x000D_
_x000D_
	//Merge - Methode, die in Mergesort aufgerufen wird_x000D_
	private static void merge(int[] datensatz, int l, int m, int r)_x000D_
	{_x000D_
		// H = Hilfsarray, zum Zwischenspeichern, mit der Länge des Arrays A_x000D_
		int hilfsArray[] = new int[datensatz.length];_x000D_
_x000D_
		// definiere i = linker Index, solange i kleiner gleich rechter Index, führe aus und erhöhe i_x000D_
		for (int i = l; i <= r; i++) {_x000D_
			// Zwischenspeichern von Array datensatz[i] nach hilfsarray[i]_x000D_
			hilfsArray[i] = datensatz[i];_x000D_
		}_x000D_
		// Laufzeitvariablen i, j und k für die while - Schleifendurchläufe_x000D_
		int i = l;_x000D_
		int j = m + 1;_x000D_
		int k = l;_x000D_
		// solange i kleiner gleich mittlerer Index UND j kleiner gleich rechter Index,_x000D_
		while (i <= m && j <= r) {_x000D_
_x000D_
			// Kopiere kleineren aktuellen Wert hilfsArray[j] -> datensatz[k] bzw. hilfsArray[i] -> datensatz[k]_x000D_
			// Erhöhe aktuellen Index von Teilarray mit kleinerem Wert_x000D_
			// Erhöhe aktuellen Index von H_x000D_
_x000D_
			// Wenn H an der Stelle i kleiner gleich H an der Stelle J, dann setze H[i] auf A[k] erhöhe i um eins_x000D_
			if (hilfsArray[i] <= hilfsArray[j]) {_x000D_
				datensatz[k] = hilfsArray[i];_x000D_
				i++;_x000D_
				// ansonsten setze H an der Stelle j auf A[k] und erhöhe j um 1_x000D_
			} else {_x000D_
				datensatz[k] = hilfsArray[j];_x000D_
				j++;_x000D_
			}_x000D_
			// Erhöhe k, die Zählvariable des Arrays A um eins,_x000D_
			// um die nächste Position im Array A im kommenden Durchlauf einzufügen_x000D_
			k++;_x000D_
		}_x000D_
_x000D_
		// übertrage Werte des noch nicht vollständig durchlaufenen Teilarrays nach H_x000D_
		// Kopiere H nach A (von Index l bis Index r)_x000D_
		while (i <= m) {_x000D_
			datensatz[k] = hilfsArray[i];_x000D_
			k++;_x000D_
			i++;_x000D_
		}_x000D_
_x000D_
		while (j <= r) {_x000D_
			datensatz[k] = hilfsArray[j];_x000D_
			k++;_x000D_
			j++;_x000D_
_x000D_
		}_x000D_
	}_x000D_
_x000D_
_x000D_
	// Hilfsklasse zum speichern von Testergebnissen_x000D_
	private static class TestErgebnis_x000D_
	{_x000D_
		private final String testDataname;_x000D_
		private final Double time;_x000D_
_x000D_
		public TestErgebnis(String testDataname, Double time)_x000D_
		{_x000D_
			this.testDataname = testDataname;_x000D_
			this.time = time;_x000D_
		}_x000D_
_x000D_
		public String getTestDataname()_x000D_
		{_x000D_
			return testDataname;_x000D_
		}_x000D_
_x000D_
		public Double getTime()_x000D_
		{_x000D_
			return time;_x000D_
		}_x000D_
	}_x000D_
}_x000D_
