program hangs after inputting array

Question

#include<stdio.h>
#include<conio.h>
//#include<alloc.h>

int* mergeSort(int*,int);
int* merge(int*,int*,int);

void main()
{
  int n;int i=0;
  int *a,*b;

  scanf("%d",&n);
  a=(int)malloc(n*sizeof(int));
  for(;i<n;i++)
     scanf("%d",&a[i]);

  b=mergeSort(a,n);
  for(i=0;i<n;i++)
     printf("%d ",b[i]);

}

int* mergeSort(int *b,int n)
{
  int temp,*s;

  if(n>2)
  {
     mergeSort(b,n/2);
     mergeSort(b+n/2,n-n/2);
     s=merge(b,b+n/2,n);

     return s;
  }
  else if(n==2)
  {
     if(b[0]>b[1])
     {
         temp=b[0];
         b[0]=b[1];
         b[1]=temp; 
     }
     return;
  }
}

int* merge(int* a,int* c,int n)
{
  int i=0,j=0,k=0,
  int* x;

  while( (j ! =n/2) && (k != (n-n/2)) && (i < n))
  {
       if(a[j]<c[k])
       {
             x[i]=a[j];
             j++; 
             i++;
       }
       else
       {
             x[i]=c[k];
             k++;
             i++;
       }
   }
   for( ; j<n/2; j++,i++)
      x[i]=a[j];

   for( ; k < (n-n/2); k++,i++)
      x[i]=c[k];

   return x;
}

when i run this code,it hangs after inputting all the elements of the array in first for loop. Please help me, how can i correct it to make it work successfully? it hangs on calling the mergeSort function from main() function.

This is quite scary code. As a side comment, please [don't cast the return value of `malloc()` in C](http://stackoverflow.com/a/605858/28169). — unwind, Feb 06 '13 at 14:41
Furthermore, coding style, indentation and whitespace please! — , Feb 06 '13 at 14:42
Now that it's formatted, i'd say your recursion never ends so if you let it run long enough you should hit a stackoverflow. Other than that, saying "my code halts after inputing elements" isn't helping much, put some prinfs to localize WHERE it hangs, and then we can figure out why... @H2CO3: thanks. — Shark, Feb 06 '13 at 14:48
1) The `mergeSort()` function has code paths that don't return a value. 2) The `merge()` function uses an uninitialized pointer (`int *x`). There may be other problems but I stopped looking. — Blastfurnace, Feb 06 '13 at 14:48

Mike · Accepted Answer · 2013-02-06T14:56:59.707

3

it hangs after inputting all the elements of the array in first for loop.

hangs? Are you sure... that's pretty good considering your merge code declares a pointer to an int:

int *x;

and never initializes it, then tries to jump to an offset (i) past it:

x[i]=a[j];

Change your code to this:

int *x = malloc(n * sizeof(int));

and it should stop crashing/hanging whatever.

FYI, whenever you malloc() you should free() right now you have memory leaks.

edited Feb 06 '13 at 14:56

answered Feb 06 '13 at 14:50

Mike

47,263
29
113
177

thank you so much...now its working fine after initializing the int *x as you suggested and thank you @blastfurnace – yoda Feb 06 '13 at 15:06
@mike....can you please help in doing this merge sort with recursion...this code doesnot give the right answer...please help me! – yoda Feb 07 '13 at 07:13
@yodh - yeah, I noticed that too, it's close, but not quite right. Have you debugged it at all? Do you have any ideas why it's not working? – Mike Feb 07 '13 at 12:31
yeah i've debugged it...and its running fine but the thing is it is still not giving the right answer. – yoda Feb 08 '13 at 15:51
@yodh - debugging doesn't just mean making it compile ;) It means analyzing logic errors too. What I mean is you say it's not giving the right answer, so what analysis do you have to show that? What sets of input don't give the right answer, when you say it's "wrong" is it all out of order or only a particular subset of the whole? is it `merge()` or `mergesort()` that is giving the wrong data? (I'm guessing `merge()`) If it's `merge()` then is the data correct after the `while()` loop but wrong before the `for()`? – Mike Feb 08 '13 at 16:07
@yodh - See what I'm saying? You can step with a debuger or printf data as you go to analyze where the failure is occuring. That's "debugging" your program. Even if you can't seem to to get the correct output, you can figure out what inputs caues bad behavior, and what function/area the problem is in. – Mike Feb 08 '13 at 16:08
hehe...i dint know how to debug the logical errors...thanks for this and now i'll try to do it this way.... :) and hope i succeed this time! – yoda Feb 08 '13 at 16:17
@yodh no problem. Once you've done some analysis, if you still can't find it feel free to post another question asking specifically why your merge sort isn't sorting and provide your debug analysis, I or others would be happy to help follow up on your leg work. – Mike Feb 08 '13 at 16:31
thanks :) i want to ask one thing as you said above that i should free the allocated memory at the end...but doesnt the program itself releases that memory after it ends?! – yoda Feb 08 '13 at 16:36
1

@yodh - C programs *do not* do memory management by themselves. The Operating System you're on *may* do this for you, but that's not guaranteed... and if you ever work on embedded projects or on computers with no MMU (memory management unit) there's almost a guarantee that they **will not** do the clean up for you. So it's a good habit and good style to free your memory and close handles when you're done with them. – Mike Feb 08 '13 at 16:53
yes i did some analysis on this code...and i am posting the output that suggests its working all well except at a single step...just before merging all elements! i'll show you with the code and its output below as a comment :) – yoda Feb 08 '13 at 17:30

score 0 · Answer 2 · answered Feb 06 '13 at 14:58

0

There are some things wrong, not only basic things like void main instead of int main but also eg the return; in mergeSort() which should return int* and the uninitialized x. Also one important thing about the algorithm: You seem to assume that n is a power of 2: you recursively divide by 2 and assume that it always is an untruncated integer.

answered Feb 06 '13 at 14:58

Bernd Elkemann

23,242
4
37
66

It might be fine for main to return void, [read this](http://stackoverflow.com/questions/5296163/why-is-the-type-of-the-main-function-in-c-and-c-left-to-the-user-to-define/5296593#5296593). Although most likely, this case is a hosted program and then your comment about main is correct. – Lundin Feb 06 '13 at 15:09
but i've taken (n-n/2) the second time...so even if its truncated i'll get the rest of the elements second time...wont i? – yoda Feb 06 '13 at 16:07
Right. I overlooked that. But please consider the other points I wrote. – Bernd Elkemann Feb 06 '13 at 16:17

score 0 · Answer 3 · answered Feb 06 '13 at 15:01

0

For starters, the code doesn't compile in a C++ compiler (I know it's C code, but still...),

a couple of problems are:

line 11:

a=(int)malloc(n*sizeof(int));

why are you casting a pointer to an int? a is an int *

line 38:

return;

you are returning from mergeSort without a return value...that can't be good

I recommend that you fix all the compiler errors and warnings, then try again

answered Feb 06 '13 at 15:01

David Hope

2,216
16
32

actually i was not getting any compile time errors but run time error...and yes after removing int casting, and initializing *x my code is working fine, not giving correct result though. – yoda Feb 06 '13 at 16:05

program hangs after inputting array

3 Answers3