[C] Prestazioni algoritmi ordinamento

[turbobenza]

Salve sn alle prime armi con la programmazione. vorrei scrivere un codice che mi confronti due algoritmi di ordinamento a scelta (bubblesort e quicksort) e mi restituisca il tempo di esecuzione per entrambi per istanze di misura crescenti. Cercando su internet sono riuscito a mettere insieme un codice ma non riesco a farlo funzionare. Ve lo posto. Potete aiutarmi? grazie

#include <stdlib.h>
#include <stdio.h>
#include <time.h>


#define MAX 100


/*
* Legge in input il numero n ed n numeri interi
* che memorizza nell'array. Restituisce il numero
* di elementi letti (n).
*/

int leggi_array(int x[]) {
int i, n;

printf("Numero di elementi: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
scanf("%d", &x[i]);
}
return(n);
}


/*
* Stampa in output l'array.
*/

void stampa_array(int x[], int n) {
int i;

for (i=0; i<n; i++) {
printf("%d ", x[i]);
}
printf("\n");
return;
}



/*
* Scambia il contanuto delle due variabili
* indirizzate dai puntatori x e y.
*/

void scambia(int *x, int *y) {
int z;

z = *x;
*x = *y;
*y = z;
return;
}



/*
* Funzione che implementa l'algoritmo Bubble sort.
* Riceve come argomento l'array ed il numero di
* elementi contenuti nell'array. Non restituisce alcun
* valore, ma modifica il contenuto dell'array, ordinandolo.
*/

void bubble_sort(int x[], int n) {
int flag=1, k=n-1, i;

while (flag == 1 && k > 0) {
flag = 0;
for (i=0; i<k; i++) {
if (x[i]>x[i+1]) {
scambia(&x[i], &x[i+1]);
flag = 1;
}
}
k = k-1;
}
return;



/*
* Trova_pivot: individua l'elemento pivot in
* V[i]...V[j]; se esistono almeno due elementi
* diversi allora l'elemento scelto come pivot
* e' il piu' grande fra i due. Restituisce -1
* se tutti gli elementi sono uguali.
*/

int trova_pivot(int V[], int i, int j) {
int k;

for (k=i+1; k<=j; k++) {
if (V[k]>V[i])
return(V[k]);
else
if (V[k]<V[i])
return(V[i]);
}
return(-1);
}


/*
* Partiziona: funzione per la ridistribuzione
* degli elementi in base al valore del "pivot".
*/

int partiziona(int V[], int p, int r, int pivot) {
int i, j;

i = p;
j = r;
do {
while (V[j]>=pivot) {
j = j-1;
}
while (V[i]<pivot) {
i = i+1;
}
if (i<j)
scambia(&V[i], &V[j]);
} while (i<j);
return(j);
}


/*
* Quick_sort: funzione ricorsiva
*/

void quick_sort(int V[], int p, int r) {
int q, pivot;

pivot = trova_pivot(V, p, r);
if (p<r && pivot!=-1) {
q = partiziona(V, p, r, pivot);
quick_sort(V, p, q);
quick_sort(V, q+1, r);
}
return;
}


/*
* Funzione principale
*/

int main(void) {
int n, A[100];
float t0, t1;

n = leggi_array(A);

t0 = ((float)clock())/CLOCKS_PER_SEC;
quick_sort(A, 0, n-1);
t1 = ((float)clock())/CLOCKS_PER_SEC;

printf("Il tempo impiegato da quick_sork: %f secondi", t1-t0);


stampa_array(A, n);

return 0;
}

[turbobenza]

quando vado a compilare non me lo compila. credo ci sia un problema nel main della funzione principale che è quella che ho inserito alla fine del codice. ma non riesco a risolvere.

[turbobenza]

syntax error at end of input...ho controllato le graffe sembra essere a posto..booooo

[M@Rk0]

la richiesta specifica che sia il programma a restituire il tempo di esecuzione?
perchè io avrei fatto fatto due eseguibili (uno per ogni algoritmo) che prendono in input l'array da sortare e li avrei lanciati con http://it.wikipedia.org/wiki/Time_%28Unix%29

[turbobenza]

Originariamente inviato da M@Rk0

la richiesta specifica che sia il programma a restituire il tempo di esecuzione?
perchè io avrei fatto fatto due eseguibili (uno per ogni algoritmo) che prendono in input l'array da sortare e li avrei lanciati con http://it.wikipedia.org/wiki/Time_%28Unix%29

si si deve essere il programma che alla fine dell'inserimento dei valori random da ordinare e successivo ordinamento, mi restituisca il tempo impiegato per entrambi gli algoritmi.

[M@Rk0]

comunque, basta indentare bene il codice per vedere che alla fine della funzione bubble_sort manca la graffa dopo al return

inoltre nel main chiami solo il quick sort, l'altro non lo fai

[turbobenza]

purtroppo sono fresco di programmazione. non è che sappia come fare perchè avevo provato a chiamare il bubblesort ma ricevevo degli errori. non riesco a rendere il codice funzionante

[M@Rk0]

allora intanto bisogna aver voglia di leggere e capire quello che ti dicono gli altri:

Originariamente inviato da Antonio23

posta gli errori di compilazione no?

Originariamente inviato da turbobenza

syntax error at end of input...ho controllato le graffe sembra essere a posto..booooo

Originariamente inviato da Antonio23

vabbè, non ho capito se lo stai facendo apposta oppure no:

fai "copia e incolla" dell'output del compilatore.

e non l'hai fatto.
nello specifico l'output dovrebbe essere:

marco@vmwx:~/Scrivania$ gcc hwu.c -o hwu
hwu.c: In function ‘bubble_sort’:
hwu.c:166:1: error: expected declaration or statement at end of input
 }
 ^
