how much efficient is this sort?

This is a discussion on how much efficient is this sort? within the C Programming forums, part of the General Programming Boards category; Hello guys and gals, I made a simple Binary search tree and traversed it using intraversal so that the list ...

  1. #1
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804

    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
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,535
    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()
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Quote Originally Posted by Salem View Post
    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?
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,535
    Make your large array static.
    Then it won't be on the stack.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    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".
    Last edited by BEN10; 08-08-2009 at 07:12 AM.
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    The "stack" is a segment of memory that your compiler sets aside for handling function changes, (such as parameters you pass into and out of a function), amongst other things. It's generally 1 MB in size.

    Static arrays might not be included in your stack's segment of memory. If you search your help files for "memory model" or "stack size", or google "memory model Microsoft Visual Studio 2005", you should be able to find the details of your compiler's memory model. Most compilers have a way to control their stack size, to some extent, as well.

    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().

    Make sure you're free'ing anything you malloc(), before it goes out of scope and becomes "lost".

    Let us know how you fare, and good luck.

  7. #7
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    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().
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,535
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  2. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  3. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 04:21 PM
  4. radix sort and radix exchange sort.
    By whatman in forum C Programming
    Replies: 1
    Last Post: 07-31-2003, 12:24 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21