Thread: 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, "%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

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?

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

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

note that calloc is just waste of time - use malloc
and instead of loop - copying - use memmove

Looks like we have another three-star-programmer:

and don't forget your textbook. very handy for refreshers.