#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void bubbleSort(int size, int array[]){
	//Einige Variablen deklarieren
	int temp;
	int i;
	int j;
	
	//Starte die beiden Schleifen. Aeussere Schleife
	for(i=0; i<size; i++){
		//Innere Schleife
		for(j = size; j>i; j--){
			//Wenn das Element kleiner ist, tausche
			if (array[j-1] > array[j]){
				temp = array[j];
				array[j] = array[j-1];
				array[j-1] = temp;
			}
		}
	}
}

int teste(double zeit, int size){
	//Deklaration von einigen Variablen
	clock_t tStart, tEnd;
	int *array;
	int i;
	double secs;
	
	//Array allokieren
	array = malloc(size*sizeof(int));
	//Array fuellen
	for(i = 0; i<size; i++){
		array[i] = size-i;
	}
	//Startzeitpunkt bestimmen
	tStart = clock();
	//Sortieren
	bubbleSort(size, array);
	//Endzeitpunkt bestimmen und Dauer berechnen
	tEnd = clock();
	secs = (double)(tEnd - tStart) / CLOCKS_PER_SEC;
	
	//Mit Vorgabe vergleichen und entsprechenden Returncode liefern
	//Wenn die Sortierung signifikant kuerzer dauert 
	if(secs < zeit-0.01){
		printf("%u ist zu klein\n", size);
		return 1;
	}else if(secs > zeit+0.01){
		//Wenn die Sortierung signifikant laenger dauert
		printf("%u ist zu groß\n", size);
		return 2;
	}else{
		//Wenn alles passt
		printf("%u passt\n", size);
		return 0;
	}
}
	

int main( int argc, const char* argv[] ){
	//Globale Variablen deklarieren
		double vorgabe;
		int size;
		int size_before;
		int result;

	
	//Wenn genügend Argumente am Start sind, lies dir die Vorgabezeit aus.
	if(argc > 1){
		vorgabe = atof(argv[1]);
	}else{
		//Sonst beschwer dich
		printf("Zu wenig Argumente.\n");
		return 1;
	}
	
	//Wenn die Groesse irreal ist, beschwer dich
	if (vorgabe <= 0.0001){
		printf("Die angegebene Zeit kann nicht verarbeitet werden.\n");
		return 1;
	}
	
	//Binaere Annaeherung an die Vorgegebene Zeit
	//Variablen initialisieren
	size = 1000;
	size_before = 0;
	//Wert 4, da test niemals 4 zurueckliefert
	result = 4;
	//Solang test nicht behauptet, dass alles passt
	while(result != 0){
		//Fuehre Teste mit size aus, und guck nach, was raus kommt.
		result = teste(vorgabe, size);
		//Wenn der Durchlauf zu kurz ist, merk dir die Zeit, falls der naechste Aufruf zu groß ist, und verdopple die Größe
		if(result == 1){
			size_before = size;
			size = size*2;
			continue;
		}
		//Wenn der Durchlauf zu lang dauert, bestimme das Mittel aus dieser Groesse und dem Durchlauf davor, der ja zu kurz dauerte
		if(result == 2){
			size = (size + size_before)/2;
			continue;
		}
	}
	//Sobald die Schleife abbricht, ist size auf dem Optimalwert. Gib den Wert aus.
	printf("Die optimale Groesse fuer Vorgabe %f ist %u. \n", vorgabe, size);
	return 0;
	
	
}