Mergesort is of the devil

This is a discussion on Mergesort is of the devil within the C Programming forums, part of the General Programming Boards category; So I'm having trouble getting my mergesort functions to work. The first function mergesort works fine, but then when the ...

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    26

    Mergesort is of the devil

    So I'm having trouble getting my mergesort functions to work. The first function mergesort works fine, but then when the program calls merge it crashes. Heres mergesort:


    Mergesort function
    Code:
    void mergesort(struct comic **comics, int len)
    {
         struct comic *left;
         struct comic *right;
         int ct;
         
         printf("test1");
         if(len <= 1) 
         {
                return;
         }
         else{
         
         left = (struct comic*)calloc(len/2, sizeof(struct comic));
         
         for(ct = 0; ct < len/2; ct++)
         {
               left[ct] = *comics[ct];
         }
         mergesort(&left, len/2);
         
         right = (struct comic*)calloc(len - len/2, sizeof(struct comic));
    	 for(ct = len/2; ct<len; ct++)
    	 {
    		   (right)[ct - len/2] = (*comics)[ct];
    	 }
    	 mergesort(&right, len - len/2);
    	 printf("test1");
    	 merge(&comics, &left, len/2, &right, len-len/2);
    	 
    	 free(left);
    	 free(right);
         }//end else
    }//End mergesort
    So when it gets done with the first few operations and hits the call for merge the program jumps to the merge function:

    Merge function
    Code:
    void merge(struct comic ***comicsc, struct comic **leftc, int leftlen, struct comic **rightc, int rightlen)
    {
        int comicsnum = 0;
    	int leftnum = 0;
    	int rightnum = 0;
    	//int righttst, lefttst;
        printf("test1");
    	while(leftnum < leftlen && rightnum < rightlen)
    	{
    		if(leftc[leftnum]->issuenum <= rightc[rightnum]->issuenum)
    		{
    			**comicsc[comicsnum] = *leftc[leftnum];
    			comicsnum++;
    			leftnum++;
    		}
    		else
    		{
    			**comicsc[comicsnum] = *rightc[rightnum];
    			comicsnum++;
    			rightnum++;
    		}
    	}
    	
            printf("test");
            //RIGHT WHEN IT GETS TO THE FOLLOWING LOOPS MY PROGRAM CRASHES
           //I KNOW THIS BECAUSE IT STILL PRINTS THE PRINTF FUNCTION
          //DIRECTLY ABOVE THIS
            if(rightnum >= rightlen) 
    	{
                    
    		while(leftnum < leftlen)
    		{
    			**comicsc[comicsnum] = *leftc[leftnum];
    			comicsnum++;
    			leftnum++;
    		}
    	}
    	else
    	{
    		while(rightnum < rightlen)
    		{
                    printf("test1");      
    			**comicsc[comicsnum] = *rightc[rightnum];
    			comicsnum++;
    			rightnum++;
    		}
    	}
    	//printf("test1");
    }//End merge
    Does anyone see whats happening in those loops in the merge function that could be causing my program to crash?



    Here's how I'm declaring everything and then calling it, its the entire main function of my program.
    Code:
    main()
    {
          char filename[50], title[100], issue[100];
          char *p;
          char uscore = '_';
          char blank = ' ';
          int issuenum, numcomics, count = 0, cnt = 0, past = 0, pcnt = 0, tempcnt = 0;
          struct comic *thecomics;
          struct comic *temp;
          FILE *f1;
          
          printf("--------------------------------------------------------------------------------------");
          printf("Welcome to the comic book sorter!\n");
          printf("Please enter in the name of the file containing the comic books: ");
          //fflush();
          fgets(filename, sizeof(filename), stdin);
          
          //Removes the \n that ENTER adds into the filename input
          if((p = strchr(filename, '\n')) != NULL)
          {
                *p = '\0';
          }
          
           //Opens the file
           f1 = fopen(filename, "r");
           //fflush();
           
           if(f1 != NULL)
           {
                 fscanf(f1, "&#37;d", &numcomics);
                 system("pause");
                 
                 thecomics = (struct comic*)calloc(numcomics, sizeof(struct comic));
                 temp = (struct comic*)calloc(numcomics, sizeof(struct comic));
                 
                 do
                 {
                        fscanf(f1, "%s %d %s", title, &issuenum, issue);
                        cnt = 0;
                        //Checks for the _ in the string and replaces it with a "space"
                        do
                        {
                             if(title[cnt] == uscore)
                             {
                                     title[cnt] = blank;
                             }
                             cnt++;
                        }while(cnt < 100);
                                   
                        //Checks for the _ in the string and replaces it with a "space"
                        cnt = 0;
                        do
                        {
                             if(issue[cnt] == uscore)
                             {
                                     issue[cnt] = blank;
                             }
                             cnt++;
                        }while(cnt < 100);
                        
                        strcpy(thecomics[count].title, title);
                        strcpy(thecomics[count].issue, issue);
                        thecomics[count].issuenum = issuenum;
                        
                        count++;
                 }while(count < numcomics);
                 
                 //Sorts by title and then mergesorts by comic number and prints
                 count = 0;
                 do
                 {
                       //Tests to see if the title has already been run
                       pcnt = count - 1;
                        while(pcnt >= 0)
                        {
                            if(strcmp(thecomics[count].title, thecomics[pcnt].title) == 0)
                            {
                                  past = 1;
                            }
                            pcnt--;
                        }
                        
                        
                        if(past != 1)
                        {
                                tempcnt = 1;
                                cnt = count +1;
                                do
                                {
                                    if(strcmp(thecomics[count].title, thecomics[cnt].title) == 0)
                                    {
                                    
                                         temp[0] = thecomics[count];
                                         temp[tempcnt] = thecomics[cnt];
                                         tempcnt++;
                                    }
                                    cnt++;
                                }while(cnt < numcomics);
                               
                                mergesort(&temp, tempcnt);
                        
                                cnt = 0;
                                printf("%s\n", temp[0].title);
                                while(cnt <= tempcnt)
                                {
                                          printf("\t%d. %s\n", temp[cnt].issuenum, temp[cnt].issue);
                                          cnt++;
                                } 
                        }//End IF
                        
                        count++;
                 }while(count < numcomics);
                 system("pause");
                                                           
                 
           }//Close if
           else
           {
               printf("There is nothing in the file or it doesn't exist!\n");
           }//Close Else
           system("pause");
    }//Close main
    Last edited by Bizmark; 03-28-2008 at 03:12 PM.

  2. #2
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    struct comic ***comicsc

    what data this pointer to pointer to pointer is pointing?
    could you show the array declarations and how you call the merge function?
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  3. #3
    Registered User
    Join Date
    Nov 2007
    Posts
    26
    Ok I added it to my original post above.

  4. #4
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    why this passing pointer to pointer crap? you never change the pointer - only the contents of the array it points

    drop your & in mergesort(&temp, tempcnt); call - update the function prototype and body accordingly, do it for merge function as well

    you do not work with pointer to pointer correctly

    you want (*comics)[ct]; where you pass *comics[ct]; - so dropping pointer to pointer stuff will save you a headake
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  5. #5
    Registered User
    Join Date
    Nov 2007
    Posts
    26
    Quote Originally Posted by vart View Post
    why this passing pointer to pointer crap? you never change the pointer - only the contents of the array it points

    drop your & in mergesort(&temp, tempcnt); call - update the function prototype and body accordingly, do it for merge function as well

    you do not work with pointer to pointer correctly

    you want (*comics)[ct]; where you pass *comics[ct]; - so dropping pointer to pointer stuff will save you a headake
    What do you mean by dropping pointer to pointer stuff? Could you take the declaration of one of my functions and change it so that I can see an example of what the rest should look like?

  6. #6
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    Code:
    void mergesort(struct comic *comics, int len)
    {
    	printf("test1");
    	if(len <= 1) 
    	{
    		return;
    	}
    	else
    	{
    		struct comic *left;
    		struct comic *right;
    		int ct;
    		left = calloc(len/2, sizeof(*left));
    
    		for(ct = 0; ct < len/2; ct++)
    		{
    			left[ct] = comics[ct];
    		}
    		mergesort(left, len/2);
    
    		right = calloc(len - len/2, sizeof(*right));
    		for(ct = len/2; ct<len; ct++)
    		{
    			right[ct - len/2] = comics[ct];
    		}
    		mergesort(right, len - len/2);
    		printf("test1");
    		merge(comics, left, len/2, right, len-len/2);
    
    		free(left);
    		free(right);
    	}//end else
    }//End mergesort
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  7. #7
    Registered User
    Join Date
    Nov 2007
    Posts
    26
    Quote Originally Posted by vart View Post
    Code:
    void mergesort(struct comic *comics, int len)
    {
    	printf("test1");
    	if(len <= 1) 
    	{
    		return;
    	}
    	else
    	{
    		struct comic *left;
    		struct comic *right;
    		int ct;
    		left = calloc(len/2, sizeof(*left));
    
    		for(ct = 0; ct < len/2; ct++)
    		{
    			left[ct] = comics[ct];
    		}
    		mergesort(left, len/2);
    
    		right = calloc(len - len/2, sizeof(*right));
    		for(ct = len/2; ct<len; ct++)
    		{
    			right[ct - len/2] = comics[ct];
    		}
    		mergesort(right, len - len/2);
    		printf("test1");
    		merge(comics, left, len/2, right, len-len/2);
    
    		free(left);
    		free(right);
    	}//end else
    }//End mergesort
    Ok, its working well now. Now I just have a few more kinks and it should be done. Thank you for all your help.

  8. #8
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    note that calloc is just waste of time - use malloc
    and instead of loop - copying - use memmove
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Looks like we have another three-star-programmer:
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,701
    and don't forget your textbook. very handy for refreshers.
    Code:
    bool fun(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() > 0;
    }

  11. #11
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Maybe another performance option would be to save len/2 into a variable and use that variable instead of performing multiple identical division operations all over the place.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How do I do MergeSort versus QuickSort instead?
    By dxfist in forum C++ Programming
    Replies: 9
    Last Post: 03-06-2008, 11:12 AM
  2. Natural Mergesort
    By wuzzo87 in forum C Programming
    Replies: 31
    Last Post: 04-14-2007, 09:41 PM
  3. Mergesort
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 10-26-2005, 11:45 PM
  4. Check out DEVIL Screensaver System!
    By hartwork in forum Projects and Job Recruitment
    Replies: 2
    Last Post: 08-31-2005, 06:28 PM
  5. Linked Lists + MergeSort....(how?)
    By JoshR in forum C++ Programming
    Replies: 4
    Last Post: 06-03-2005, 02:40 PM

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