/*
* Nome del file: main.c
* Autore - Daniele Brundu Matricola:4655895
* Gennaio 2009
* Realizzazione per Riconoscimento 1cfu
* Il programma legge da file e ordina tramite scelta dell'utente
* del tipo di algoritmo una serie di valori virtualizzando il vettore ordinato
*/
#include <string.h>
#include <stdio.h> //libreria per lettura da input e scrittura a video
//(standard input-output header)
#include <stdlib.h> /* dichiara funzioni e costanti di utilità generale:
* allocazione della memoria, controllo dei processi,
* conversione tra tipi ecc
*/
/*SI PARTE CON LA PROTOTIPAZIONE DELLE FUNZIONI AFFICHE'
*SI POSSANO UTILIZZARE "SENZA ESSERE DEFINITE"
*/
int main(void); //prototipo della funzione
void sequential_sort(float * V,int N,int * Perm); //prototipo della funzione
void bubble_sort(float * V,int N,int * Perm); //prototipo della funzione
void merge_sort(float * V,int N); //prototipo della funzione
void _mergesort(float * V,int N,float * tmp); //prototipo della funzione
void merge(float * V,int N,int Nl); //prototipo della funzione
void quicksort(float * V,int N); //prototipo della funzione
int partition(float * V,int N); //prototipo della funzione
void swap(int * Perm,int a,int b); //prototipo della funzione
//prototipo della funzione
void printArray(float * V, int N); //prototipo della funzione
void printPermutatedArray(float * V, int N, int * Perm); //prototipo della funzione
int main(void)
/* apre un file testo e vi legge i valori di un vettore.
Assume che i dati nel file siano codifcati in sequenza senza
specificarne all'inizio il numero, dunque con il tracciato:
{float valore}
*/
{
FILE *fhandle; //successivamente verrà utilizzato per aprire il file e leggerlo,dichiara fhandle
int N; //variabile di tipo int con nome N
float * V;
int count; //variabile di tipo int con nome count
float value; //variabile di tipo float(reale) con nome value
int * Perm;
#define NAlgoritmi 4 //Direttiva di definizione che associa alla costante NAlgoritmi valore 2
char nomeAlgoritmo[NAlgoritmi][18]; //definisce array bidimensionlae di grandezza 4x16 per le stringhe
strcpy(nomeAlgoritmo[0],"sequential sort"); //copia la stringa nell'indice 0
strcpy(nomeAlgoritmo[1],"bubble sort"); //copia la stringa nell'indice 1
strcpy(nomeAlgoritmo[2],"merge sort"); //copia la stringa nell'indice 2
strcpy(nomeAlgoritmo[3],"quick sort"); //copia la stringa nell'indice 3
printf("\n vettoreN.txt"); // stampa il nome del file
fhandle = fopen("vettoreN.txt", "r"); //apre il file in lettura
N=0;
while(fscanf(fhandle,"%f",&value)!=EOF){ //condizione che la lunghezza dello stream
//sia diversa dll'end of file
N++; //incrementa N e scrive su value di appoggio
}
printf("\n Il vettore nel file ha lunghezza : %d", N); //stampa lunghezza file
Perm=(int *)malloc(N*sizeof(int)); //in questo modo lo alloca nello stack
rewind(fhandle); //reinizializza lettura del file da capo
V=(float *)malloc(N*sizeof(float)); //malloc: abilita gestione dinamica della memoria
//sizeof restituisce la dimensione del tipo di dato da allocare
//quindi crea un buffer con dimensione 32 bits(cadauno)per N
rewind(fhandle); //reinizializza lettura del file da capo
for(count=0;count<N;count++){
fscanf(fhandle,"%f",&V[count]); //legge da fhandle (file) e lo mette nella posizione [count]
}
printf("\n Il vettore in ingresso e': ");
printArray(V,N); //stampa l'array
fflush(fhandle); //svuota fhandle
fclose(fhandle); //chiude la lettura
//NEL PROSSIMO CICLO SELEZIONIAMO L'ALGORITMO DA USARE E CONSIDERANDO
//CHE PER UNA PERSONA E' PIU' SEMPLICE NELLA SELEZIONE PARTIRE DA 1
//E NON DA ZERO,CHIEDO DI INSERIRE I VALORI
//DA UNO A 4 MA IN REALTA' SUBITO DOPO L'INSERIMENTO
//LI SFASO DI UNO ADATTANDOLI ALL'ARRAY
//CHE PARTE DA 0!!
count = 5; //lo imposto a 4 per permettere al ciclo di partire(faccio questo affinchè
//se successiamente si inserisce un valore superiore riparte il ciclo fino a quando
//il valore non è compreso fra 1 e 4 che nel ciclo divente fra 0 e 3.
//E' "complesso" nella logica ma funzionale al 100% in quanto adatto all'utente!
while(count > 4 || count < 1){
printf("\n\n Selezionare un algoritmo di ordinamento premendo :");
printf("\n 1. per utilizzare il Sequential Sort ");
printf("\n 2. per utilizzare il Bubble Sort ");
printf("\n 3. per utilizzare il Merge Sort ");
printf("\n 4. per utilizzare il Quick Sort \n");
scanf("%u",&count);
} //con un semplice decremento un'adattabilità maggiore all'utenza.
printf("\n L'algoritmo selezionato e' : %s",nomeAlgoritmo[count-1]);
//il valore algoritmo in questo momento deve essere per forza compreso fra 0 e 3 in quanto altrimenti
//il ciclo while si reinizializzerebbe.
switch(count){ //uso il comando switch che è più comodo in questi casi
case 1: //se il valore è 0 passo al sequential sort
sequential_sort(V,N,Perm);
printf("\n\n il vettore ordinato con %s e':", nomeAlgoritmo[count-1]);
printPermutatedArray(V,N,Perm);//richiamo la funzione di stampa
break;
case 2: //se il valore è 1 passo al bubble sort
bubble_sort(V,N,Perm);
printf("\n\n il vettore ordinato con %s e':", nomeAlgoritmo[count-1]);
printPermutatedArray(V,N,Perm); //richiamo la funzione di stampa
break;
case 3: //se il valore è 2 passo a merge sort
merge_sort(V,N);
printf("\n\n il vettore ordinato con %s e':", nomeAlgoritmo[count-1]);
printPermutatedArray(V,N,Perm);//richiamo la funzione di stampa
break;
case 4: //se il valore è 3 passo al quick sort(il più veloce)
quicksort(V,N);
printf("\n\n il vettore ordinato con %s e':", nomeAlgoritmo[count-1]);
printPermutatedArray(V,N,Perm);//richiamo la funzione di stampa
break;
}
free (V); //libera la memoria altrimenti
free (Perm);
printf("\n ");
system("PAUSE"); //comando DOS
return 0;
}
//cerco l'elemento con il valore più alto e lo scambio con quello dell'ultima
//posizione dell'array,e così via per n-1 volte.
//Invece di modificare gli elementi dell'array,costruisco un vettore di
//permutazione che fornisce la sequenza attraverso la quale visitiamo il vettore
//V in modo ordinato.Costo O(N).
void sequential_sort (float * V,int N,int * Perm){
int count;
int count_of_max;
int iter;
for(count = 0;count<N;count++)
Perm[count]=count;
for(iter=0;iter<N-1;iter++){
for(count=1,count_of_max=0;count<N-iter;count++){
if(V[Perm[count]]>V[Perm[count_of_max]]){
count_of_max = count;
}
swap(Perm,count_of_max,N-iter-1);
}
}
}
//confronta l'elemento con il suo successivo e li scambia se count<count+1
void bubble_sort(float * V,int N,int * Perm){
int count;
int iter;
int iter_without_swap;
int swap_found;
iter=0;
iter_without_swap=0;
while(iter_without_swap == 0){
for(count=0,swap_found=0;count<N-iter-1;count++){
if(V[Perm[count]]<V[Perm[count+1]]){
swap(Perm,count,count+1);
swap_found=1;
}
}
if(swap_found==0)
iter_without_swap=1;
else iter++;
}
}
//duè metà del vettore vengono ordinate separatamente e poi
//fuse in modo da ottenere un vettore ordinato
void merge_sort(float * V,int N){
float * tmp;
tmp=(float *)malloc(N*sizeof(float));
_mergesort(V,N,tmp);
free(tmp);
}
//funzioe che ordina il vettore v sfruttando il vettore tmp di appoggio
//e riutilizzandolo nelle diverse istanze
void _mergesort(float * V,int N,float * tmp){
if(N>2){
_mergesort(V,N/2,tmp);
_mergesort(&V[N/2],N-N/2,&tmp[N/2]);
merge(V,N,N/2);
}
else{
if(V[0]<V[1]){
// _swap(V,0,1);
}
}
}
//funzione che fonde i due semi-vettori ordinati di V di lunghezza Nl e N-Nl
void merge(float * V,int N,int Nl){
int l,r,count;
float * tmp;
tmp=(float *)malloc(Nl*sizeof(int));
for(count=0;count<Nl;count++)
tmp[count]=V[count];
l=0;
r=0;
while(l<Nl && r<N-Nl){
if(tmp[l]<V[Nl+r]){
V[l+r]=tmp[l];
l++;
}
else{
V[l+r]=V[Nl+r];
r++;
}
}
while(l<Nl){
V[l+r]=tmp[l];
l++;
}
free(tmp);
}
//considera un pivot e porta gli elementi minori a sx e i maggiori a dx.
void quicksort(float * V,int N){
int q;
q=partition(V,N);
quicksort(V,q-1);
quicksort(&V[q+1],N-q-1);
}
//considera il pivot e riordina i valori del vettore maggiori e minori ad esso
//e spostando il pivot in posizione tale dove alla sua sinistra risulteranno solo
//elementi minori ad esso
int partition(float * V,int N){
int l;
int r;
float pivot;
pivot=V[0];
l=0;
r=N;
while(l<r)
{ do { r--; } while(V[r]>pivot && r>l);
if(r!=l)
{ do{ l++;} while (V[l]<=pivot && l<r);
// _swap(V,l,r);
}
}
// _swap(V,l,0);
return l+1;
}
//funzioni di swap
void swap(int * Perm,int a,int b){ //lavoro con puntatori
int temp = Perm[a];
Perm[a]=Perm[b];
Perm[b]=temp;
}
//funzioni di stampa dei vettori
void printArray(float * V, int N){
int count;
for(count=0;count<N;count++)
printf("\n V[%d]=%4.2f",count,V[count]);
}
void printPermutatedArray(float * V, int N, int * Perm){
int count;
for(count=0;count<N;count++)
printf("\n V[%d]=%4.2f",count,V[Perm[count]]);
}