calcolo tempo di esecuzione di un algoritmo (c++)

[thedreamer84]

Sto calcolando il tempo di esecuzione di insertion sort..

typedef int *P;
class InsertionSort{
public:
InsertionSort(int n);//costruttore
~InsertionSort(); //distruttore
void ordinamento(int m1);
void inserisciElemento(int m);
private:
P p;

};

InsertionSort::InsertionSort(int n){
p=new int[n];
}

InsertionSort::~InsertionSort(){

delete[] p;

}

void InsertionSort::inserisciElemento(int m){
int i=0;
while(i<m){
cout<<endl;
cout<<"Inserisci l'elemento di posizione "<< i <<"\n";
cin>>p[i];
i++;
}

}

void InsertionSort:rdinamento(int m1){

clock_t start,end;
double tempo;
start=clock();
int key,i;
for(int j=1;j<m1;j++)
{
key=p[j];
i=j-1;

while(i>=0 && p[i]>key)
{
p[i+1]=p[i];
i--;
}
p[i+1]=key;
}
end=clock();
tempo=((double)(end-start))/CLOCKS_PER_SEC;
cout<<endl<<tempo<<endl;
cout<<"\nVettore ordinato : "<<endl;
for(int j=0;j<m1;j++)
cout<<p[j]<<endl;
cout<<endl;

}


quando vado ad eseguire mi dà sempre tempo 0..come mai??

[thedreamer84]

mi viene 0 perchè il tempo start viene uguale al tempo end!come mai visto che tra i due tempi ci sono altre istruzioni da eseguire??cioè end dovrebbe essere maggiore di start..

[YuYevon]

Non ho quasi mai usato la funzione clock() ma da quel poco che ne so, e da quello che ho verificato con questo codice

#include <iostream>
#include <ctime>
using namespace std;

int main()
{
	clock_t time_i, prev;

	prev = time_i = clock();

	for ( unsigned int i = 0; i < 1000000; i++ ) {
		if ( prev != time_i ) {
			cout << time_i << endl;
			prev = time_i;
		}
		time_i = clock();
	}

	return 0;
}

clock() restituisce il numero di cicli di clock completati in un certo intervallo di tempo, e non istante per istante... tant'è che con questo programmino ottengo incrementi di 10000 ad ogni stampa, non minori.

Evidentemente stai provando il tuo programma su un array troppo piccolo che viene ordinato in un tempo così breve da far restituire a clock() 0 sia all'inizio che alla fine della procedura. Ho provato ad eseguire il tuo codice con un array di 10000 elementi (ovviamente randomizzando la creazione dell'array perché sarebbe stato poco stimolante inserire a mano 10000 elementi... o-o") e ottengo un risultato diverso da 0.

[thedreamer84]

infatti..credo sia proprio questo il problema..devo ordinare almeno un vettore di dim pari a 1500..e ci mette pochissimo 0.016 secondi!!!