hello my friend,

I need your help.
I try to calculate quicksort and heapsort runtime. I write code in C++, but not calculate runtime. for example, both of them take a array[10000], I use <time h> and clock_t start, finish time, then finish-start return 0.

please help.
thanks...

Code samples always help.

my code

#include <iostream>
#include <time.h>
#include <stdlib.h>
int asize,heapsize;
void maxheapify(int *,int);
void buildmaxheap(int *);
void heapsort(int *);
int main(){
   char ch;
   int *a,i;
 do{
    double dif;
    cout<<"Enter array size: ";
    cin>>asize;
    a=new int[asize];
    srand(time(0));
    for(i=0;i<asize;i++){
  a[i]=1+(rand());
    }
    cout<<"please wait, array sorting..."<<endl;
      clock_t start,end;
     start = clock ();
      heapsort(a);
      end= clock ();
     dif = (end-start)/100;
     cout<<"Time: "<< dif<<"ms";
    cout<<endl<<"Do you want to exit(y/n): ";
    cin>>ch;
   }while (ch!='n');
    return 0;
}

void maxheapify(int *a,int i){
    int left,right,largest,temp;
    left=2*i+1;
    right=2*i+2;
    if(left<heapsize && a[i]<a[left])
     largest=left;
    else
     largest=i;
    if(right<heapsize && a[right]>a[largest])
     largest=right;
    if(largest!=i)
    {
        temp=a[i];
        a[i]=a[largest];
        a[largest]=temp;
        maxheapify(a,largest);
    }
}

void buildmaxheap(int *a){
    int i,j;
    heapsize=asize;
    i=heapsize/2-1;
    for(j=i;j>=0;j--)
    maxheapify(a,j);
}

void heapsort(int *a){
    int temp,i;
    buildmaxheap(a);
    for(i=asize-1;i>0;i--)
    {
        temp=a[i];
        a[i]=a[0];
        a[0]=temp;
        heapsize=heapsize-1;
        maxheapify(a,0);
    }
}

I'm (mostly) new to cpp (I've used it in bursts for a few months and then not bothered, it was so laborious), I tried that on my home linux machine but got this error when compiling on the commandline:

