turbobenza
27-02-2015, 11:05
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;
}
#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;
}