EvilZone

Programming and Scripting => C - C++ => : haseebr21 September 21, 2015, 08:51:54 PM

: Stuck at Merge Sort Problem
: haseebr21 September 21, 2015, 08:51:54 PM

Hello, I am actually doing a merge sort assignment and I am stuck at the code and I don't know where am I making error, kindly help me out.

:

/**
  * Divide  : Divide the n-element array into two n/2-element
  *           sub-arrays
  * Conquer : Sort the two sub-arrays recursively using
  *           merge sort
  * Combine : Merge the two sorted subsequences to form the
  *           sorted array
  **/

#include<stdio.h>

int arr[20];       // array to be sorted

int main()
{

  int n,i;
  clrscr();
  printf("Enter the size of array\n");  // input the elements
  scanf("%d",&n);
  printf("Enter the elements:");
  for(i=0; i<n; i++)
    scanf("%d",&arr[i]);

  merge_sort(arr,0,n-1);  // sort the array

  printf("Sorted array:");  // print sorted array
  for(i=0; i<n; i++)
    printf("%d",arr[i]);
   getch();
  return 0;
}

int merge_sort(int arr[],int low,int high)
{
  int mid; int i;
  if(low<high) {

    mid=(low+high)/2;
    // Divide and Conquer
    merge_sort(arr,low,mid);
    merge_sort(arr,mid+1,high);
    // Combine


    merge(arr,low,mid,high);
  }

  return 0;
}

int merge(int arr[],int l,int m,int h)
{
  int arr1[10],arr2[10];  // Two temporary arrays to
  //hold the two arrays to be merged
  int n1,n2,i,j,k,z;

i=0;j=0;

for(z=l;z<=m;z++)
{
arr1[i]=arr[z];
i++;
}
for(z=m+1;z<=h;z++)
{
arr2[j]=arr[z];
j++;
}




  n1=i;
  n2=j;
  i=0;
  j=0;
  for(k=l; k<=h; k++)
  { //process of combining two sorted arrays

    if(i<n1 && j<n2)
    {
if(arr1[i]<=arr2[j])
      arr[k]=arr1[i++];
else
     arr[k]=arr2[j++];
     }
     else if(i>=n1)
     {
  arr[k]=arr[j++];
     }
     else
     {
arr[k]=arr[i++];
     }


  }

  return 0;
}



: Re: Stuck at Merge Sort Problem
: blindfuzzy September 21, 2015, 10:48:40 PM

I am assuming you have ran the code? Assuming that.....are you getting any errors? (If so what are they)

I'll have to run this later and see for myself.


EDIT: undeclared identifiers...maybe?

: Re: Stuck at Merge Sort Problem
: haseebr21 September 22, 2015, 08:02:23 AM

: blindfuzzy  September 21, 2015, 10:48:40 PM

I am assuming you have ran the code? Assuming that.....are you getting any errors? (If so what are they)

EDIT: undeclared identifiers...maybe?

I think there is some logical error which outputs a wrong value.

: Re: Stuck at Merge Sort Problem
: fuicious September 22, 2015, 06:48:28 PM

Isn't the merge_sort function supposed to divide the array? But yours is just calling itself without actually doing something, if I'm seeing this correctly.

EDIT: What I mean is that you should have more sub-arrays made at the point where you break it down to the ones that have only one element. As far as I can see here at the and you're going to have only the original array and 2 sub-arrays, which means that it's going to edit the original one multiple times, instead of just once.