marco@vmwx:~/Scrivania$

cosa vuol dire? molto probabilmente che manca una graffa o un ; da qualche parte. dove? in questo caso molto semplice bastava indentare bene il codice, a questo punto notavi che dopo un return definisci direttamente una funzione nuova, senza chiudere con la graffa quella prima

Originariamente inviato da M@Rk0

comunque, basta indentare bene il codice per vedere che alla fine della funzione bubble_sort manca la graffa dopo al return

inoltre nel main chiami solo il quick sort, l'altro non lo fai

Originariamente inviato da turbobenza

purtroppo sono fresco di programmazione. non è che sappia come fare perchè avevo provato a chiamare il bubblesort ma ricevevo degli errori. non riesco a rendere il codice funzionante

ti ho appena scritto come fare per farlo funzionare. devi aggiungere la graffa alla fine del bubble_sort. e devi aggiungere la chiamata all'altro algoritmo di sorting, nello stesso modo in cui l'hai fatto per il bubble.

più di così, non te lo possiamo scrivere noi il codice. se davvero sei in difficoltà, parti da problemi più semplici. per esempio, in questo codice passi puntatori alle funzioni. sai il perché? sai cosa sono e come funzionano? il fatto che tu dica "Cercando su internet sono riuscito a mettere insieme un codice" mi fa pensare a "non molto" come risposta

[turbobenza]

ho provato a modificare il main in questo modo:

int main(void) {
  int n, A[100];
  float t0, t1;
  
  n = leggi_array(A); 
  
  t0 = ((float)clock())/CLOCKS_PER_SEC;
  quick_sort(A, 0, n-1);
  t1 = ((float)clock())/CLOCKS_PER_SEC;
  
  printf("Il tempo impiegato da quick_sork: %f secondi", t1-t0);
  
  t0 = ((float)clock())/CLOCKS_PER_SEC;
  bubble_sort(v, n);
  t1 = ((float)clock())/CLOCKS_PER_SEC;
  
  printf("Il tempo impiegato da bubble_sork: %f secondi", t1-t0);
  
  stampa_array(A, n);
  
  return 0;
  }
}

mi restituisce questo errore: `v' undeclared (first use in this function)

[M@Rk0]

Originariamente inviato da turbobenza

ho provato a modificare il main in questo modo:

int main(void) {
  int n, A[100];
  float t0, t1;
  
  n = leggi_array(A); 
  
  t0 = ((float)clock())/CLOCKS_PER_SEC;
  quick_sort(A, 0, n-1);
  t1 = ((float)clock())/CLOCKS_PER_SEC;
  
  printf("Il tempo impiegato da quick_sork: %f secondi", t1-t0);
  
  t0 = ((float)clock())/CLOCKS_PER_SEC;
  bubble_sort(v, n);
  t1 = ((float)clock())/CLOCKS_PER_SEC;
  
  printf("Il tempo impiegato da bubble_sork: %f secondi", t1-t0);
  
  stampa_array(A, n);
  
  return 0;
  }
}

mi restituisce questo errore: `v' undeclared (first use in this function)

