/* Stefano Salvi - 16/10/02
* tempi_ord.c
*
* Programma che in base ai tempi degli algoritmi di ordinamento (Bubble Sort, Quick Sort,
* Selection Sort e Insertion Sort) e al variare della dimensione del vettore da ordinare:
* 1: raccoglie i dati in una tabella elencandoli
* 2: cosruisce un grafico rappresentando i dati raccolti
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vga.h>
#include <vgagl.h>
#define compGT(a,b) (a>b)
#define NUM_TESTS 10 /* Numero di prove */
#define NUM_SORTS 6 /* Numero di algoritmi di sort */
// Indici degli algoritmi di sort
#define QUICKSORT 0
#define SHELLSORT 1
#define BUBBLESORT 2
#define SELECTIONSORT 3
#define INSERTIONSORT 4
#define SHAKESORT 5
#define MINL 1000 /* Minimo num. el. per sort lenti */
#define STEPL 1000 /* Incremento num. el. per sort lenti */
#define MAXL (MINL+NUM_TESTS*STEPL) /* Max numero elementi per sort lenti */
#define MINH 100000 /* Minimo num. el. per sort veloci */
#define STEPH 100000 /* Incremento num. el. per sort veloci */
#define MAXH (MINH+NUM_TESTS*STEPH) /* Max numero elementi per sort veloci */
// Costanti per disegnare il gafico
#define BORDER 20 /* Bordo superiore e destro */
#define BOTTOM_BORDER 30 /* Bordo inferiore (contiene valoro) */
#define LEFT_BORDER 38 /* Bordo sinsistro (contiene valori) */
#define NUM_VERT_SC 10 /* Numero tacche sull'asse verticale */
#define BASE_COLOR 4 /* Colore della prima linea del grafico */
int *vetalloc(int dim); /* alloca un vettore e lo riempie di numeri random */
int cmpint(const void *a,const void *b); /* Confornta due elementi di un vettore */
clock_t quick(int dim); /* ritorna il tempo del quick sort sul vettore*/
int shellseq(int h[],int n); /* */
clock_t shellsort(int dim); /* ritorna il tempo del shell sort sul vettore*/
void swap(int *a,int *b); /* scambia due elementi dell'array*/
clock_t bubble(int dim); /* ritorna il tempo del bubble sort sul vettore*/
clock_t selection(int dim); /* ritorna il tempo del selection sort sul vettore*/
clock_t insertion(int dim); /* ritorna il tempo dell' insertion sort sul vettore*/
clock_t shake(int dim); /* ritorna il tempo del shake sort sul vettore*/
void grafico (int dati [NUM_TESTS][NUM_SORTS]); /* Fa un grafico dei dati */
// Funzioni relative alla grafica
void initgraph (void); // Inizializza modo grafico e font
int maxDati (int dati [NUM_TESTS][NUM_SORTS]); // Calcola il massimo dato da tracciare
// Disegna un asse verticale con NUM_VERT_SC tacche e relativi valori
void asseVerticale (int left, int top, int bottom, int max);
// Disegna un asse orizzontale, con NUM_TESTS tacche e relativi valori
void asseOrizzontale (int left, int right, int bottom);
// Disenga le linee relative ai NUM_SORTS algoritmi ed ai NUM_TESTS campioni
void linee (int left, int right, int top, int bottom, int max, int dati [NUM_TESTS][NUM_SORTS]);
// Disegna una legenda realtiva ai NUM_SORTS algoritmi
void legenda (int left, int top);
int main()
{
int i,n;
int sortResults [NUM_TESTS][NUM_SORTS];
printf("Prima ecco i tempi degli ordinamenti piu' veloci:\n");
printf("\nN. EL\tQUICK\tSHELL\t");
printf("N. EL\tBUBBL\tSELEC\tINSER\tSHAKE\n");
for(i=0;i < NUM_TESTS; i++)
{
// Sort veloci - range da 100.000 a 1.000.000 di elementi
n = MINH+i*STEPH;
printf("%7d\t",n);
sortResults [i][QUICKSORT] = quick(n);
printf("%.3f\t",sortResults [i][QUICKSORT]/(float)CLOCKS_PER_SEC);
sortResults [i][SHELLSORT] = shellsort(n);
printf("%.3f\t",sortResults [i][SHELLSORT]/(float)CLOCKS_PER_SEC);
// Sort lenti - range da 1.000 a 10.000
n = MINL+i*STEPL;
printf("%5d\t",n);
sortResults [i][BUBBLESORT] = bubble(n);
printf("%.3f\t",sortResults [i][BUBBLESORT]/(float)CLOCKS_PER_SEC);
sortResults [i][SELECTIONSORT] = selection(n);
printf("%.3f\t",sortResults [i][SELECTIONSORT]/(float)CLOCKS_PER_SEC);
sortResults [i][INSERTIONSORT] = insertion(n);
printf("%.3f\t",sortResults [i][INSERTIONSORT]/(float)CLOCKS_PER_SEC);
sortResults [i][SHAKESORT] = shake(n);
printf("%.3f\n",sortResults [i][SHAKESORT]/(float)CLOCKS_PER_SEC);
}
printf ("Per viusalizzare il grafico, premete Enter\n");
getchar ();
grafico (sortResults);
return 0;
}
/* funzione che alloca il vettore e lo riempie di numeri random
* Alloca un vettore di interi di dimensione 'dim' e lo riempie di numeri casuali
*/
int *vetalloc(int dim)
{
int *vet,i;
vet = (int *) malloc(dim*sizeof(int));/*alloco lo spazio per il vettore*/
for (i=0;i<dim;i++)
{
vet[i]=rand(); /*riempio il vettore con interi random (da 0 a MAXINT)*/
}
return vet;
}
/* Confronta due elementi di un vettore.
* Ritorna:
* -1 se *a < *b
* 0 se *a == *b
* 1 se *a > *b
* Viene passata alla funzione di libreria 'qsort'
*/
int cmpint(const void *a,const void *b)
{
if (*((int *)a)==*((int *)b))
{
return 0;
} else if (*((int *)a) < *((int *)b))
{
return -1;
} else {
return 1;
}
}
/* Esegue il quick sort di un array di dimensione data (dim)
* Calcola il temmpo impiegato e lo restituisce.
* Utilizza la funzione di libreria 'qsort' per fare il lavoro
*/
clock_t quick(int dim)
{
int *vett; // Vettore da ordinare
clock_t t; // Tempo (prima iniziale, poi differenza)
vett = vetalloc(dim); // Alloca il vettore
t=clock(); // Misura il tempo iniziale
qsort(vett,dim,sizeof(int),cmpint); // Chiama la funzione per il sort
t=clock()-t; // Fa' la differenza tra tempo inizio e ora
free (vett); // Libera la memoria del vettore
return t; // Ritorna il tempo impiegato
}
/* Algoritmo che genera nell'array 'h' una sequenza di numeri primi
* all'incirca l'uno il doppio dell'altro, fino a superare un terzo del
* limite (n) dato.
* Ritorna il l'indice dell'ultimo elemento lasciato nell'array, quello che supera
* il terzo del limite
*/
int shellseq(int h[],int n)
{
int p1,p2,p3;
int s; // Indice nel vettore
p1=p2=1; // Inizializza i due numeri generatori (uno vale 2^s,
// l'altro 2^(s/2)
s=-1; // parte da -1 per dare 0 con il primo preincremento
do {
if(++s%2) // Se l'indice gia' incrementato e' dispari
{
h[s]=8*p1-6*p2+1;
} else { // Se l'indice e' pari
h[s]=9*p1-9*p2+1;
p2*=2; // Calcola il prossimo 2^(s/2)
}
p1*=2; // Calcola il prossimo 2^s
}while(3*h[s]<n);
return s>0?--s:0; // Ritorna l' indice dell'ultimo elemento utile (sempre positivo)
}
/* Esegue lo shell sort di un array di dimensione data (dim)
* Calcola il temmpo impiegato e lo restituisce.
* Utilizza un algoritmo modificato che, invece di utilizzare le dimensioni
* classiche dividendo di volta in volta per due la dimensione dell'array,
* utilizza una serie di numeri primi e, invece di eseguire lo scambio tra
* gli elementi, se non sono ordinati, fa 'scivolare' in alto gli elementi maggiori.
*/
clock_t shellsort(int dim)
{
int h,i,j;
int seq[100]; // Array con i valori dei salti
int *a; // Vettore da ordinare
int s; // Indice della dimensione del salto corrente
clock_t t; // Tempo (prima iniziale, poi trascorso)
a = vetalloc(dim); // Alloca il vettore
t = clock(); // Misura il tempo iniziale
s = shellseq(seq,dim); // Calcola le dimensioni dei salti, dal piu' grande
for (; s>=0; s--) // Per ogni elemento del vettore dei salti
{
h = seq[s]; // salto
for ( i = h; i < dim; i++) // Spazzola dal salto corrente alla fine
{
int t = a[i]; // Mette da parte l'elemento in fondo
// Scandisce gli elementi all'indietro, a salti di dimensione 'h'
for(j = i-h; j >= 0 && compGT(a[j],t); j -= h)
{
a[j+h]=a[j]; // Porta in alto l'elemento maggiore
}
a[j+h]=t; // Mette l'elemento in cima al suo posto
}
}
t=clock()-t; // Fa' la differenza tra tempo inizio e ora
free(a); // Libera la memoria del vettore
return t; // Ritorna il tempo impiegato
}
/* Scambia due elementi di un vettore
* 'a' e 'b' sono i puntatori ai due elementi.
* al ritorno i valori dei due elementi sono scambiati
*/
void swap(int *a,int *b) /*scambia i due elementi*/
{
int box; // Elemento di appoggio per lo scambio
box=*a; // Salvo il primo
*a=*b; // Ci copio il secondo
*b=box; // Copio il dato salvato nel primo
}
/* Esegue il bubble sort del vettore di dimensione data (dim).
* Calcola il temmpo impiegato e lo restituisce.
* Usa l'algoritmo modificato che termina se non ha fatto scambi in un ciclo
* esterno
*/
clock_t bubble(int dim)
{
clock_t tIni,tFin; // Tempi iniziale e finale
int *vett; // Vettore da ordinare
int sup; // Limite superiore del sort (sopra sono ordinati)
int i; // Elemento corrente del ciclo interno
int f; // Ultimo elemento scambiato (sopra, di fatto, sono ordinati)
vett = vetalloc(dim); // Alloca il vettore
tIni = clock(); // Rileva il tempo iniziale
sup = dim-1; // Inizia spazzolando l'intero vettore
do {
f=0; // Indice dell'ultimo scambio: inizialmente nessuno
for (i = 0; i < sup; i++) // Ciclo interno dal primo al limite corrente
{
if(vett[i]>vett[i+1]) // Se l'el. corrente e' inferiore al successivo (fuori ordine)
{
swap(&vett[i],&vett[i+1]); // Li scambia (fa' salire)
f=i; // ed annota la posizione
}
}
sup=f; // Per il prossimo giro, si fermera' al massimo scambiato
} while(f!=0); // Ripete finche' il massimo ordinato non e' il primo
tFin = clock(); // Rileva il tempo finale
free(vett); // Dealloca il vettore
return tFin - tIni; // Restiruisce il tempo trascorso
}
/* Esegue il selection sort del vettore di dimensione data (dim).
* Calcola il temmpo impiegato e lo restituisce.
*/
clock_t selection(int dim)
{
clock_t begin,end; // Tempi iniziale e finale
int i,j; // Indici dei cicli
int min; // Indice del Minimo
int *vet; // Vettore da ordinare
vet = vetalloc(dim); // Alloca il vettore
begin = clock(); // Rileva il tempo iniziale
for(i = 0; i < dim-1; i++) // Scandisce l'array
{
min=i; // Ipotizza che il minimo sia gia' in basso
// Ricerca del minimo
for (j = i+1; j < dim; j++) // Dalla posizione del ciclo esterno, fino alla fine
{
if(vet[j]<=vet[i]) // Se l'elemneto corrente e' minore del primo
{
min=j; // questo e' il nuovo minimo
}
}
if(min!=i) // Se il minimo non e' gia' a posto
{
swap(&vet[min],&vet[i]); // Sposta al suo posto il minimo
}
}
end = clock(); // Rileva il tempo finale
free(vet); // Dealloca il vettore
return end-begin; // Restiruisce il tempo trascorso
}
/* Esegue l'insertion sort del vettore di dimensione data (dim).
* Calcola il temmpo impiegato e lo restituisce.
*/
clock_t insertion(int dim)
{
clock_t tempo; // Tempo (prima iniziale, poi trascorso)
int i; // Indice ciclo
int t; // Indice della psoizione di inserimento
int tmp; // Valore dell' elemento in cima
int *vet; // Vettore da ordinare
vet = vetalloc(dim); // Alloca il vettore
tempo = clock(); // Rileva il tempo iniziale
for(i = 1; i < dim; i++) // Scandisce il vettore
{
tmp = vet[i]; // Prende l'elemento in cima
t = i; // Comincia ipotizzando che sia gia' al suo posto
// Ricerca la posizione corretta, sposta in alto gli altri
for (; tmp < vet[t-1] && t > 0; t--)
{
vet[t] = vet[t-1]; // Sposta in alto gli elementi maggiori
}
vet[t]=tmp; // Mette l'elemento corrente al suo posto
}
tempo = clock() - tempo; // Fa' la differenza tra tempo inizio e ora
free(vet); // Dealloca il vettore
return tempo; // Restiruisce il tempo trascorso
}
/* Esegue lo shake sort del vettore di dimensione data (dim).
* Calcola il temmpo impiegato e lo restituisce.
*/
clock_t shake(int dim)
{
int *vet; // Vettore da ordinare
int i; // Indice del ciclo
int min,max; // Minimo e massimo della sezione disordinata
clock_t t; // Tempo (prima iniziale, poi trascorso)
min=0; // Minimo inizialmente primo
max=dim-1; // Massimo inizialmante ultimo
vet = vetalloc(dim); // Alloca il vettore
t = clock(); // Rileva il tempo iniziale
while(min<max) // Finche' c'e' una sezione non ordinata
{
for(i = min;i < max; i++) // Spazzolata in su, trova il massimo
{
if(vet[i] > vet[i+1]) // Se il corrente e' minore del successivo
{
swap(&vet[i],&vet[i+1]);// Scambia
}
}
max--; // Adesso l'ultimo e' il massimo vero
for(i = max; i > min; i--) // Spazzolata in giu', trova il minimo
{
if(vet[i] < vet[i-1]) // Se il corrente e' minore del precedente
{
swap(&vet[i],&vet[i-1]);// Scambia
}
}
min++; // Adesso il primo e' il minimo vero
}
t = clock() - t; // Fa' la differenza tra tempo inizio e ora
free(vet); // Dealloca il vettore
return t; // Restiruisce il tempo trascorso
}
/* Inizializza la libreria svgalib e la vgagl.
* Seleziona il modo video 320x200 a 25 colori.
* Inizializza anche il font per le scritte.
*/
void initgraph ()
{
int mode = G320x200x256; // Modo video selezionato8
vga_init(); // Inizializza il sistema grafico
vga_setmode(mode); // Entra in modo grafico
gl_setcontextvga(mode); // Inizializza le gl con il modo grafico
gl_setfont (8,8,gl_font8x8); // Imposta il font di sistema
// Consente di usare il font di sistema senza espanderlo e sovrappore scritte al disegno
gl_setwritemode (FONT_COMPRESSED + WRITEMODE_OVERWRITE);
gl_setfontcolors(0, vga_white()); // Setta scritte bianche su fondo nero
}
/* Calcola il valore massimo degli elementi della matrice 'dati'
*/
int maxDati (int dati [NUM_TESTS][NUM_SORTS])
{
int i,j; // Indici
int max; // Massimo
for (max = i = 0;i < NUM_TESTS; i++)
{
for (j = 0; j < NUM_SORTS; j++)
{
if (dati [i][j] > max) // Se l'elemento corrente e' maggiore del massimo
{
max = dati [i][j]; // diventa il nuovo massimo
}
}
}
return max; // Ritorna il massimo
}
/* Disegna un asse verticale, con la freccia, NUM_VERT_SC tacche e relativi
* valori, tra 0 e 'max', convertiti in secondi tramite la costante CLOCKS_PER_SEC.
* L'asse e' posizionato a 'left', le graduazioni sono a sinistra, da 0.
* L'asse va da bottom (valore 0) a top (valore 'max').
* I valori vengono stampati in 'secondi'
*/
void asseVerticale (int left, int top, int bottom, int max)
{
int i;
// Asse verticale
gl_line (left, BORDER / 2, left, bottom, vga_white());
// Freccetta
gl_line (left, BORDER / 2, left+BORDER / 4, 3*BORDER/4, vga_white());
gl_line (left, BORDER / 2, left-BORDER / 4, 3*BORDER/4, vga_white());
// Scala
for (i = 0;i++ < NUM_VERT_SC;)
{
// Tacche
gl_line (left -2, bottom + (top-bottom)*i/NUM_VERT_SC,
left, bottom + (top-bottom)*i/NUM_VERT_SC, vga_white());
// Valori
gl_printf (0, bottom + (top-bottom)*i/NUM_VERT_SC-4,"%4.2f",
i*max/NUM_VERT_SC/(float)CLOCKS_PER_SEC);
}
}
/* Disegna un asse orizzontale, con NUM_TESTS tacche ed i valori, espressi
* in migliaia. Due righe di valori, una per i sort lenti (da 1K a 10K) ed
* una per i sort veloci (da 100 a 1000, intesi come K).
* La parte attiva dell'asse va' da 'left' a 'right', la freccia e' oltre a destra.
* Le graduazioni sono sotto l'asse, in due linee
* L'asse e' posizionato a 'bottom'
*/
void asseOrizzontale (int left, int right, int bottom)
{
int i;
// Asse orizzontale
gl_line (left, bottom, right + BORDER / 2, bottom, vga_white());
// Freccia
gl_line (right+BORDER/2, bottom, right + BORDER/4, bottom-BORDER/4, vga_white());
gl_line (right+BORDER/2, bottom, right + BORDER/4, bottom+BORDER/4, vga_white());
// Scala
for (i = 0;i < NUM_TESTS; i++)
{
// Tacche
gl_line (left + (right-left)*i/(NUM_TESTS-1), bottom,
left + (right-left)*i/(NUM_TESTS-1), bottom + 2, vga_white());
// Graduazione Sort Lenti (da 1K a 10K)
gl_printf (left+(right-left)*i/(NUM_TESTS-1)-8, bottom+2,"%dK", (MINL+i*STEPL)/1000);
// Graduazione Sort Veloci (da 100 a 1000)
gl_printf (left+(right-left)*i/(NUM_TESTS-1)-16, bottom+12,"%d", (MINH+i*STEPH)/1000);
}
}
/* Disegna le linee del grafico, per ognuno dei 6 algoritmi di sort.
* Disegna NUM_SORTS linee di NUM_TESTS punti, a partire dall'array 'dati'.
* Il grafico e' scalato per riempire il rettangolo 'left', 'right', 'top', 'bottom'.
* I valori di 'dati' vanno da 0 a 'max' (calcolato in precedenza e passato).
* Le linee saranno di colori diversi, a partire dal colore BASE_COLOR.
*/
void linee (int left, int right, int top, int bottom, int max, int dati [NUM_TESTS][NUM_SORTS])
{
int i,j; // Indici del punto e del test
int p1,p2; // Posizione orizzontale dei due punti
for (i = 0;i < NUM_TESTS - 1; i++) // Per copia di punti
{
p1 = left + (right-left)*i/(NUM_TESTS - 1); // Posizione punto corrente
p2 = left + (right-left)*(i+1)/(NUM_TESTS - 1) // Posizione punto successivo
for (j = 0; j < NUM_SORTS; j++) // Per ogni algoritmo
{
/* Traccia una linea dal punto corrente al successivo, con il colore
* calcolato in base al sort (indice colore da BASE_COLOR a BASE_COLOR+NUM_SORTS) */
gl_line (p1, bottom + (top-bottom)*dati [i][j]/max,
p2, bottom + (top-bottom)*dati [i+1][j]/max,
BASE_COLOR + j);
}
}
}
/* Stampa la legenda dei sort.
* La legenda parte da 'left' 'top' e contiene NUM_SORTS righe.
* Ogni riga contiene un segnemto di 10 pixel con il colore della linea
* relativa al sort, seguito dal nome del sort
*/
void legenda (int left, int top)
{
// Array con i nomi dei sort
char *sorts [] = {"Quicksort", "Shellsort", "Bubblesort", "Selection Sort",
"Insertion Sort", "Shake Sort"};
int i; // Indice del ciclo
for (i = 0; i < NUM_SORTS; i++) // Per ogni sort
{
// Disegna la lineetta, con il colore calcolato come in 'linee'
gl_line (left, top + 4 + 9*i, left + 10, top + 4 + 9*i, BASE_COLOR + i);
gl_write (left + 12,top + 9*i,sorts [i]); // Stampa il nome del sort (dall'array)
}
}
/* Disegna un grafico dei dati contenuti nella matrice 'dati'.
* Utilizza le costanti definite all'inizio, ed una serie di assunzioni, come
* i nomi dei sort.
*/
void grafico (int dati [NUM_TESTS][NUM_SORTS])
{
int leftLimit; // Lato sinistro dell'area del disegno
int rightLimit; // Lato destro dell'area del disegno
int topLimit; // Lato superiore dell'area del disegno
int bottomLimit; // Lato inferiore dell'area del disegno
int max; // Valore massimo nella matrice
initgraph (); // Inizializza la grafica
// Calcola l'area del grafico, in base allo schermo
leftLimit = LEFT_BORDER;
rightLimit = WIDTH - BORDER;
topLimit = BORDER;
bottomLimit = HEIGHT - BOTTOM_BORDER;
max = maxDati (dati); // Calcola il massimo dato da tracciare
// Disegna gli assi
asseVerticale (leftLimit, topLimit, bottomLimit, max);
asseOrizzontale (leftLimit, rightLimit, bottomLimit);
// Disegna il grafico
linee (leftLimit, rightLimit, topLimit, bottomLimit, max, dati);
legenda (leftLimit + 5, BORDER); // scrive la legenda
gl_write (0,HEIGHT - 10,"Premi ENTER per terminare"); // Messaggio di chiusura
getchar (); // Attende la pressione di un tasto
vga_setmode(TEXT); // Ripristina il modo testo
}
|
