By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,537 Members | 1,743 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,537 IT Pros & Developers. It's quick & easy.

merge sort help

P: 9
below is my code for my merge sort but I can't get it to sort properly. I am trying generate random numbers based on input from the user and then sort those random numbers. Can you tell me what I am doing wrong?

Expand|Select|Wrap|Line Numbers
  1. void merge(int,int,int);
  2. void merge_sort(int low, int high)
  3. {
  4.  int mid, temp;
  5.  if (low==high)
  6.      return;
  7.  if (low+1==high)
  8.  {
  9.      temp=high;
  10.      high=low;
  11.      low=temp;
  12.  }
  13.  if(low<high)
  14.  {
  15.   mid=(low+high)/2;
  16.   merge_sort(low,mid);
  17.   merge_sort(mid+1,high);
  18.   merge(low,mid,high);
  19.  }
  20. }
  21. void merge(int low,int mid,int high)
  22. {
  23.     int p, q, i, c[10],r;
  24.      p=low; //index for a[i]...a[mid]
  25.      q=mid+1; //index for a[mid + 1]...a[j]
  26.     while((p<=mid)&&(q<=high))
  27.     {
  28.         if(a[p]<=a[q]) //copy smaller value to local array c
  29.         {
  30.             c[i]=a[p];
  31.            p++;
  32.           }
  33.         else
  34.           {
  35.            c[i]=a[q];
  36.            q++;
  37.           }
  38.       i++;
  39.     }
  40.     while (a[p]<= mid)//copy the rest of the longer array
  41.     {
  42.          c[i] = a[p];
  43.     }
  44.     while (a[q]<=high)//copy the rest of the larger array
  45.      {
  46.          c[i]=a[q];
  47.      }
  48.     for (i=low; i<=high; i++)//copy back from temp array to main array
  49.         {
  50.          a[i]=c[i];
  51.          }
  52. }
  53.  
  54. int main()
  55.     long timeElapsed;
  56.     timeElapsed = clock();
  57.     int num,i,elem, percent;
  58.     a[num];
  59.     cout<<"*********************************************************************"<<endl;
  60.     cout<<"                             MERGE SORT PROGRAM"<<endl;
  61.     cout<<"**********************************************************************"<<endl<<endl<<endl;
  62.     cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort[THEN PRESS ENTER]:"<<endl;
  63.     cin>>num;
  64.     cout<<"Please Enter THE PERCENTAGE you want to sort[THEN PRESS ENTER]:"<<endl;
  65.     cin>>percent;
  66.     for (i=1; i<=num; i++)
  67.     {
  68.         elem =((rand()*9)+1);
  69.         cout<<endl<<"element "<<i<<"is "<<elem<<endl;
  70.         a[i]= elem;
  71.         cout<<"When i is "<<i<<" ai is "<<a[i];
  72.     }
  73.     merge_sort(1,num);
  74.     cout<<endl<<"So, the sorted list (using MERGE SORT) will be : "<<endl;
  75.     for(i=1;i<=num;i++)
  76.     {
  77.          cout<<a[i]<<" ";
  78.     }
  79.     cout<<endl<<"Time Elapsed is: "<<timeElapsed<<endl<<endl<<endl<<endl<<endl;
  80.     system("PAUSE");
  81. return 0;
  82. }
Oct 31 '07 #1
Share this Question
Share on Google+
2 Replies


gpraghuram
Expert 100+
P: 1,275
Hi,
There are couple of issues in the code....
1)First u start referencing the array from 1 and reach the max size which is wrong(For example if size of array is 5 then in the loop u shuld start from 0 and reference upto 4)
2)U are not initializing local variables before usage.

I have corrected some part of the code and posted it here....
Expand|Select|Wrap|Line Numbers
  1. void merge(int,int,int);
  2. void merge_sort(int low, int high)
  3. {
  4.  int mid, temp;
  5.  if (low==high)
  6.      return;
  7.  if (low+1==high)
  8.  {
  9.      temp=high;
  10.      high=low;
  11.      low=temp;
  12.  }
  13.  if(low<high)
  14.  {
  15.   mid=(low+high)/2;
  16.   merge_sort(low,mid);
  17.   merge_sort(mid+1,high);
  18.   merge(low,mid,high);
  19.  }
  20. }
  21. void merge(int low,int mid,int high)
  22. {
  23.     int p, q, i, c[10],r;
  24.     i=0;
  25.     r=0;
  26.      p=low; //index for a[i]...a[mid]
  27.      q=mid+1; //index for a[mid + 1]...a[j]
  28.     while((p<=mid)&&(q<=high))
  29.     {
  30.         if(a[p]<=a[q]) //copy smaller value to local array c
  31.         {
  32.             c[i]=a[p];
  33.            p++;
  34.           }
  35.         else
  36.           {
  37.            c[i]=a[q];
  38.            q++;
  39.           }
  40.       i++;
  41.     }
  42.     while (a[p]<= mid)//copy the rest of the longer array
  43.     {
  44.          c[i] = a[p];
  45.     }
  46.     while (a[q]<=high)//copy the rest of the larger array
  47.      {
  48.          c[i]=a[q];
  49.      }
  50.     for (i=low; i<=high; i++)//copy back from temp array to main array
  51.         {
  52.          a[i]=c[i];
  53.          }
  54. }
  55.  
  56. int main()
  57.     long timeElapsed;
  58.     timeElapsed = clock();
  59.     int num,i,elem, percent;
  60.     //a[num];
  61.     cout<<"**************************************************  *******************"<<endl;
  62.     cout<<"                             MERGE SORT PROGRAM"<<endl;
  63.     cout<<"**************************************************  ********************"<<endl<<endl<<endl;
  64.     cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort[THEN PRESS ENTER]:"<<endl;
  65.     cin>>num;
  66.     cout<<"Please Enter THE PERCENTAGE you want to sort[THEN PRESS ENTER]:"<<endl;
  67.     cin>>percent;
  68.     //for (i=1; i<=num; i++)
  69.     for (i=0; i<num; i++)
  70.     {
  71.         elem =((rand()*9)+1);
  72.         cout<<endl<<"element "<<i<<"is "<<elem<<endl;
  73.         a[i]= elem;
  74.         cout<<"When i is "<<i<<" ai is "<<a[i];
  75.     }
  76.     //merge_sort(1,num);
  77.     merge_sort(0,num);
  78.     cout<<endl<<"So, the sorted list (using MERGE SORT) will be : "<<endl;
  79.     //for(i=1;i<=num;i++)
  80.     for(i=0;i<num;i++)
  81.     {
  82.          cout<<a[i]<<" ";
  83.     }
  84.     cout<<endl<<"Time Elapsed is: "<<timeElapsed<<endl<<endl<<endl<<endl<<endl;
  85.     system("PAUSE");
  86. return 0;
  87. }
  88.  
  89.  
Try this....i havent checked the logic of ur code still...
Raghuram
Oct 31 '07 #2

P: 9
<Sometimes posting with a quote and code causes the post to disappear. The quote has been removed so that the response is visible.

MODERATOR>

I tried this and it looks good, but my sort isn't sorting correctly. Can you you look at the logic? Thank you!!
Oct 31 '07 #3

Post your reply

Sign in to post your reply or Sign up for a free account.