[C++] Calcolare il tempo di esecuzione Della CPU in algoritmo QuickSort

[3nigma666]

salve a tutti ho un problema.
In c++ ho implementato il codice dell'algoritmo di ordinamento divettori QuickSort,il quale risulta molto efficente essendo la sua complessita pari a n(logn) quando altri algoritmi hanno complessita'n^2 ecc.
L'algoritmo in se funziona perfettamente,il problema è ke nn riesko a calcolare ltempo di esecuzione con la funzione clock() inclusa nella libreria time.h,mi da come risultato 0 ms,il ke è impossibile aveno effettuato circa 500000 ripetizioni dell algoritmo con 1 vettore lungo 5000 elementi
vi allego il codice qua sotto,spero ke l identazione del forum nn faccia pasticci e sia comprensibile il tutto

CODICE:


//----------------------------------------------------------------------------------
// Università agli studi di Udine
// Anno Accademico : 2004/2005
// Studente : Valerio Bignardi
// Name : QuickSort
// Desc : Funzione ke prende in input un vettore di lunghezza definita da MAX,
// dove ogni elemento del vettore è generato casualmente dalla funzione Random
// il programma prende un elemento a caso nel vettore definito come pivot e divide
// ricorsivamente il vettore in 2 parti ,dove a sx ci sono tutti gli elementi inferiori
// di pivot e a dx tutti gli elementi maggiori di pivot.
// ci sono 2 puntatori uno all'inizio del vettore e uno alla fine ke scorrono verso il
// pivot tutto il vettore.
// Quando il programma trova un elemento inferiore a pivot nella parte dx o
// viceversa un elemento maggiore a sx,inverte i 2 vettori,posizionando cosi tutti gli
// elementi.
// QuickSort di divide essenzialmente in 2 funzioni:
// -Partition ke assegna un pivot e scandisce il vettore
// -Swap ke inverte due elementi da ordinare
// -QuickSort ke richiama ricorsivamente se stesso passando a se stesso prima l'albero sx
// e poi l'albero dx
// Vers : 0.99
// ToDo : Implementare il calcolo del tempo di esecuione tramite la funzione clock() e
// immettere un numero di ripetizione tali ke l'esecuzione del programma sia maggiore
// dell'orologio di sistema
// Bugs : Implementare il codice relativo al calcolo del tempo
//----------------------------------------------------------------------------------

#include <iostream>
#include <stdio.h>
#include <time.h>
#include <math.h>


//DICHIARAZIONE DELLE COSTANTI

#define A 16087
#define M 2147483647
#define Q 127773
#define R 2836

//DICHIARAZIONE DELLE VARIABILI E INIZIALIZZAZIONE

const int max = 500000; // Dichiaro la costante intera max inizializzata a 10000
int j = 0;
int q = 0;
int pivot = 0;
int i = 0;
long vettore [max];// Dichiaro un array di nome vettore, di dimensione max.
double seed; //Variabile globale ke contiene il seme della funzione random


//------------------------------------------
// Name : Random()
// Desc : funzione Random() che restituisce un numero casuale compreso tra 0 e 1
// ToDo : Nulla
//------------------------------------------

double Random()
{
double lo, hi, test;

hi = ceil(seed / Q);
lo = seed - Q * hi;
test = A * lo - R * hi;
if (test < 0.0) {
seed = test + M;
} else {
seed = test;
} /* endif */
return seed / M;
} //end random



//------------------------------------------------------------------------
// Name : swap(long& a, long& b)
// Desc : Questa funzione implementa lo scambio dei valori con
// la tecnica inplace, ovverosia senza alcuna variabile di supporto
// Si noti che i parametri sono passati per riferimento, altrimenti
// le modifiche sarebbero effettuate su copie di essi, e lo scambio di valore non ci sarebbe.
// ToDo : Nulla
// Vers : 1.0
//--------------------------------------------------------------------------

void swap (long& a, long& b) {
a = b + a; // (a+b) b
b = a - b; // (a+b) (a+b)-b
a = a - b; // (a+b)-a a
};

