// In questo file sono contenute alcune funzioni viste
// durante le esercitazioni sui vettori, in particolare alcuni algoritmi
// di ordinamento e ricerca
//
// - l'ordinamento di un vettore mediante algoritmo "selection sort"
// - l'ordinamento di un vettore mediante algoritmo a bolle ("bubble sort")

		 
// - ricerca lineare su porzione di un vettore
// - ricerca binaria su porzione di vettore (assumendolo ordinato)



	
#include <iostream>
using namespace std;

// -- FUNZIONI DI UTILITA' ---------------------------------------

// scambia l'elemento i del vettore con l'elemento j
void scambia(int v[],int i, int j){
	int aux = v[i];
	v[i]=v[j];
	v[j]=aux;
}

// restituisce la posizione dell'elemento avente valore minimo,
// fra gli elementi di v aventi indice nel range [infe, n-1]
int posMinimo(const int v[], int infe, int n){
	int min = v[infe];
	int posMin = infe;	
	for (int i=infe+1; i<n; i++)
		if ( v[i]<min ){
			posMin = i;
			min = v[i];
		}		
	return posMin;
}

// mostra a video gli elementi del vettore
void stampa(int *v, int nElem){
	cout<<"["<<v[0];
	for(int i=1; i<nElem; i++)
		cout<<", "<<v[i];
	cout<<']';
}

// legge gli elementi del vettore da tastiera
void leggi(int v[], int n){
	for (int i=0; i<n; i++){
		cout<<"v["<<i<<"] = ";
		cin>>v[i];		
	}
}

// -- FINE FUNZIONI DI UTILITA' -----------------------------------

// ORDINAMENTO

// selection sort basato sulla funzione di utilita' "posMinimo"
void selectionSort(int v[], int nElem){
	for (int i=0; i<nElem; i++){
		int posMin = posMinimo(v,i,nElem);
		if ( posMin != i )
			scambia(v,i,posMin);
	}
}

// selection sort (versione compatta, senza uso di funzioni di utilita')
void selectionSort2(int v[], int nElem){     
	for (int i=0; i<nElem; i++)
		for (int j=i+1; j<nElem; j++)
		if ( v[j] < v[i] ){
			int aux = v[i];
			v[i] = v[j];
			v[j]=aux;
		}			
}

// bubble sort con ottimizzazione (appena nel ciclo piu' interno 
// non si fanno piu' scambi si interrompe il ciclo esterno)
void bubbleSort(int v[], int n){ 
	bool ordinato = false;
	for (int i = n-1; i > 0  && !ordinato; i--){
		ordinato = true;
		for (int j = 0; j < i; j++)
			if( v[j] > v[j+1] ){
				scambia(v, j, j+1);
				ordinato = false;
			}
	}
}


// RICERCA

// ricerca lineare della posizione del primo elemento avente valore k
// all'interno dell'intervallo [infe, supe]. Se l'elemento viene trovato,
// la funzione restituisce true (e mette in pos la posizione in cui e' stato
// trovato l'elemento). Restituisce false altrimenti.
bool ricLin(int v[], int infe, int supe, int k, int &pos){
	bool trovato = false;
	while ((!trovato) && (infe <= supe))
	{	
		if (v[supe] == k)
		{
			pos = supe;
			trovato = true;
   		}
		supe--;
   	}
	return trovato;
}

// ricerca binaria. Ha lo stesso scopo della funzione precedente, ma funziona solo
// se il vettore di partenza e' ordinato. Potendo assumere che il vettore
// sia ordinato, l'algoritmo di ricerca binaria e' molto piu' efficiente di quello 
// a ricerca lineare.
bool ricBin(int ordVett[], int infe, int supe, int k, int &pos){
	while (infe <= supe){
       	int medio = (infe + supe) / 2; // calcola l'indice centrale
		if (ordVett[medio] == k){
			pos = medio;   			   // trovato
			return true;
		}else{
			if (ordVett[medio] > k)
				supe = medio - 1;      // ricerca nella meta' inferiore
			else
				infe = medio + 1;      // ricerca nella meta' superiore
		}
	}
    return false;
} 


int main(){
	
	const int maxElem = 9;
	int vett[maxElem]={4,8,2,7,1,3,9,15,12};
    	
	cout<<"Quanti elementi deve avere il vettore ( <9 ) ?";
	int nElem;
	cin>>nElem;
	if (nElem > maxElem)
		nElem = maxElem;

	leggi(vett,nElem);

	//selectionSort(vett,nElem);	
	bubbleSort(vett,nElem);
		
	cout<<endl<<"Vettore ordinato: "<<endl;
	stampa(vett,nElem);
	cout << endl;
	
	cout<<endl<<"Ricerca della posizione dell'elemento avente valore vett[nElem/2]"<<endl;
	int posElemento;
	int val = vett[nElem/2];
	
	/*
	cout<<"Inserisci l'elemento da cercare nel vettore ";	
	cin>>val;
	*/
		
	
	// cout<<"RICERCA LINEARE"<<endl;
	bool trovato = ricLin(vett, 0, nElem-1, val, posElemento);
	
		
	//cout<<"RICERCA BINARIA"<<endl;
	// bool trovato = ricBin(vett, 0, nElem-1, val, posElemento);	
	
	if (trovato)
		cout<<"Elemento "<<val<<" trovato in posizione "<<posElemento<<" (NB: l'indice e' 0-based)"<<endl;
	else
		cout<<"Elemento "<<val<<" non presente"<<endl;

	return 0;
}