Thread: mergesort

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    88

    mergesort

    I need help with mergesort
    I used an algoritm form a book I have and have looked through the code but can't seem to understand what is wrong.
    Can anyone help? I feel that I am close
    any help is much appreciated

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define count 10000//count is maximum allowable array size
    
    void mergesort(int[], int, int);
    void merge(int[], int, int, int);
    
    int main()
    {
    	int x,amount, array[count];
    	
    	//user prompt
    	printf("Enter the number of integers you would like to sort\n(no larger than %d): ", count);
    	scanf("%d",&amount);
    	
    	//fills array with an amount of random integers decided by user, and prints the array
    	printf("\n\n Unsorted array: \n");
    	for (x = 1; x <= amount; x++)   
    	{
    		array[x] = rand() % count;
    		printf("%d\t",array[x]);
    	}
    	printf("here x= %d",x);//print test
    	mergesort(array, 0, amount);
    	printf("here");//print test
    
    	//prints the sorted array to screen
    	printf("\n\n Sorted array: \n");
    	for (x = 1; x <= amount; x++)
    	{
    		printf("%d\t",array[x]);	   
    	}
    	printf("\n\n");
    	return 0;
    }
    void mergesort(int array[], int l, int r)
    {
    	if (r <= 1)
    	{
    		return;
    	}
    	int m = (r+1)/2;
    	mergesort(array, l, m);
    	mergesort(array, m+1, r);
    	merge(array, l, m, r);
    }
    
    void merge(int a[], int l, int m, int r)
    {
    	int i, j;
    	static aux[count];
    	for(i = m+1; i > 1; i--)
    	{
    		aux[i-1] = a[i-1];
    	}
    	for(j= m; j < r; j++)
    	{
    		aux[r+m-j] = a[j+1];
    	}
    	for(int k = 1; k<= r; k++)
    	{
    		if(aux[j] < aux[i])
    		{
    			a[k] = aux[j--];
    		}
    		else
    		{
    			a[k] = aux[i++];
    		}
    	}
    }

  2. #2
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    Looks like you'd rather be in the C forum.

    A thing or two, though. You're using deprecated headers, and using a #define like that is bad practice.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Not if it's really C
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Looks like you'd rather be in the C forum.
    Try compiling it as C if you really think that.

    >I used an algoritm form a book
    Beware the code given in that book, it's of incredibly poor quality. In fact, that's the reason you are having problems. Sedgewick's use of l as a variable name got you confused and you used 1 instead. Compare this with your code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define count 10000//count is maximum allowable array size
    
    void mergesort(int[], int, int);
    void merge(int[], int, int, int);
    
    int main()
    {
      int x,amount, array[count];
    
      //user prompt
      printf("Enter the number of integers you would like to sort\n(no larger than %d): ", count);
      scanf("%d",&amount);
    
      //fills array with an amount of random integers decided by user, and prints the array
      printf("\n\n Unsorted array: \n");
      for (x = 1; x <= amount; x++)   
      {
        array[x] = rand() % count;
        printf("%d\t",array[x]);
      }
      printf("here x= %d",x);//print test
      mergesort(array, 0, amount);
      printf("here");//print test
    
      //prints the sorted array to screen
      printf("\n\n Sorted array: \n");
      for (x = 1; x <= amount; x++)
      {
        printf("%d\t",array[x]);	   
      }
      printf("\n\n");
      return 0;
    }
    void mergesort(int array[], int l, int r)
    {
      if (r <= l)
      {
        return;
      }
      int m = (r+l)/2;
      mergesort(array, l, m);
      mergesort(array, m+1, r);
      merge(array, l, m, r);
    }
    
    void merge(int a[], int l, int m, int r)
    {
      int i, j;
      static aux[count];
      for(i = m+1; i > l; i--)
      {
        aux[i-1] = a[i-1];
      }
      for(j= m; j < r; j++)
      {
        aux[r+m-j] = a[j+1];
      }
      for(int k = l; k<= r; k++)
      {
        if(aux[j] < aux[i])
        {
          a[k] = aux[j--];
        }
        else
        {
          a[k] = aux[i++];
        }
      }
    }
    My best code is written with the delete key.

  5. #5
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    I'm curious and willing to admit I was wrong. Why isn't that pure C?
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Why isn't that pure C?
    Assuming C89 as we usually do because C99 is still considered nonportable.
    Code:
    void mergesort(int array[], int l, int r)
    {
      if (r <= l)
      {
        return;
      }
      int m = (r+l)/2; // Declaration not at the beginning of a block
      mergesort(array, l, m);
      mergesort(array, m+1, r);
      merge(array, l, m, r);
    }
    Code:
    void merge(int a[], int l, int m, int r)
    {
      int i, j;
      static aux[count];
      for(i = m+1; i > l; i--)
      {
        aux[i-1] = a[i-1];
      }
      for(j= m; j < r; j++)
      {
        aux[r+m-j] = a[j+1];
      }
      for(int k = l; k<= r; k++) // Declaration in initialization of a for loop
      {
        if(aux[j] < aux[i])
        {
          a[k] = aux[j--];
        }
        else
        {
          a[k] = aux[i++];
        }
      }
    }
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Plus this:
    >int main()

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Plus this:
    >>int main()
    This is valid C, but the practice is usually discouraged.
    My best code is written with the delete key.

  9. #9
    Been here, done that.
    Join Date
    May 2003
    Posts
    1,164
    Originally posted by Prelude
    >Plus this:
    >>int main()
    This is valid C, but the practice is usually discouraged.
    Que? No comprendo.

    After all the arguments over
    Code:
    int|void main()
    I suddenly am not following this.

    Why would
    Code:
    int main()
    be discouraged in practice? Have I misinterpreted something here?
    Definition: Politics -- Latin, from
    poly meaning many and
    tics meaning blood sucking parasites
    -- Tom Smothers

  10. #10
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    I missed those declarations.

    int main(void) would be more like C.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  11. #11
    Registered User
    Join Date
    Feb 2002
    Posts
    465
    Originally posted by WaltP
    Why would
    Code:
    int main()
    be discouraged in practice? Have I misinterpreted something here?
    no, in C++ this is the preferred, no, make that standard declaration for main.

    in pure C however, its usually just:

    main()
    I came up with a cool phrase to put down here, but i forgot it...

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Have I misinterpreted something here?
    While there is nothing wrong with
    Code:
    int main()
    because it has no prototype and is a function definition (note that we are in a very subtle part of the C standard now), the majority of the C community prefers to use
    Code:
    int main ( void )
    This discourages the belief that an empty argument list means that the function takes no arguments when in the case of prototyped functions, an empty list means that the function takes an unknown number of arguments with unknown type (ie. The old style function declaration).

    C++ makes this even worse because it defines an empty parameter list as meaning no arguments. So C++ programmers get confused when they use C (though this is by no means the most confusing thing that C++ programers encounter).

    >in pure C however, its usually just:
    >main()
    Acceptable, but bad style in C89. Implicit int was removed in C99 though.
    My best code is written with the delete key.

  13. #13
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    So C++ programmers get confused when they use C (though this is by no means the most confusing thing that C++ programers encounter).
    That's why I almost always use:

    int main( void )

    for C++ and C, just to have one less thing to worry about. And also put a:

    return 0

    or equivalent at the end of main.

  14. #14
    Been here, done that.
    Join Date
    May 2003
    Posts
    1,164
    Originally posted by Prelude
    This discourages the belief that an empty argument list means that the function takes no arguments when in the case of prototyped functions, an empty list means that the function takes an unknown number of arguments with unknown type (ie. The old style function declaration).
    This is subtle. I guess I just don't get the difference between "no arguments" and "unknown arguments"... I understand there may be a theoretical difference (like in backgammon rolling 2 & 5 is not rolling 7) but is there a practical difference?
    Definition: Politics -- Latin, from
    poly meaning many and
    tics meaning blood sucking parasites
    -- Tom Smothers

  15. #15
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >I guess I just don't get the difference between "no arguments" and "unknown arguments"...
    Code:
    #include <stdio.h>
    
    int f();
    int g ( void );
    
    int main ( void )
    {
      f(); // Okay, prototype specifies unknown arguments
      g(); // Okay, prototype specifies no arguments
    
      f ( 10 ); // Okay, prototype specifies unknown arguments
      g ( 10 ); // Not okay, prototype specifies no arguments
    }
    
    int f()
    {
      return 0;
    }
    
    int g ( void )
    {
      return 1;
    }
    >but is there a practical difference?
    Yes. One of the primary reasons that C++'s prototype scheme was adapted to C89 is because the K&R style function declaration/definition scheme already in use was far too error prone. It was incredibly easy to pass the wrong number and/or type of arguments. The compiler had no way of detecting this and warning the programmer. However, for backward compatibility the old style function declarations and definitions were still allowed, paving the way for the same problems as the old style and more problems when both the old and new styles are mixed. And of course, who can forget the confusion raised by allowing two completely different styles?

    So the practical difference is static type checking. K&R style functions don't have it, ANSI/ISO style functions do.

    >This is subtle.
    It gets even more subtle. An empty parameter list in a function declarator is old-style K&R C and specifies that the function has an unknown number of parameters. But an empty parameter list in a function declarator that is also a definition specifies that the function has no parameters. So
    Code:
    int f();
    says that f has an unknown number of parameters, while
    Code:
    int f()
    {
    }
    says that f has no parameters, which is why
    Code:
    int main()
    {
      return 0;
    }
    is valid C. Yet another detail that helps to fuel the confusion.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Mergesort in C
    By Oduig in forum C Programming
    Replies: 2
    Last Post: 09-14-2008, 11:30 AM
  2. How do I do MergeSort versus QuickSort instead?
    By dxfist in forum C++ Programming
    Replies: 9
    Last Post: 03-06-2008, 12:12 PM
  3. Natural Mergesort
    By wuzzo87 in forum C Programming
    Replies: 31
    Last Post: 04-14-2007, 09:41 PM
  4. Mergesort
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 10-26-2005, 11:45 PM
  5. Linked Lists + MergeSort....(how?)
    By JoshR in forum C++ Programming
    Replies: 4
    Last Post: 06-03-2005, 02:40 PM