[C] qsort() e algoritmi di ordinamento
Salve ragazzi, io avrei una domanda sul quicksort ed in particolare sulla funzione qsort().
Sto facendo un esercizio che chiede di leggere delle parole da un file (che ne contiene 104890) e le richieste sono di ordinare queste parole con:
a)quicksort
b)quicksort ottimizzato
c)qsort()
Su a) e b) non ho problemi, ma avrei una curiosità sulla c)
La richiamo così:
Voglio implementare confr
Scrittura 1:
Scrittura 2:
Io ho svolto l'esercizio con la scrittura 2, mentre nella soluzione dell'esercizio c'è la scrittura 1.
La mia domanda è se queste 2 scritture sono equivalenti o se c'è qualche ragione per cui è più conveniente usare la 1.
Grazie mille per l'attenzione
Sto facendo un esercizio che chiede di leggere delle parole da un file (che ne contiene 104890) e le richieste sono di ordinare queste parole con:
a)quicksort
b)quicksort ottimizzato
c)qsort()
Su a) e b) non ho problemi, ma avrei una curiosità sulla c)
La richiamo così:
qsort(parole, n, sizeof(char*),confr);
Voglio implementare confr
Scrittura 1:
int confr(const void *a,const void *b)
{
return strcmp(*(char **)a,*(char **)b);
}
Scrittura 2:
int confr(char **a, char**b)
{
return strcmp(*a,*b);
}
Io ho svolto l'esercizio con la scrittura 2, mentre nella soluzione dell'esercizio c'è la scrittura 1.
La mia domanda è se queste 2 scritture sono equivalenti o se c'è qualche ragione per cui è più conveniente usare la 1.
Grazie mille per l'attenzione
Risposte
Il terzo argomento della funzione qsort è un puntatore ad una funzione che ritorna un intero e che possiede due puntatori costanti a void come argomenti. La prima scrittura fa esplicitamente il cast mentre la tua la fa implicitamente. La differenza è tutta qui.
Ok, capito, grazie mille
Il primo modo è corretto, il secondo no, ha comportamento indefinito. qsort() si aspetta un puntatore a funzione di un certo tipo, non puoi passargliene un altro.
Nella pratica, almeno sulle architetture più comuni, potrebbero essere equivalenti.
Nella pratica, almeno sulle architetture più comuni, potrebbero essere equivalenti.
Ok allora userò la prima scrittura.
E poi volevo chiedere se mettere le "free" alla fine del MAIN è veramente necessario.
Cioè in ogni caso alla fine del programma non se le libera da solo?
Il mio problema è che ho scritto un programma con queste 16 opzioni:
Il programma funziona perfettamente a meno che non scelga 12-13-14.
In quel caso continua a funzionare, ma all'uscita dal programma, non esce correttamente, ma crasha.
Ho dunque commentato le 2 free che avevo messo alla fine del MAIN ed il programma non crasha.
Il programma all'inizio, primo del menu, genera comunque 50.000 numeri
Quindi sono sicurissimo che esistano sia vettore, che vettore vettore_backup.
Infatti se scelgo subito "Esci" esce senza nessun errore anche se quelle 2 righe NON sono commentate.
Queste sono le uniche 2 funzioni degne d'interesse, cioè quella dove creo il vettore con numeri casuali, e quella dove faccio il backup del vettore.
Questa è l'opzione 12 all'interno dello switch
E poi volevo chiedere se mettere le "free" alla fine del MAIN è veramente necessario.
Cioè in ogni caso alla fine del programma non se le libera da solo?
Il mio problema è che ho scritto un programma con queste 16 opzioni:
printf ("Ordinamenti \n\n");
printf ("1:Naive sorte \n");
printf ("2:Bubble sort \n");
printf ("3:Insert sort \n");
printf ("4:Quick sort \n");
printf ("5:Selection sort \n");
printf ("6:Bubble sort V2 \n");
printf ("7:Insert sort V2 \n");
printf ("8:Shell sort \n");
printf ("9: Quick sort V1 \n");
printf ("10: Quick sort V2 \n");
printf ("11: Merge soft \n");
printf ("12: Compara algoritmi lenti \n");
printf ("13: Compara algoritmi veloci \n");
printf ("14: Compara tutti \n");
printf ("15: Crea un nuovo vettore \n");
printf ("16: Genera vettore con numeri casuali\n");
printf ("17: Esci \n\n\n");
Il programma funziona perfettamente a meno che non scelga 12-13-14.
In quel caso continua a funzionare, ma all'uscita dal programma, non esce correttamente, ma crasha.
Ho dunque commentato le 2 free che avevo messo alla fine del MAIN ed il programma non crasha.
// free(vettore);
// free(vettore_backup);
return 0;
}
Il programma all'inizio, primo del menu, genera comunque 50.000 numeri
n=50000;
vettore=random_vettore(n);
vettore_backup=malloc(n*sizeof(int));
copia_vettore(vettore_backup, vettore, n);
Quindi sono sicurissimo che esistano sia vettore, che vettore vettore_backup.
Infatti se scelgo subito "Esci" esce senza nessun errore anche se quelle 2 righe NON sono commentate.
Queste sono le uniche 2 funzioni degne d'interesse, cioè quella dove creo il vettore con numeri casuali, e quella dove faccio il backup del vettore.
int *random_vettore(int n)
{
int *vett=malloc(n*sizeof(int));
int i;
for (i=0; i<n; i++) vett[i]=rand();
return vett;
}
void copia_vettore (int *dest, int *src, int n)
{
int i;
if (src && dest) for (i=0; i<n; i++) dest[i]=src[i];
}
Questa è l'opzione 12 all'interno dello switch
case 12:
start=clock();
naiveSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("\n\nVettore di %d numeri ordinato da Naive Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
selectionSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato Selection Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
bubbleSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato Bubble Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
bubbleSort_V2(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Bubble Sort V2 in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
insertSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Insert Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
insertSort_V2(vettore,0,n-1);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Insert Sort V2 in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
printf ("Premi INVIO per continuare \n");
getchar();
break;
Process returned -1073741819 (0xC0000005) execution time : 16.181 s Press any key to continue.
Io ho fatto andare il programma sotto Debug mettendo l'interruzione alla fine di case 12:
Quindi poi ho scelto "Esci" e ho controllato che
vettore e vettore_backup
continuassero ad avere i loro valori, ed infatti fino alla fine (cioè fino a prima di usare free) hanno continuato ad avere i loro valori. Dopo di che esegue l'istruzione "return 0" ed invece di ritornare il valore 0 alla funzione main, continuando a premere F7 sul Debbuger leggo:
In ?? () () Cannot find bounds of current function Cannot find bounds of current function Cannot find bounds of current function
Ho letto su Internet che questo succede perchè non sono più all'interno della mia funzione (main) ma sono finito nello stack. Com'è potuto accadere? In generale come si fa ed evitare questa cosa, cioè quali sono i casi più comuni di "cattiva programmazione" che fanno incorrere in questo tipo di problemi? Perchè se commento le 2 istruzioni "free" alla fine del MAIN questo non succede? Quale può essere il nesso?
Puoi provare ad inserire i controlli sull'allocazione dinamica per vedere se va sempre a buon fine?
Un qualcosa tipo:
Inoltre, dovrebbe essere una buona pratica usare la free() non appena l'area di memoria allocata non serve più, per evitare di creare memory leak, ma attendi i più esperti
Un qualcosa tipo:
int *vett;
vett=malloc(10*sizeof(int));
if(vett==NULL)
{
printf("Errore, impossibile allocare il vettore..\n");
exit(1);
}
Inoltre, dovrebbe essere una buona pratica usare la free() non appena l'area di memoria allocata non serve più, per evitare di creare memory leak, ma attendi i più esperti
Fatto, ma non era quello il problema, infatti i numeri li ha sempre ordinati ed il crash avveniva solo dopo aver selezionato "Esci". Invece di uscire, crasha.
Comunque ho sempre usato la free ogni volta che fosse necessario e cioè prima di usare una nuova malloc per vettore, eseguo free(vettore)
All'interno del programma l'ho sempre usata, e solo alla fine il problema quindi mi chiedevo se è comunque un'operazione necessaria (all'uscita del programma) visto che quando un processo termina dovrebbe anche deallocare la memoria allocata in automatico...
Ma in questo caso il problema è che usando le free per qualche oscura ragione l'esecuzione del programma passa allo stack quando invece dovrebbe stare sul MAIN e quindi il "return 0" finale non corrisponde ad int main infatti alla fine leggo:
Comunque ho sempre usato la free ogni volta che fosse necessario e cioè prima di usare una nuova malloc per vettore, eseguo free(vettore)
case 15:
free(vettore);
free(vettore_backup);
n=inserisci_numero("Quanti elementi vuoi inserire nel vettore? ");
vettore=crea_vettore(n);
vettore_backup=malloc(n*sizeof(int));
copia_vettore(vettore_backup, vettore, n);
break;
case 16:
free(vettore);
free(vettore_backup);
n=inserisci_numero("Quanti elementi vuoi inserire nel vettore? ");
vettore=random_vettore(n);
vettore_backup=malloc(n*sizeof(int));
copia_vettore(vettore_backup, vettore, n);
break;
All'interno del programma l'ho sempre usata, e solo alla fine il problema quindi mi chiedevo se è comunque un'operazione necessaria (all'uscita del programma) visto che quando un processo termina dovrebbe anche deallocare la memoria allocata in automatico...
Ma in questo caso il problema è che usando le free per qualche oscura ragione l'esecuzione del programma passa allo stack quando invece dovrebbe stare sul MAIN e quindi il "return 0" finale non corrisponde ad int main infatti alla fine leggo:
Process returned -1073741819 (0xC0000005) execution time : 16.181 s Press any key to continue.
Scrivi troppa roba dentro lo switch, spostali dentro delle funzioni a parte: ne faciliti la lettura.
Immagino comunque che tu possa aver liberato la memoria prima di arrivare all'ultimo free. Prova a stampare a video il valore del primo elemento dell'array.
Immagino comunque che tu possa aver liberato la memoria prima di arrivare all'ultimo free. Prova a stampare a video il valore del primo elemento dell'array.
"vict85":
Scrivi troppa roba dentro lo switch, spostali dentro delle funzioni a parte: ne faciliti la lettura.
Immagino comunque che tu possa aver liberato la memoria prima di arrivare all'ultimo free. Prova a stampare a video il valore del primo elemento dell'array.
printf("vett: %d copia: %d", vettore[0], vettore_backup[0]);
free(vettore);
free(vettore_backup);
printf("vett: %d copia: %d", vettore[0], vettore_backup[0]);
return 0;
}
Output:
Che scegli? 17 vett: 13414 copia: 13414 Process returned -1073741819 (0xC0000005) execution time : 11.434 s Press any key to continue.
Comunque il codice completo sarebbe questo:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>
#define OPTIONS 17
typedef enum {false, true} boolean;
int inserisci_numero(char* domanda);
int *crea_vettore(int n);
int *random_vettore(int n);
void leggi_vettore(int *vettore, int n);
void copia_vettore (int *dest, int *src, int n);
void scambia(int *x, int *y);
int findPosMax(int *vettore, int n);
void naiveSort(int *vettore, int n);
void bubbleSort(int*vettore, int n);
void insertSort(int*vettore, int n);
void insertMinore(int*vettore, int lastpos);
void quickSort(int* vettore, int first, int last);
void selectionSort (int *v, int n);
void bubbleSort_V2(int *v, int n);
void insertSort_V2(int*v, const int primo, const int ultimo);
void shellSort(int *v, int n);
void quickSort_V1(int* x, int first, int last);
void quickSort_V2(int* vettore, int first, int last);
void mergeSort(int *a, const int left, const int right);
char ordinamenti[20][20]={"Naive Sort", "Bubble Sort", "Insert Sort", "Quick Sort", "Selection Sort", "Bubble Sort V2", "Insert Sort V2", "Shell Sort", "Quick Sort V1", "Quick Sort V2", "Merge Sort"};
int main()
{
int scelta=0;
int n=0;
int *vettore;
int *vettore_backup;
clock_t start, stop;
float duration;
srand(time(NULL));
n=50000;
vettore=random_vettore(n);
vettore_backup=malloc(n*sizeof(int));
copia_vettore(vettore_backup, vettore, n);
while (scelta!=OPTIONS)
{
printf ("Ordinamenti \n\n");
printf ("1:Naive sorte \n");
printf ("2:Bubble sort \n");
printf ("3:Insert sort \n");
printf ("4:Quick sort \n");
printf ("5:Selection sort \n");
printf ("6:Bubble sort V2 \n");
printf ("7:Insert sort V2 \n");
printf ("8:Shell sort \n");
printf ("9: Quick sort V1 \n");
printf ("10: Quick sort V2 \n");
printf ("11: Merge soft \n");
printf ("12: Compara algoritmi lenti \n");
printf ("13: Compara algoritmi veloci \n");
printf ("14: Compara tutti \n");
printf ("15: Crea un nuovo vettore \n");
printf ("16: Genera vettore con numeri casuali\n");
printf ("17: Esci \n\n\n");
do
{
scelta=inserisci_numero("Che scegli? ");
} while ((scelta<1) || (scelta>OPTIONS));
if (scelta!=OPTIONS)
{
switch (scelta)
{
case 1:
start=clock();
naiveSort(vettore,n);
stop=clock();
break;
case 2:
start=clock();
bubbleSort(vettore,n);
stop=clock();
break;
case 3:
start=clock();
insertSort(vettore,n);
stop=clock();
break;
case 4:
start=clock();
quickSort(vettore,0,n-1);
stop=clock();
break;
case 5:
start=clock();
selectionSort(vettore,n);
stop=clock();
break;
case 6:
start=clock();
bubbleSort_V2(vettore,n);
stop=clock();
break;
case 7:
start=clock();
insertSort_V2(vettore,0,n-1);
stop=clock();
break;
case 8:
start=clock();
shellSort(vettore,n);
stop=clock();
break;
case 9:
start=clock();
quickSort_V1(vettore,0,n-1);
stop=clock();
break;
case 10:
start=clock();
quickSort_V2(vettore,0,n-1);
stop=clock();
break;
case 11:
start=clock();
mergeSort(vettore, 0, n-1);
stop=clock();
break;
case 12:
start=clock();
naiveSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("\n\nVettore di %d numeri ordinato da Naive Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
selectionSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato Selection Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
bubbleSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato Bubble Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
bubbleSort_V2(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Bubble Sort V2 in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
insertSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Insert Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
insertSort_V2(vettore,0,n-1);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Insert Sort V2 in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
printf ("Premi INVIO per continuare \n");
getchar();
break;
case 13:
start=clock();
shellSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("\n\nVettore di %d numeri ordinato da Shell Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
mergeSort(vettore, 0, n-1);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Merge Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
quickSort(vettore,0,n-1);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Quick Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
quickSort_V1(vettore,0,n-1);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Quick Sort V1 in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
quickSort_V2(vettore,0,n-1);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Quick Sort V2 in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
printf ("Premi INVIO per continuare \n");
getchar();
break;
case 14:
start=clock();
naiveSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("\n\nVettore di %d numeri ordinato da Naive Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
selectionSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Selection Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
bubbleSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Bubble Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
bubbleSort_V2(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Bubble Sort V2 in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
insertSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Insert Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
insertSort_V2(vettore,0,n-1);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Insert Sort V2 in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
shellSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Shell Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
mergeSort(vettore, 0, n-1);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Merge Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
quickSort(vettore,0,n-1);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Quick Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
quickSort_V1(vettore,0,n-1);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Quick Sort V1 in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
start=clock();
quickSort_V2(vettore,0,n-1);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("Vettore di %d numeri ordinato da Quick Sort V2 in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
printf ("Premi INVIO per continuare \n");
getchar();
break;
case 15:
free(vettore);
free(vettore_backup);
n=inserisci_numero("Quanti elementi vuoi inserire nel vettore? ");
vettore=crea_vettore(n);
vettore_backup=malloc(n*sizeof(int));
copia_vettore(vettore_backup, vettore, n);
break;
case 16:
free(vettore);
free(vettore_backup);
n=inserisci_numero("Quanti elementi vuoi inserire nel vettore? ");
vettore=random_vettore(n);
vettore_backup=malloc(n*sizeof(int));
copia_vettore(vettore_backup, vettore, n);
break;
}
if (scelta>=1 && scelta <=OPTIONS-6)
{
printf ("\nVettore non ordinato: ");
leggi_vettore(vettore_backup,n<20? n:20);
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("\n\nVettore ordinato da %s in %f secondi: \n", ordinamenti[scelta-1], duration);
leggi_vettore(vettore,n<20? n:20);
copia_vettore(vettore, vettore_backup, n);
printf ("Premi INVIO per continuare \n");
getchar();
}
}
}
printf("vett: %d copia: %d", vettore[0], vettore_backup[0]);
free(vettore);
free(vettore_backup);
printf("vett: %d copia: %d", vettore[0], vettore_backup[0]);
return 0;
}
int inserisci_numero(char* domanda)
{
char *s0=(char*)malloc(10);
int n;
printf ("%s", domanda);
fgets (s0, 10, stdin);
s0[strlen(s0)-1]=0;
n=atoi(s0);
free(s0);
return n;
}
int *crea_vettore(n)
{
int *vett=(int*) malloc (n*sizeof(int));
int i;
for (i=0;i<n;i++)
{
printf ("%d elemento: ",i+1);
scanf("%d", &vett[i]);
}
return vett;
}
int *random_vettore(int n)
{
int i;
int *vett=malloc(n*sizeof(int));
if (!vett)
{
printf ("Impossibile allocare il vettore \n");
exit(1);
}
for (i=0; i<n; i++) vett[i]=rand();
return vett;
}
void copia_vettore (int *dest, int *src, int n)
{
int i;
if (src && dest) for (i=0; i<n; i++) dest[i]=src[i];
}
void leggi_vettore(int *vettore, int n)
{
int i;
for (i=0; i<n-1; i++)
{
printf("%d ->", vettore[i]);
}
printf("%d \n", vettore[n-1]);
}
void scambia(int *x, int *y)
{
int tmp;
tmp=*x;
*x=*y;
*y=tmp;
}
int findPosMax(int *vettore, int n)
{
int i, pos=0;
for (i=1; i<n; ++i)
{
if (vettore[i]>vettore[pos])
{
pos=i;
}
}
return pos;
}
void naiveSort(int *vettore,int n)
{
int p=findPosMax(vettore, n);
// printf ("pos max: %d \n", p);
if (n>0)
{
if (p!=n-1)
{
scambia(&vettore[p], &vettore[n-1]);
//printf("scambia %d con %d \n", vettore2[p], vettore2[n2-1]);
}
naiveSort(vettore, n-1);
}
}
void bubbleSort(int *vettore,int n)
{
int i;
boolean ordinato=false;
while ((n>1) &&(ordinato==false))
{
ordinato=true;
for (i=0; i<n-1; i++)
{
if (vettore[i]>vettore[i+1])
{
ordinato=false;
scambia(&vettore[i],&vettore[i+1]);
}
}
n--;
}
}
void insertSort(int *vettore,int n)
{
int i;
for (i=1; i<n; i++) insertMinore (vettore, i);
}
void insertMinore(int *vettore, int lastpos)
{
int x=vettore[lastpos];
int i;
for (i=lastpos-1; i>=0 && x<vettore[i]; --i)
{
vettore[i+1]=vettore[i];
vettore[i]=x;
}
}
void quickSort(int* vettore, int first, int last)
{
int i,j, pivot;
if (first<last)
{
i=first;
j=last;
pivot = vettore[(last+first)/2];
do
{
while(vettore[i]<pivot) i++; //ttrova il primo elemento maggiore del pivot partendo da sx verso dx
while (vettore[j]>pivot) j--; //trova il primo elemento minore del pivot partendo da dx verso sx
if (i<=j) //se i<j cioè se il maggiore si trova a sinistra del minore, effettua lo scambia
{
scambia(&vettore[i], &vettore[j]);
i++; // inizia la ricerca del prossimo elemento maggiore del pivot
j--; // inizia la ricerca del prossimo elemento minore del pivot
}
} while(i<=j); //cicla finchè non s'incontrano perchè dopo non avrà piu senso continuare
//visto che i a sinistra di j ci sono elementi sicuramente maggiori del pivot,
//e quindi i non andrebbe mai avanti dato che viene incrementata solo se vettore2[i]<pivot
quickSort(vettore, first, j);
quickSort(vettore, i, last);
}
}
void selectionSort (int *v, int n)
{
int i,j,minimo;
for (i=0; i<n-1; i++)
{
minimo=i;
for (j=i+1; j<n; j++)
{
if (v[j]<v[minimo]) minimo=j;
}
scambia(&v[i], &v[minimo]);
}
}
void bubbleSort_V2(int *v, int n)
{
int i, last, sup=n-1;
while (sup>0)
{
last=-1;
for (i=0; i<sup; ++i)
{
if (v[i]>v[i+1])
{
scambia(&v[i], &v[i+1]);
last=i;
}
}
sup=last;
}
}
void insertSort_V2(int*v, const int primo, const int ultimo)
{
int temp, i, j;
j=primo;
for (i=primo+1; i<=ultimo; i++)
{
if (v[i]<v[j]) j=i;
}
scambia (&v[i], &v[j]);
for (i=primo+2; i<=ultimo; i++)
{
j=i;
temp=v[i];
while (temp<v[j-1])
{
v[j]=v[j-1];
--j;
}
v[j]=temp;
}
}
void shellSort(int *v, int n)
{
int i,j,h, temp;
for (h=1; h<= (n-1)/9; h=3*h+1);
for (;h>0; h/=3)
{
for (i=h; i<n; ++i)
{
j=i;
temp=v[i];
while ((j>=h) && (temp<v[j-h]))
{
v[j]=v[j-h];
j-=h;
}
v[j]=temp;
}
}
}
void quickSort_V2(int* x, int first, int last)
{
if (first>=last) return;
int i,j,ipivot,pivot,center;
if (last-first<=50)
{
insertSort_V2(x, first, last);
return;
}
center=(first+last)/2;
if (x[first]>x[last] && x[first]<=x) ipivot=first;
else if (x[last]>x[first] && x[last]<=x) ipivot=last;
else ipivot=center;
if (ipivot!=first) scambia (&x[first], &x[ipivot]);
pivot=x[first];
i=first;
j=last;
while (i<j)
{
while (i<last && x[i]<=pivot) i++;
while (j>first && x[j]>pivot) j--;
if (i<j) scambia (&x[i], &x[j]);
}
scambia (&x[j],&x[first]);
quickSort_V2(x,first,j-1);
quickSort_V2(x,j+1,last);
}
void mergeSort(int *a, const int left, const int right)
{
if (left>=right) return;
int i, j, k, center;
center=(left+right)/2;
mergeSort(a,left,center);
mergeSort(a,center+1,right);
int *b=malloc((right-left+1)*sizeof(int));
i=left;
j=center+1;
k=0;
while(i<=center && j<=right)
{
if (a[i]<=a[j])
{
b[k]=a[i];
k++;
i++;
}
else
{
b[k]=a[j];
k++;
j++;
}
}
while (i<=center)
{
b[k]=a[i];
k++;
i++;
}
while (j<=right)
{
b[k]=a[j];
k++;
j++;
}
memcpy(a+left, b, (right-left+1)*sizeof(int));
free(b);
}
void quickSort_V1(int* x, int first, int last)
{
if (first>=last) return;
int i,j,pivot;
pivot=x[first];
i=first;
j=last;
while (i<j)
{
while (i<last && x[i]<=pivot) i++;
while (j>first && x[j]>pivot) j--;
if (i<j) scambia (&x[i], &x[j]);
}
scambia (&x[j],&x[first]);
quickSort_V1(x,first,j-1);
quickSort_V1(x,j+1,last);
}
"vict85":
Scrivi troppa roba dentro lo switch, spostali dentro delle funzioni a parte: ne faciliti la lettura.
Il problema è che non lo so fare. Come si passa una funzione ad un'altra funzione?
Visto che tutti i blocchi sono praticamente uguali, eccetto per il nome della funzione eseguita, supponiamo di voler trasformare in una funzione questo pezzo di codice:
start=clock();
shellSort(vettore,n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("\n\nVettore di %d numeri ordinato da Shell Sort in %f secondi \n", n, duration);
copia_vettore(vettore, vettore_backup, n);
Io nel MAIN ho scritto:
void algoritmo(int* vettore, int *vettore_backup, int n, int k, void ordinamento (int *vettore, int n));
E poi:
void algoritmo(int* vettore, int *vettore_backup, int n, int k, void ordinamento (int *vettore, int n));
{
clock_t start, stop;
float duration;
start=clock();
ordinamento(vettore, n);
stop=clock();
duration=(stop-start)/(float)CLOCKS_PER_SEC;
printf ("\n\nVettore di %d numeri ordinato da %s in %f secondi \n", n, ordinamenti[k], duration);
copia_vettore(vettore, vettore_backup, n);
}
Ma ovviamente è sbagliato e non ho la più pallida idea di come passare come parametro una funzione ad un'altra.
error: invalid use of void expression|
||=== Build finished: 1 errors, 0 warnings (0 minutes, 0 seconds) ===|
PS: ho modificato il titolo del topic visto che stiamo parlando di algoritmi di ordinamento in generale.
"Atem":
All'interno del programma l'ho sempre usata, e solo alla fine il problema quindi mi chiedevo se è comunque un'operazione necessaria (all'uscita del programma) visto che quando un processo termina dovrebbe anche deallocare la memoria allocata in automatico...
Quasi sicuramente non sono le chiamate a free() a causare il problema, ma si limitano a manifestarlo. Toglierle non risolve niente, il problema è sempre lì, potrebbe ripresentarsi alla prossima modifica.
Potresti aver chiamato due volte free() sullo stesso vettore, aver acceduto oltre gli indici di un vettore, aver chiamato printf() con un numero incoerente di argomenti, ed innumerevoli altre possibilità. E non è detto che il problema sia dove lo cerchi tu, magari è dentro una delle funzioni di ordinamento. E non è detto che il problema si manifesti sempre, né sempre nello stesso modo.
Alla fine del programma il sistema operativo rilascia automaticamente tutta la memoria allocata, quindi non è strettamente necessario chiamare esplicitamente free (a meno di implementazioni inconsuete, in genere senza sistema operativo e su hardware particolare). Il problema vero è che evitare di liberare la memoria esplicitamente diventa una cattiva abitudine. Pensa di dover spostare quel codice in una funzione a parte che verrà chiamata molte volte: ecco che hai ottenuto un memory leak bello grosso.
Comunque, provando a togliere codice dal main sono arrivato a questo, che continua a dare errore:
int main() {
int n = 0;
int *vettore;
int *vettore_backup;
srand(time(NULL));
n = 50000;
vettore = random_vettore(n);
vettore_backup = malloc(n * sizeof(int));
copia_vettore(vettore_backup, vettore, n);
quickSort_V2(vettore, 0, n-1);
printf("vett: %d copia: %d\n", vettore[0], vettore_backup[0]);
free(vettore);
free(vettore_backup);
return 0;
}
Quindi un errore potrebbe essere dentro la funzione quickSort_V2. Non mi da errore se invece chiamo quickSort_V2(vettore, 0, n), ma probabilmente è sbagliato lo stesso.
"Atem":
Il problema è che non lo so fare. Come si passa una funzione ad un'altra funzione?
Così:
void ordina(int *vettore, int *vettore_backup, int n, void (*algoritmo)(int*, int), const char * nomeAlgoritmo)
{
clock_t start = clock();
algoritmo(vettore,n);
clock_t stop = clock();
float duration = (stop-start) / (float)CLOCKS_PER_SEC;
printf ("\n\nVettore di %d numeri ordinato da %s in %f secondi \n", n, nomeAlgoritmo, duration);
copia_vettore(vettore, vettore_backup, n);
}
int main() {
int n = 0;
int *vettore;
int *vettore_backup;
srand(time(NULL));
n = 50000;
vettore = random_vettore(n);
vettore_backup = malloc(n * sizeof(int));
copia_vettore(vettore_backup, vettore, n);
ordina(vettore, vettore_backup, n, shellSort, "Shell Sort");
ordina(vettore, vettore_backup, n, selectionSort, "Selection Sort");
ordina(vettore, vettore_backup, n, insertSort, "Insert Sort");
free(vettore);
free(vettore_backup);
return 0;
}
Wow, grazie mille!
Certo che invece l'errore sulla quick_SortV2 è veramente strano perchè se ci vado col debug non entra nella funzione ma si perde chissà dove (nello stack?)...
"Atem":
Wow, grazie mille!
Certo che invece l'errore sulla quick_SortV2 è veramente strano perchè se ci vado col debug non entra nella funzione ma si perde chissà dove (nello stack?)...
Ops, scusate ho detto una schiocchezza.
Ero in modalità "Release" e non in modalità "Debug" ecco perchè andava direttamente alla fine...
Salve ragazzi, ho appena svolto un esercizio (in cui non si possono usare array nè matrici) che chiede di
a)memorizzare le prima 2000 parole del file in ordine alfabetico in un'opportuna struttura dati, stando attenti a non memorizzare doppioni ed in questo caso bisognerà contare le occorrenze della parola
b)utilizzare un algoritmo di complessità logaritmica per ordinare le parole in base alle ricorrenze
Io ho risolto a) usando una struttura "albero binario di ricerca" e
b)con il mergesort appoggiandomi ad un nuovo file.
Il procedimento che ho usato è il seguente:
1)ho memorizzato i dati del file in una struttura ad albero di ricerca binario
2)ho controllato con la visit_in_order che tutto fosse andato a buon fine (cioè che la memorizzazione delle parole sia avvenuta in ordine alfabetico)
3)ho aperto un nuovo file in scrittura "ricorrenze.dat" e vi ho memorizzato i seguenti campi:
parola
occorrenze
4)ho usato il mergesort su questo file per ordinare rispetto alle occorrenze
Il risultato finale è corretto ma vorrei sapere se esiste un modo per applicare il mergesort o il quicksort alla struttura ad albero senza appoggiarsi ad un file.
Perché creare un file? Basta memorizzare le coppie (parola, occorrenze) in un array ed ordinarlo.
Comunque un albero ha un ordine intrinseco, non puoi ordinarne gli elementi. Quello che potresti fare è inserire tutti gli elementi in un nuovo albero, in cui l'ordine dipende non dalla parola ma dalle occorrenze (la chiave non è "parola", ma "occorrenze").
"claudio86":
Perché creare un file? Basta memorizzare le coppie (parola, occorrenze) in un array ed ordinarlo.
Comunque un albero ha un ordine intrinseco, non puoi ordinarne gli elementi. Quello che potresti fare è inserire tutti gli elementi in un nuovo albero, in cui l'ordine dipende non dalla parola ma dalle occorrenze (la chiave non è "parola", ma "occorrenze").
L'esercizio dice esplicitamente di "non usare array o matrici".
All'esame non potremo usare "array nè matrici" quindi tutti gli esercizi su cui mi esercito vietano espressamente l'uso di array. Dato che una caratteristica dell'albero di ricerca binario è che la chiave deve essere univoca, se io scegliessi "ricorrenza" come chiave, poi dovrei usare un array per memorizzare tutte le parole che hanno quella ricorrenza, e non posso usare array.
Ma non devi usare un array, né usare due chiavi. È sufficiente visitare tutti i nodi del tuo albero secondo un qualche ordinamento e poi inserire questi valori in un nuovo albero in cui la chiave è il numero di ricorrenze..
"apatriarca":
Ma non devi usare un array, né usare due chiavi. È sufficiente visitare tutti i nodi del tuo albero secondo un qualche ordinamento e poi inserire questi valori in un nuovo albero in cui la chiave è il numero di ricorrenze..
Il mio albero è stato creato secondo l'ordine alfabetico perchè è quello che viene richiesto al punto a).
Ammettiamo che sia la parola "summer" sia la parola "spring" compaiano 10 volte.
La chiave in questo caso sarebbe il numero 10 ma ci sono due parole con la stessa riccorenza.
Quindi cosa posso fare? A me vengono in mente queste possibilita:
a)creare un nuovo albero con i campi: intero per le ricorrenze e array di puntatori a char per le parole (e non si può).
b)Oppure potrei evitare di usare l'array creando l'unica stringa che si ottiene dalla concatenazione di tutte le parole con la stessa ricorrenza.
E' vero che avrei ottenuto un albero ordinato secondo le ricorrenze ma avrei bypassato l'uso del mergesort/quicksort e non posso farlo perchè l'esercizio chiede espressamente di usare uno di questi 2 algoritmi.
Bhe, la chiave del nuovo albero sarebbe ricorrenza e nome insieme. Ordini prima in base alla ricorrenza e poi in base al nome..
Ciao! Sono il tuo Tutor AI, il compagno ideale per uno studio interattivo. Utilizzo il metodo maieutico per affinare il tuo ragionamento e la comprensione. Insieme possiamo:
- Risolvere un problema di matematica
- Riassumere un testo
- Tradurre una frase
- E molto altro ancora...
Il Tutor AI di Skuola.net usa un modello AI di Chat GPT.
Per termini, condizioni e privacy, visita la relativa pagina.
Per termini, condizioni e privacy, visita la relativa pagina.
Annuale
3,99€
-
Accedi a tutti gli appunti
-
Tutor AI: studia meglio e in meno tempo
-
Nessuna pubblicità sul sito
-
100€ di bonus su Ripetizioni.it
Trimestrale
7,99€
-
5 appunti ogni mese
-
Tutor AI: studia meglio e in meno tempo
-
Nessuna pubblicità sul sito
-
100€ di bonus su Ripetizioni.it
Mensile
12,79€
-
3 appunti ogni mese
-
Tutor AI: studia meglio e in meno tempo
-
Nessuna pubblicità sul sito
-
100€ di bonus su Ripetizioni.it