#include <stdio.h>
#include <time.h>
#define MAX 1000000


int v[MAX];
int limite;


void RANDOMIZE(){
    time_t t;
    srand((unsigned) time(&t));
}


int random(int massimo){
	return 1+rand() % massimo;
}


void scambio(int v[], int indice1, int indice2){
	int dep = v[indice1];
	v[indice1] = v[indice2];
	v[indice2] = dep;
}


void bubble(int v[]){
	int scambiato, i;
	do{
		scambiato = 0;
		for(i = 0; i < limite-1; i++){
			if(v[i] > v[i+1]){
				scambio(v, i, i+1);
				scambiato = 1;
			}
		}
	}while(scambiato);
}


void select(int v[]){
	int i, j, minimo;
	for(i = 0; i < limite; i++){
		for(j = i, minimo = i; j < limite; j++){
			if(v[j] < v[minimo]){
				minimo = j;
			}
		}
		if(minimo != i){
			scambio(v, minimo, i);	
		}
	}
}


void insert(int v[]){
	int i, j, valore;
	for(i = 1; i < limite; i++){
		valore = v[i];
		j = i - 1;
		while(j >= 0 && v[j] > valore){
			v[j+1] = v[j];
			j--;
			v[j+1] = valore;
		}
	}
}


void quicksort(int v[], int sx, int dx){
	if(sx >= dx){
		return;
	}
	int i = sx;
	int j = dx;
	int pivot = v[(sx+dx)/2];
	while(i <= j){
		while(v[i] < pivot){
			i++;
		}
		while(v[j] > pivot){
			j--;
		}
		if(i <= j){
			scambio(v, i, j);
			i++;
			j++;
		}
	}
	quicksort(v, sx, j);
	quicksort(v, i, dx);
}


int media(int a, int b){
	return (a+b)/2;
}


int dimezzamenti(int n){
	int dim = 0;
	while(n > 0){
		dim++;
		n /= 2;
	}
	return dim;
}


int ricerca_lineare(int v[], int valore){
	int i;
	for(i = 0; i < limite; i++){
		if(v[i] == valore){
			return i;
		}
	}
	return -1;
}


int ricerca_dicotomica(int v[], int valore){
	int sx = 0;
	int dx = limite-1;
	int medio;
	int c = 0;
	int dimezza = dimezzamenti(limite);
	while(c != dimezza){
		medio = media(sx, dx);
		if(v[medio] == valore){
			return medio;
		}else if(v[medio] > valore){
			dx = medio;
		}else{
			sx = medio;
		}
		c++;
	}
	return -1;
}


int main(){
	int scelta, i, j, massimo, stampa, valore, indiceRicerca;
	int run = 1;
	char continua;
	time_t inizio, fine;
	RANDOMIZE();
	while(run){
		printf("\n1. Dimensionamento vettore\n");
		printf("2. Riempimento vettore\n");
		printf("3. Stampa vettore\n");
		printf("4. Bubble sort\n");
		printf("5. Select sort\n");
		printf("6. Insert sort\n");
		printf("7. Quick sort\n");
		printf("8. Ricerca lineare\n");
		printf("9. Ricerca dicotomica [se il vettore e' ordinato]\n");
		printf("0. Esci\n\n");
		printf("Cosa vuoi fare? ");
		scanf("%d", &scelta);
		switch(scelta){
			case 0:
				run = 0;
				break;
			case 1:
				printf("Inserire la dimensione del vettore: ");
				scanf("%d", &limite);
				break;
			case 2:
				printf("Quale deve essere il valore massimo nel vettore? ");
				scanf("%d", &massimo);
				for(i = 0; i < limite; i++){
					v[i] = random(massimo);
				}
				break;
			case 3:
				stampa = 1;
				for(i = 0; stampa && i < limite; i++){
					printf("Elemento %d: %d\n", i+1, v[i]);
					if((i+1) % 20 == 0){
						printf("\nContinuo a stampare? [s/n]: ");
						scanf(" %c", &continua);
						if(continua == 'n' || continua == 'N'){
							stampa = 0;
						}
					}
				}
				break;
			case 4:
				inizio = time(NULL);
				bubble(v);
				fine = time(NULL);
				printf("Tempo passato: %0.3f", difftime(fine, inizio));
				break;
			case 5:
				inizio = time(NULL);
				select(v);
				fine = time(NULL);
				printf("Tempo passato: %0.3f", difftime(fine, inizio));
				break;
			case 6:
				inizio = time(NULL);
				insert(v);
				fine = time(NULL);
				printf("Tempo passato: %0.3f", difftime(fine, inizio));
				break;
			case 7:
				inizio = time(NULL);
				quicksort(v, 0, limite-1);
				fine = time(NULL);
				printf("Tempo passato: %0.3f", difftime(fine, inizio));
				break;
			case 8:
				printf("Inserisci il valore da cercare nel vettore: ");
				scanf("%d", &valore);
				indiceRicerca = ricerca_lineare(v, valore);
				if(indiceRicerca < 0){
					printf("L'elemento non e' presente nel vettore.\n");
				}else{
					printf("L'elemento si trova alla posizione %d.\n", indiceRicerca);
				}
				break;
			case 9:
				printf("Inserisci il valore da cercare nel vettore: ");
				scanf("%d", &valore);
				indiceRicerca = ricerca_dicotomica(v, valore);
				if(indiceRicerca < 0){
					printf("L'elemento non e' presente nel vettore.\n");
				}else{
					printf("L'elemento si trova alla posizione %d.\n", indiceRicerca);
				}
				break;
		}
	}
	return 0;
}