//-------------------------------------------------------
// Name : Partition
// Desc : Prende come parametri puntatore ad un vettore, indice sinistro ,indice destro
// Inizia a scorrerre il vettore partendo da fuori il vettore
// e inizia un loop ke continua fino a quando l'indice sx è minore dell'indice dx
// Dentro al loop viene fatto scorrere il vettore e ogni singolo elemento del vettore
// viene confrontato con il pivot e se maggiore viene messo a dx se inferiore viene
// posizionato a sx tramite la funzione swap
// ToDo : Nulla
// Vers : 0.9
// Bugs : N.P.
//--------------------------------------------------------

int Partition (long* vett,int left,int right){
pivot = vett[left];//a pivot assegno il primo elemento
i = left - 1 ; //inizio da fuori il vettore
j = right + 1; //inizio da fuori il vettore
//fino a quando l indice inferiore non supera l indice superiore continua a cercare gli elementi
while (i < j){
do{j--;} //decrementa di una posizione l'indice superiore
while (vett[j]>pivot); //continua a decrementare fino a quando l elemento trovato nn è maggiore del pivot
do{ i++;}
while (vett[i]<pivot);//continua a decrementare fino a quando l elemento trovato nn è minore del pivot
if (i<j)
swap(vett[i],vett[j]);//inverti i due valori
else
return j;// se i ha superato j ritorno il nuovo pivot a Qsort
}//end while
}//end partition




//-------------------------------------------------------------
// Name : QuickSort
// Desc : Assegna un valore a al pivot q.la funzione richiama se stessa
// ricorsivamente passandosi prima l'albero di dx e poi quello di sx
// ToDO : Nulla
// Vers : 1.0
// Bugs : N.P
//-----------------------------------------------------------



void QuickSort (long* vett,int left,int right){
if (left < right){
q = Partition (vett,left,right); //Assegnazione pivot
QuickSort(vett,left,q);//albero di sinistra
QuickSort(vett,q+1,right);//albero di destra
}//end if
}//end quicksort


// Programma principale

int main () {

seed = 123456789; //inizializzazione seme
//---------Creo il vettore----------
for (int i=0; i<=max;i++)
vettore[i] =(long)( Random()*500000);


// --- Richiamo la funzione QuickSort
// --- Implemento il calcolo temporale di esecuzione dell'algoritmo QuickSort
// Per eseguire tale operazione devo a priori calcolare la precisione dell'orologio
// di sistema,per fare cio' basta implementare questo codice:
/*int main()
{
float t0 = clock();
float t1 = clock();
while (t0 == t1)
t1 = clock();
float tot = (t1 - t0)/CLOCKS_PER_SEC;
return 0;
}*/
// il valore risultante è 15 ms. di conseguenza il tempo minimo misurabile con
// errore massimo del 5% è dato da:
// errore tollerato : 100 = precisione orologio : minimo tempo misurab. x
// quindi x = (100 * precisione orologio) / 5%
// ke nel nostro caso è: (100 * 15) / 5 quindi x = 300 ms

float t0 = clock();
for (int y=0;y==5000000;y++)
QuickSort(vettore,0,(max - 1));
float t1 = clock();
float tot = (t1-t0)/CLOCKS_PER_SEC;
/* //--Stampo il vettore ordinato per controllo
for (int i = 0; i < max; i++)
std::cout << vettore[i] << std::endl; //stampo a schermo*/
// Aspetto input da tastiera prima di chiudere la shell ( per evitare chiusura immediata sotto Win)
std::cout<<tot;
int n = 0;
std::cin>>n;
//exit with code 0
return 0;
}//end mainAllego il link del mio ftp dal quale poter scaricare il codice sorgente se dal forum risulta di difficile comprensione

ftp://hwupgrade:[email protected]

Grazie a tutti coloro ke mi daranno una mano

3NiGm@666

PS: Se si usa browser FTP entrare in attive mode ,disabilitare il passive mode perke sono dietro a router

[ilsensine]

for (int y=0;y==5000000;y++)

La condizione y==5000000 è sempre falsa, quindi il ciclo for non viene eseguito neanche una volta.

[3nigma666]

ma scusa nn dovrebbe essere un semplicissimo for ke va da 0 a 500.000 ripetizioni??

[ilsensine]

No è un semplicissimo for che non viene eseguito neanche una volta
Forse volevi scrivere
for (int y=0;y<5000000;y++)

[3nigma666]

ke idiota ke sono ... grazie mille ..nel frattempo per ovviare avevo fatto un do{
}while (n<500000)

grazie mille