0

When i try to run my code using using recursion i get stuck in an infinite loop.

this is my first time implementing divide and conquer using recursion so i am a bit rusty on the concepts. Please have a look at the code an let me know where i can correct it.

/**
 * MergeSort.c
 *
 * Ujjwal Arora
 * 
 *
 * Implements merge sort for an array
 */

#include<stdio.h>
#include<conio.h>
void merge(int array[6],int beg,int mid,int end);
void mergesort(int array[6],int beg,int end);
void display(int array[6]);

int main(void)
{
     // Initializes the array
     int array[6]={3,1,2,9,5,4};
     // Initialize the beginning and the end 
     int beg=0, end=5;
     // Implement the Merge Sort 
     mergesort(array,beg,end);
     getch();
}
void mergesort(int array[6],int beg,int end) //Calls Initial merge sort
{
      int mid;

      if(beg<end)
      {
            mid=(beg+end)/2;
            mergesort(array,beg,mid);        //Left part of the array
            mergesort(array,mid+1,end);      //Right part of the array
            merge(array,beg,mid,end);        //merge two sorted arrays
      }
 }
void merge(int array[6],int beg,int mid,int end)
{
     int temp[6]; //Declare a temp array for storing the sorted data
     //Initialize the temp array
     int k=beg;
     //initialize the pointers for two sub arrays     
     int i=beg;
     int j=mid;

     while(i<=mid && j<=end)
       {
            if(array[i] < array[j])
              {
                 temp[k]=array[i];
                 i++;                     
              }
            else
              {
                 temp[k]=array[j];
                 j++;                     
              }
                 k++;              
        }            
    //Clearing any remaining elements in the sub array
     if(i>mid) 
      {
           for(int m=j;j<=end;m++)
           {
                  temp[k]= array[m];
                  k++;                      
           }               
      }        
    else 
      {
           for(int m=i;m<=mid;m++)
           {
                  temp[k]= array[m];
                  k++;
           }
      }
    //Reassign the sorted elements to the original array
    for(k=beg;k<end;k++)     
      {
          array[k]=temp[k];                                      
      }  
 display(array);           //display array
}
void display(int array[6])
{
     for(int i=0;i<6;i++)
     {
             printf("%d ",array[i]);
     }
     printf("\n");
}
6
  • hi, @Ujjwal Arora! your question may have a better chance of getting answered if you format your code according to the style guidelines. see manual.cs50.net/style!
    – kzidane
    Mar 27 '16 at 13:15
  • @Kareem: Thank You for your suggestions,i have reformatted the code to make it presentable,please have a look. Mar 27 '16 at 14:51
  • Are you running your code on the IDE and does it compile? If so, what is the purpose of the getch line in main? Could it be that the blinking cursor you're seeing is not an infinite loop but the program waiting for an input when it executes that line? Finally, in your mergesort function, you want mid=(beg+end)/2 inside the while loop for it to be recursive, otherwise its value will never change.
    – ronga
    Mar 28 '16 at 12:16
  • Hi @ronga ,i included the getch as i wanted to see the output if it was being executed correctly. Also,could you please elaborate on the mid=(beg+end)/2 being included inside the while loop? i am new to recursion and my implementation is a bit scratchy.My IDE is Dev C++ Mar 28 '16 at 13:54
  • Ok, so that answers the compilation issue, I can't seem to compile it on my end using the terminal, and I'm guessing neither can check50, so unless it can run on CS50 IDE, it won't pass. As Aquablitz below correctly identified (and which I inadvertently failed to mention), end, beg and mid are all staying static and not updating. For them to update, you need to put them within the while loop, so their values change each time the loop executes. As it is, their values are fixed as initial values you pass to the function. Also, your using a "," to separate conditions in the for loop should be ok.
    – ronga
    Mar 29 '16 at 3:54
1

Your first mergesort() call results in an infinite loop. beg < end will always evaluate to true as the value is not modified. Recursively calling mergesort() creates copies of those integers. Any changes inside those functions have no effect on them. Consider removing the loop. Add a check such that the function does nothing if there's only one element to be sorted.

Now, assuming your mergesort() is fixed, let's see the merge() function. An element in your array might be ignored. For example, with beg at 0, mid at 2 and end at 5. Your loop condition implies that you want i to be from 0 to 1 and j to be from 2 to 4. The fifth element is ignored. I believe you want i to range from 0 to 2 and j to range from 3 to 5, though. All while must be fixed. (<= instead?)

Furthermore, even if conditions are fixed, please check your j value carefully. For example, if you have beg at 0, end at 1 (an array with two elements), mid is obviously 0. Your merge() will start with i at 0 and j at 0. First time the loop executes, if condition is always false because they refer to same value, so else executes and turns j into 1. Another time the loop executes, if if part executes then it's fine. But.

If else part executes, i is at 0, j turns into 2. The loop exits. Next condition checking will result in else being executed as i is equal to mid. As that part executes, the loop will run once, setting the third element of your array. It shouldn't do that at all. You're sorting two, not three. This may cause a segmentation fault if it goes over array's boundary. How about setting j at mid + 1 instead?

You incorrectly specify conditions for for loop. Comma simply ignores the first condition and only second is significant. Link the conditions with && operator instead. Better off, you only need one variable here. Just i is enough. Make sure the value doesn't just start at 0. You don't want to accidentally replace the original array with garbage values trying to merge on the right side.

The condition for display() should be i < 6 also, not i < 5. Otherwise, the last element won't be displayed. And, lastly, don't forget to make it such that it doesn't fix to six elements. You might encounter some problems trying with bigger element count.

Good luck with your code!

2
  • Thank You @AquaBlitz11,I have made the necessary changes in the code,i am afraid i am still hazy on our explanation on variable "j". "Furthermore, please check your j value carefully. For example, if you have beg at 0, end at 1 and mid at 0, your i and j will be the same and your loops are prone to copying same value twice.". Could you please explain the same in a little detail? I have also modified my code to incorporate the logic pitfalls but my program is crashing,could you please take a look? Mar 29 '16 at 21:23
  • Okay, I added an explanation on that part. That should also explain possible segmentation fault. And, it seems like you forgot to change your last for loop condition in merge(). It should be i <= end. Mar 30 '16 at 7:32
0

when I compiled and executed your program, it terminated normally (i.e., it didn't get stuck in an infinite loop/recursion). however, it did not appear to be sorting the array correctly. I think your merging process is the problem.

if (array[i] < array[j])
{
    temp[k]=array[i];
    i++;                     
}
else
{
    temp[k]=array[j];
    j++;                     
}

giving your variables meaningless names (e.g., i, j, k, etc) makes your code much more difficult do understand. now here's a question: can i (aka beg) be ever equal to j (aka mid)? what happens in this case?

here is some pseudocode that may help you implement the merging process in a more elegant way:

define leftIndex and set it to the starting index of the left half
define rightIndex and set it to the starting index of the right half

calculate the number of elements in the two halves (in terms of the starting and ending indexes)
store the value above in SIZE
create a temporary array of size SIZE

for tempIndex = 0 to SIZE, increment tempIndex
    if leftIndex passed the ending index of the left half
        set temp[tempIndex] to array[rightIndex++]
    else if rightIndex passed the ending index of the right half
        set temp[tempIndex] to array[leftIndex++]
    else if array[leftIndex] < array[rightIndex]
        set temp[tempIndex] to array[leftIndex++]
    else
        set temp[tempIndex] to array[rightIndex++]

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .