Riporto qui il testo dell'esercizio:
"Creare un programma in linguaggio C che legga da file 1000 valori double, li memorizzi in
un vettore e li salvi in un file dopo aver effettuato l’ordinamento.
a. Effettuare l’ordinamento con merge sort
b. Effettuare l’ordinamento con quick sort
c. Stampare la posizione di ogni singolo valore nel file attraverso la funzione ftell"
Ho fatto due codici differenti, uno per il merge ed un altro per il sort:
#include <stdio.h>
#include <stdlib.h>
#define N 1000
double merge_sort(double vect[], int dim); //prototipi
double merge(double vect[], int mid, int dim); //prototipi
int main()
{
int c, i;
FILE *ifp;
double vect[N];
ifp=fopen("doublevect.dat", "w");
for(c=0; c<N; c++) {
vect[c]=rand()%10001/500.0;
fprintf(ifp, "%lf ", vect[c]); }
fclose(ifp);
FILE *ofp;
ofp=fopen("doublevect1.dat", "w");
if(ofp==NULL)
printf("Impossibile accedere al file\n");
else {
merge_sort(vect, N);
for(i=0; i<N; i++)
fprintf(ofp, "%lf %li\n", vect[i], ftell(ofp));
}
fclose(ofp);
}
double merge_sort(double vect[], int dim)
{
int indx;
indx=dim/2;
if(dim>1)
{
merge_sort(vect, indx);
merge_sort(vect+indx, dim-indx);
merge(vect, indx, dim);
}
}
double merge(double vect[], int mid, int dim)
{
int i,il,ir;
double *temp;
temp=(double*)malloc(dim*sizeof(double));
for(i=0; i<dim; i++)
temp[i]=vect[i];
il=0; ir=mid;
i=0;
while(il<mid && ir<dim)
{
if(temp[il]<=temp[ir])
vect[i++]=temp[ir++];
else
vect[i++]=temp[ir++];
}
if(il<mid)
{
while(il<mid)
vect[i++]=temp[il++];
}
else
while(ir<dim)
vect[i++]=temp[ir++];
}
#include <stdio.h>
#include <stdlib.h>
#define N 1000
void quicksort(double *vect[], int dim);
int partition(double *vect[], int dim);
void swap_pointers(double *v[], int i, int j);
int main()
{
double *vect1[N];
int c, i;
FILE *ifp;
ifp=fopen("qsortvect.dat", "w");
for(c=0; c<N; c++) {
vect1[c]=rand()%10001/500.0;
fprintf(ifp, "%lf ", vect1[c]); }
fclose(ifp);
FILE *ofp;
ofp=fopen("qsortvect1.dat", "w");
if(ofp==NULL)
printf("Impossibile accedere al file\n");
else {
quicksort(vect1, N);
for(i=0; i<N; i++)
fprintf(ofp, "%lf %li\n", vect1[i], ftell(ofp));
}
fclose(ofp);
}
void quicksort(double *vect[], int dim) //implementazione del quicksort
{
int a, d;
if(dim<=1) return;
d=partition(vect, dim);
quicksort(vect, d); //d è il pivot
quicksort(vect+d+1, dim-d-1); //tutto il vettore di destra
}
int partition(double *vect[], int dim)
{ //lascia nella posizione h il valore scelto come pivot
double *t;
int l=1, h=dim-1;
if(dim==1) return 0;
swap_pointers(vect, 0, dim/2);
while(l<=h)
{
while(l<dim && vect[l]<vect[0])
l++;
while(h>0 && vect[h]>vect[0])
h--;
if(l<=h)
{
swap_pointers(vect, l, h);
l++;
h--;
}
} //chiude il while
swap_pointers(vect, h, 0); //scambio il pivot che era in posizione 0 con quello in h
return h;
}
void swap_pointers(double *v[], int i, int j)
{
double *t;
t=v[i];
v[i]=v[j];
v[j]=t;
}
Il codice con il merge sort funziona però non esegue correttamente l'ordinamento, mentre quello implementato con il quick non riesco a compilarlo perché a bloccarmi credo ci sia uno scorretto utilizzo del vettore di puntatori... Grazie in anticipo!