[:~/Desktop] shams% gcc voo.c
voo.c:1: header file 'iostream' not found
voo.c:15: illegal statement, missing `;' after `new'
voo.c:15: illegal declaration, missing name, found `;'
cpp-precomp: warning: errors during smart preprocessing, retrying in basic mode

now i've tried it on a server that was clearly much more full of things, and the initial error is gone but i'm getting this one...

# g++ -o voo voo.cpp
voo.cpp: In function ‘int main()’:
voo.cpp:13: error: ‘cout’ was not declared in this scope
voo.cpp:14: error: ‘cin’ was not declared in this scope
voo.cpp:20: error: ‘endl’ was not declared in this scope

how does one fix this?


I did however manage to get this far, and get one cpp application running...

#include <iostream>

int main()

{

std::cout << "blah blah blah\n";

}

Well you've got to start somewhere. If you can help me properly try and get your application working I'll look up what's wrong and fix it, unless someone else tells you before that. cheers. on second thoughts it looks like it would take weeks to figure out what this quicksort heapsort malarkey is, i'll just try sticking std:: in front of various couts and see if that makes a difference to my error messages...

okay. I got it working

./voo
Enter array size: 3
please wait, array sorting...
Time: 0ms
Do you want to exit(y/n): n

(however it did exit anyway)

So

I try to calculate quicksort and heapsort runtime. I write code in C++, but not calculate runtime. for example, both of them take a array[10000], I use <time h> and clock_t start, finish time, then finish-start return 0.

so you're trying to time it when it is sorting an array, just taking a measurement...

(is that right?)

by the way it exits when you say 'n' and carries on when you say 'y' (in answer to "do you want to exit (y/n) - that's backwards)

I have focused in on the timing issue and it is the clock () command/wotsit that is where the work needs to be done by the cpp dentist

I'm looking here to try and fix it...

http://apcsteacher.com/reference/cpp/tips_time.htm

I've done all this and it still doesn't work...

do{
double dif;
std::cout<<"Enter array size: ";
std::cin>>asize;
a=new int[asize];
srand(time(0));
for(i=0;i<asize;i++){
a[i]=1+(rand());
}
std::cout<<"please wait, array sorting..."<<std::endl;
clock_t start,end;
start = time(NULL);

heapsort(a);

end = time(NULL);

dif = difftime(end,start);

by the way it's not scalable, look:

Enter array size: 23
please wait, array sorting...
Time: 0ms
Do you want to exit(y/n): y
Enter array size: 10000
please wait, array sorting...
Time: 0ms
Do you want to exit(y/n): y
Enter array size: 1010202020
terminate called after throwing an instance of 'std::bad_alloc'
what(): St9bad_alloc
Aborted

Or maybe it's just something to do with the 'std'... who knows?

#include <iostream>

#include <time.h>
#include <stdlib.h>
int asize,heapsize;
void maxheapify(int *,int);
void buildmaxheap(int *);
void heapsort(int *);
int main(){
   char ch;
   int *a,i;
 do{
    double dif;
    std::cout<<"Enter array size: ";
    std::cin>>asize;
    a=new int[asize];
    srand(time(0));
    for(i=0;i<asize;i++){
  a[i]=1+(rand());
    }
    std::cout<<"please wait, array sorting..."<<std::endl;
      clock_t midgeure,start,end;
start = time(NULL); 
std::cout<< start << "\n";
      heapsort(a);

end = time(NULL);
std::cout<< end << "\n";
midgeure=end-start;

std::cout<< midgeure << "\n";

dif = difftime(end,start);

     std::cout<<"Time: "<< dif<<"ms";
    std::cout<<std::endl<<"Do you want to exit(y/n): ";
    std::cin>>ch;
   }while (ch!='y');
    return 0;
}

void maxheapify(int *a,int i){
    int left,right,largest,temp;
    left=2*i+1;
    right=2*i+2;
    if(left<heapsize && a[i]<a[left])
     largest=left;
    else
     largest=i;
    if(right<heapsize && a[right]>a[largest])
     largest=right;
    if(largest!=i)
    {
        temp=a[i];
        a[i]=a[largest];
        a[largest]=temp;
        maxheapify(a,largest);
    }
}

void buildmaxheap(int *a){
    int i,j;
    heapsize=asize;
    i=heapsize/2-1;
    for(j=i;j>=0;j--)
    maxheapify(a,j);
}

void heapsort(int *a){
    int temp,i;
    buildmaxheap(a);
    for(i=asize-1;i>0;i--)
    {
        temp=a[i];
        a[i]=a[0];
        a[0]=temp;
        heapsize=heapsize-1;
        maxheapify(a,0);
    }
}

produces this...

(which is easier to debug, you can start to see what is and isn't wrong)...

# g++ -o voo voo.cpp; chmod u+x voo; ./voo
Enter array size: 23
please wait, array sorting...
1230744108
1230744108
0
Time: 0ms
Do you want to exit(y/n): y

so, here's the still-not-working-but-easier-to-debug version:

#include <iostream>

#include <time.h>
#include <stdlib.h>
int asize,heapsize;
void maxheapify(int *,int);
void buildmaxheap(int *);
void heapsort(int *);
int main(){
   char ch;
   int *a,i;
 do{
    double dif;
    std::cout<<"Enter array size: ";
    std::cin>>asize;
    a=new int[asize];
    srand(time(0));
    for(i=0;i<asize;i++){
  a[i]=1+(rand());
    }
    std::cout<<"please wait, array sorting..."<<std::endl;
      clock_t midgeure,start,end;
start = time(NULL); 
std::cout<< start << "\n";
      heapsort(a);

for(i=0;i<10000;i++){
std::cout<<"cows is animals, bananas is fruit" << i << "\n";
}

end = time(NULL);
std::cout<< end << "\n";
midgeure=end-start;

std::cout<< midgeure << "\n";

dif = difftime(end,start);

     std::cout<<"Time: "<< dif<<"ms";
    std::cout<<std::endl<<"Do you want to exit(y/n): ";
    std::cin>>ch;
   }while (ch!='y');
    return 0;
}

void maxheapify(int *a,int i){
    int left,right,largest,temp;
    left=2*i+1;
    right=2*i+2;
    if(left<heapsize && a[i]<a[left])
     largest=left;
    else
     largest=i;
    if(right<heapsize && a[right]>a[largest])
     largest=right;
    if(largest!=i)
    {
        temp=a[i];
        a[i]=a[largest];
        a[largest]=temp;
        maxheapify(a,largest);
    }
}

void buildmaxheap(int *a){
    int i,j;
    heapsize=asize;
    i=heapsize/2-1;
    for(j=i;j>=0;j--)
    maxheapify(a,j);
}

void heapsort(int *a){
    int temp,i;
    buildmaxheap(a);
    for(i=asize-1;i>0;i--)
    {
        temp=a[i];
        a[i]=a[0];
        a[0]=temp;
        heapsize=heapsize-1;
        maxheapify(a,0);
    }
}

if you run it like that, you'll start to see that a certain degree of counting is going on, something is being timed, but there are two problems - where it says 6ms, it seems to take about 20 seconds.

plus where you were dividing by 100... that's magnifying that strange skewing of the numbers even more... where the ratio is 20 seconds to 0.006 seconds, your factor of 100 turns it to (2000 seconds to 0.006 seconds, i.e. 2000 : 0.006 , 20000 : 0.06 , 200,000:0.6 , 2,000,000 : 6, 1,000,000:3,) 300,000:1 approximately.

my output was

cows is animals, bananas is fruit9995
cows is animals, bananas is fruit9996
cows is animals, bananas is fruit9997
cows is animals, bananas is fruit9998
cows is animals, bananas is fruit9999
1230745082
6
Time: 6ms
Do you want to exit(y/n): y

thanks for your excellent help.
I use windows, borland 5.02 for c++.
std::count give error. for this reason I use cout<< or cin>>.

I try to solve this problem. in quicksort I maybe solve it.
I make to take function which calculate (quickSort(a,l,r) in a for loop. for loop inital 1 to 1000. then 2nd step get time same method (start-end). I divide result /1000. I have result. but I dont know that it is true.

but this method not work in heapsort.

regarding std::cout, if you import using namespace std you won't have to worry about scoping.

#include <iostream>

#include <time.h>
#include <stdlib.h>
using namespace std;

Cool. I'll try it next time.