#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

#define GROESSE 20

// Initialisierung eines Feldes mit Zufallszahlen

void init(int feld[], int feld_groesse) {
	for (int i=0; i < feld_groesse; i++) 
		feld[i] = rand()%GROESSE;
}

// Ausgabe eines Feldes 

void print(int feld[], int feld_groesse) {
	cout << "[";
	for (int i=0; i < feld_groesse; i++) 
		cout << feld[i] << " ";
	cout << "]" << endl;
}

// Hilfsfunktion zum Vertauschen zweier Feldelemente
// (verwendet in Bubblesort)

void swap(int feld[], int idx1, int idx2) {
	int tmp = feld[idx1];
	feld[idx1] = feld[idx2];
	feld[idx2] = tmp;
}

// Bubblesort

void bubblesort (int feld[], int feld_groesse) {

	// Mit swapped wird in jedem Schleifendurchlauf getestet, ob
	// eine Vertauschung durchgeführt wurde - wenn nicht, ist das
	// Feld fertig sortiert	
	bool swapped; 
	// In jedem Durchlauf rutscht die größte Zahl automatisch an's
	// aktuelle Ende=max - ab dieser Position müssen wir im nächsten
	// Durchlauf nicht mehr testen (Optimierung)
	int max = feld_groesse - 1; 
	do {
	    swapped = false;
	    // In jedem Durchlauf: gehe durch das Feld, und wenn zwei
	    // aufeinanderfolgende Elemente im falschen Größebverhältnis sind,
	    // tausche diese
	    for (int i = 0; i < max; i++) {
		if (feld[i] > feld[i + 1]) {
		    swap (feld, i, i + 1);
		    swapped = true;
		}
	    }
	    max--;
	} while (swapped);
}

// Rekursive Funktion zur Durchführung von Mergesort

void msort (int feld[], int feld_groesse, int l, int r) {
	
	int i, j, k;
	// Das Hilsfeld b wird für das Mischen (Merge) benötig
	int* b = new int[feld_groesse]();

	// Algorithmus setzt Teile un Herrsche um:
	// ---------------------------------------
	// TEILE: zerlege das Feld rekursiv in immer kleinere Bereiche mit den 
	// Grenzen l (links) und r (rechts), solange diese sich nicht überschneiden.
	// Rekursion endet im Trivialfall r=l - ein-elementiges Feld ist immer 
	// sortiert
	if (r > l) {
		int mid = (r + l) / 2;
		msort (feld, feld_groesse, l, mid);
		msort (feld, feld_groesse, mid + 1, r);
		// an dieser Stelle sind die "von unten kommenden" Teillisten
		// schon in sich sortiert
		
		// HERRSCHE: Mische die sortierten Teillisten über das Hilfsfeld b
		// wie folgt:
		// kopiere die untere sortierte Teilliste in das Hilfsfeld
		for (i = mid + 1; i > l; i--)
			b[i - 1] = feld[i - 1];
		// kopiere die obere sortierte Teilliste in das Hilfsfeld
		// (hier in umgekehrter Reihenfolge)
		for (j = mid; j < r; j++)
			b[r + mid - j] = feld[j + 1];
		// kopiere aus b jeweils das kleinere der beiden Elemente der
		// Teillisten zurück in das Originalfeld 
		for (k = l; k <= r; k++)
			if (b[i] < b[j])
				feld[k] = b[i++];
			else
				feld[k] = b[j--];
	}
}

// Rekursionseinstieg für Mergesort
// -> eigentliche Arbeit macht msort() rekursiv 

void mergesort (int feld[], int feld_groesse) {
	msort (feld, feld_groesse, 0, feld_groesse-1);
}

int main() {
	srand(time(NULL));

	cout << "Bubblesort ..." << endl;
	int feld1[GROESSE];	
	init(feld1,GROESSE);
	print(feld1,GROESSE);
	bubblesort(feld1,GROESSE);
	print(feld1,GROESSE);
	
	cout << "Mergesort ..." << endl;
	int feld2[GROESSE];
	init(feld2,GROESSE);
	print(feld2,GROESSE);
	mergesort(feld2,GROESSE);
	print(feld2,GROESSE);
	return 0;
}