Thread: how much efficient is this sort?

Hello guys and gals,
I made a simple Binary search tree and traversed it using intraversal so that the list gets sorted. Here is what I did.

Code:

#include<stdio.h>
#include<time.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 25
struct node
{
	int info;
	struct node *left;
	struct node *right;
};
typedef struct node *vish;
vish tree,p,q;
vish maketree(int x)
{
	p=malloc(sizeof(struct node));
	p->info=x;
	p->left=NULL;
	p->right=NULL;
	return p;
}
void setleft(vish p,int x)
{
	if(p==NULL)
		printf("void insertion\n");
	else if(p->left!=NULL)
		printf("invalid insertion\n");
	else
		p->left=maketree(x);
}
void setright(vish p,int x)
{
	if(p==NULL)
		printf("void insertion\n");
	else if(p->right!=NULL)
		printf("invalid insertion\n");
	else
		p->right=maketree(x);
}
void intrav(vish tree)
{
	if(tree!=NULL)
	{
		intrav(tree->left);
		printf("\n%d\n",tree->info);
		intrav(tree->right);
	}
}
int main(void)
{
	int elt,i,x[MAX],y;
	time_t first,second;
	printf("Enter the number of elements in the tree\n");
	scanf("%d",&elt);
	printf("Enter elements one by one");
	for(i=0;i<=elt-1;i++)
		scanf("%d",&x[i]);
	printf("The elements you entered are\n");
	for(i=0;i<=elt-1;i++)
		printf("%d\t",x[i]);
	tree=maketree(x[0]);
	for(i=1;i<elt;i++)
	{
		y=x[i];
		q=tree;
		p=q;
		while(p!=NULL)
		{
			q=p;
			if(y< p->info)
				p=p->left;
			else
				p=p->right;
		}
		if(y<q->info)
			setleft(q,y);
		else
			setright(q,y);
	}
	first=time(NULL);
	intrav(tree);
	second=time(NULL);
	printf("\n\nTime taken to sort %f",difftime(second,first));
	getch();
}

Now actually I want to look at the efficiency of the method, for that I used difftime function. But whatever number of elements I enter, the result is same 0.000000seconds. I was thinking of making the output something like MK27 has shown(elapsed time) in here(post no.14). How can I do that such that the time taken to sort the list is also displayed correctly in the output. I hope I made myself clear.
Thanks

Unless you can get your code to run for at least several seconds, you're going to get zero.

It's like timing a bullet with a stopwatch - the show is over before you've realised something is happening.

Rather than reading data in manually, use a loop to generate an array filled with 1M random numbers, then try and sort that.
Compare with the result of using say qsort()

Originally Posted by Salem

Unless you can get your code to run for at least several seconds, you're going to get zero.

It's like timing a bullet with a stopwatch - the show is over before you've realised something is happening.

Rather than reading data in manually, use a loop to generate an array filled with 1M random numbers, then try and sort that.
Compare with the result of using say qsort()

Ok, now I modified my code but it's still showing 0 sec.

Code:

#include<stdio.h>
#include<time.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
#define MAX 100000
struct node
{
	int info;
	struct node *left;
	struct node *right;
};
typedef struct node *vish;
vish tree,p,q;
vish maketree(int x)
{
	p=malloc(sizeof(struct node));
	p->info=x;
	p->left=NULL;
	p->right=NULL;
	return p;
}
void setleft(vish p,int x)
{
	if(p==NULL)
		printf("void insertion\n");
	else if(p->left!=NULL)
		printf("invalid insertion\n");
	else
		p->left=maketree(x);
}
void setright(vish p,int x)
{
	if(p==NULL)
		printf("void insertion\n");
	else if(p->right!=NULL)
		printf("invalid insertion\n");
	else
		p->right=maketree(x);
}
void intrav(vish tree)
{
	if(tree!=NULL)
	{
		intrav(tree->left);
		//printf("\n%d\n",tree->info);
		intrav(tree->right);
	}
}
int main(void)
{
	int i,x[MAX],y;
	time_t first,second;
	for(i=0;i<MAX;i++)
		x[i]=rand()%100;
	tree=maketree(x[0]);
	for(i=1;i<MAX;i++)
	{
		y=x[i];
		q=tree;
		p=q;
		while(p!=NULL)
		{
			q=p;
			if(y< p->info)
				p=p->left;
			else
				p=p->right;
		}
		if(y<q->info)
			setleft(q,y);
		else
			setright(q,y);
	}
	first=time(NULL);
	intrav(tree);
	second=time(NULL);
	printf("\n\nTime taken to sort %f",difftime(second,first));
	getch();
}

If I change MAX to 1000000, it shows stack overflow error. What should I do now?

Make your large array static.
Then it won't be on the stack.

I changed my array declaration to static and increased MAX to 1000000, then after waiting for around 5min, the code gave stack overflow error at the first brace of intrav function. Isn't there any other way by which I can also check efficiency for smaller number of elements in the array? Also can you please explain when you say "Then it won't be on the stack".

Ok. Now diverting from my original topic. Tell me if I'm correct here.
There is a thing called RAM. Stack is a part of RAM. All the variables and function calls and return address are stored in stack. Heap is where malloc'd variables are stored. Is heap also a part of RAM? Are static variables stored in heap(That's why in my problem stack overflow didn't occur)? Where are global variables stored(heap or stack)?
@Adak
I googled "memory model Microsoft Visual Studio 2005", but to no avail. Can you please explain, by an example, what do you mean here:

Your largest arrays can not normally be included in the stack's memory - unless you have very limited memory. If you try these different ways, you should be able to find which one will give you the largest array size:

1) A global array before any function.
2) A normal array in main()
3) A static array in main()
4) A malloc'd array in main().

Code:

int global[SIZE1];  // data
int main ( ) {
  int local[SIZE2];  // stack
  static int slocal[SIZE3]; // data
  int *p = malloc ( sizeof(*p) * SIZE4 );  // heap
}

Yes, it's all RAM.

For your average desktop machine, you have a 2GB address space into which
- code
- data
- stack
- heap
are all placed.

Code and data are allocated and initialised as the OS loads your program.
The stack allocation begins with just 1 page. Additional pages are mapped on demand until the limit is reached. The default may be 1MB, but most programs seldom use anywhere near the total.
Finally, the heap is initialised for any future new/malloc calls the program may make.