vabbè, io ora non voglio offendere nessuno e questo voglio che sia chiaro, chiedo solo: è il primo programma che provi a scrivere? così almeno ti si sa indirizzare in modo corretto.
chiusa questa parentesi, andiamo per piccoli passi: sai cosa significa l'errore che ti ha dato? o meglio, cosa pensi che voglia dire? hai idea di come usare la funzione quick_sort (tanto più che hai la bubble_sort come riferimento), e soprattutto di cosa faccia?
secondo me, ripeto, dovresti partire proprio dalle basi, non copiaincollare codice in giro sperando che funzioni (o questa è l'impressione che mi sono fatto da questo thread)

[Simonex84]

Originariamente inviato da turbobenza

ho provato a modificare il main in questo modo:

int main(void) {
  int n, A[100];
  float t0, t1;
  
  n = leggi_array(A); 
  
  t0 = ((float)clock())/CLOCKS_PER_SEC;
  quick_sort(A, 0, n-1);
  t1 = ((float)clock())/CLOCKS_PER_SEC;
  
  printf("Il tempo impiegato da quick_sork: %f secondi", t1-t0);
  
  t0 = ((float)clock())/CLOCKS_PER_SEC;
  bubble_sort(v, n);
  t1 = ((float)clock())/CLOCKS_PER_SEC;
  
  printf("Il tempo impiegato da bubble_sork: %f secondi", t1-t0);
  
  stampa_array(A, n);
  
  return 0;
  }
}

mi restituisce questo errore: `v' undeclared (first use in this function)

se il vettore l'hai chiamato A, perchè nel bubble_sort gli passi v?

Gli errori che restituisce il compilatore non sono messaggi scritti a caso, se li leggi ti dicono quello che non va "`v' undeclared" indica che non capisce cos'è "v"

[M@Rk0]

edit: fail mio

[Simonex84]

nell'esercizio però c'è un errore di fondo, su un vettore inserito a mano, quindi diciamo con una ventina di elementi, ti risulterà esattamente lo stesso tempo di ordinamento, andrebbe fatto almeno su 100.000 elementi per vedere qualche differenza

[turbobenza]

si esatto simone..è un altro problema che mi sono posto ma non so come risolvere..avevo pensato a generare migliaia di numeri random ma non so come fare

[Simonex84]

Originariamente inviato da turbobenza

si esatto simone..è un altro problema che mi sono posto ma non so come risolvere..avevo pensato a generare migliaia di numeri random ma non so come fare

un bel ciclo for e la funzione rand() fanno al caso tuo

http://www.html.it/pag/15491/il-ciclo-for/
http://www.cplusplus.com/reference/cstdlib/rand/

[Simonex84]

Originariamente inviato da Antonio23

la prima cosa che devi fare è prendere un libro e studiare le basi del C.

dopo X settimane puoi porti problemi avanzati.

spero che non siano esercizi richiesti a livello universitario per una facoltà di informatica o ingegneria, altrimenti prevedo giorni molto duri...

purtroppo ho visto pure di peggio al Politecnico, avevo parecchi compagni di corso che veninavo dal liceo classico e non avevano mai sentito nominare il C siamo partiti proprio dalle basi, non ti dico che noia per chi come me era perito informatico

in quel periodo ho notato che la cosa più difficie per i poco avvezzi all'informatica era l'indentazione, ho visto cose che voi umani....

[Simonex84]

Originariamente inviato da Antonio23

non è tanto questione di che scuola hai fatto (io ho fatto lo scientifico e il C l'avevo visto di striscio per fatti miei, mentre ho visto tanti venire dagli istituti tecnici e mantenere la loro mentalità da scuola superiore anche studiando materie prettamente tecniche che avevano già fatto), ma di come ti approcci allo studio di una nuova materia.

prendere pezzi di codice da internet e pregare che tutto funzioni non è un buon modo di cominciare.

verissimo, in questo caso turbobenza dovrebbe prendere carta e penna e partire con un bel diagramma di flusso, altro che google....

Poi magari una lettura ad un manuale di C non avrebbe guastato, ma se non hai in testa l'algoritmo non si va da nessuna parte