Connecting Tech Pros Worldwide Forums | Help | Site Map
bytes > topic > c > answers

merge sort help

Newbie
  
Join Date: Oct 2007
Location: Chicago
Posts: 9
#1: Oct 31 '07
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. { 
  56.     long timeElapsed;
  57.     timeElapsed = clock();
  58.     int num,i,elem, percent;
  59.     a[num];
  60.     cout<<"*********************************************************************"<<endl;
  61.     cout<<"                             MERGE SORT PROGRAM"<<endl;
  62.     cout<<"**********************************************************************"<<endl<<endl<<endl;
  63.     cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort[THEN PRESS ENTER]:"<<endl;
  64.     cin>>num;
  65.     cout<<"Please Enter THE PERCENTAGE you want to sort[THEN PRESS ENTER]:"<<endl;
  66.     cin>>percent;
  67.     for (i=1; i<=num; i++)
  68.     {
  69.         elem =((rand()*9)+1);
  70.         cout<<endl<<"element "<<i<<"is "<<elem<<endl;
  71.         a[i]= elem;
  72.         cout<<"When i is "<<i<<" ai is "<<a[i];
  73.     }
  74.     merge_sort(1,num);
  75.     cout<<endl<<"So, the sorted list (using MERGE SORT) will be : "<<endl;
  76.     for(i=1;i<=num;i++)
  77.     {
  78.          cout<<a[i]<<" ";
  79.     }
  80.     cout<<endl<<"Time Elapsed is: "<<timeElapsed<<endl<<endl<<endl<<endl<<endl;
  81.     system("PAUSE");
  82. return 0;
  83. }

gpraghuram's Avatar
Expert
  
Join Date: Mar 2007
Location: Chennai
Posts: 1,258
#2: Oct 31 '07

re: merge sort help

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. { 
  58.     long timeElapsed;
  59.     timeElapsed = clock();
  60.     int num,i,elem, percent;
  61.     //a[num];
  62.     cout<<"**************************************************  *******************"<<endl;
  63.     cout<<"                             MERGE SORT PROGRAM"<<endl;
  64.     cout<<"**************************************************  ********************"<<endl<<endl<<endl;
  65.     cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort[THEN PRESS ENTER]:"<<endl;
  66.     cin>>num;
  67.     cout<<"Please Enter THE PERCENTAGE you want to sort[THEN PRESS ENTER]:"<<endl;
  68.     cin>>percent;
  69.     //for (i=1; i<=num; i++)
  70.     for (i=0; i<num; i++)
  71.     {
  72.         elem =((rand()*9)+1);
  73.         cout<<endl<<"element "<<i<<"is "<<elem<<endl;
  74.         a[i]= elem;
  75.         cout<<"When i is "<<i<<" ai is "<<a[i];
  76.     }
  77.     //merge_sort(1,num);
  78.     merge_sort(0,num);
  79.     cout<<endl<<"So, the sorted list (using MERGE SORT) will be : "<<endl;
  80.     //for(i=1;i<=num;i++)
  81.     for(i=0;i<num;i++)
  82.     {
  83.          cout<<a[i]<<" ";
  84.     }
  85.     cout<<endl<<"Time Elapsed is: "<<timeElapsed<<endl<<endl<<endl<<endl<<endl;
  86.     system("PAUSE");
  87. return 0;
  88. }
  89.  
  90.  
Try this....i havent checked the logic of ur code still...
Raghuram
Newbie
  
Join Date: Oct 2007
Location: Chicago
Posts: 9
#3: Oct 31 '07

re: merge sort help

<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!!
Reply

« previous question | next question »

Similar C / C++ bytes

/bytes/development

/bytes/it

Forums
Visit our community forums for general discussions and latest on Bytes

Our staff and community areas have moved to bytes.com/forums/

/bytes/about

We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights. Get the best answers to your questions from over 226,531 network members.

dev questions:
algorithms | asp | asp.net | c/c++ | coldfusion | c# | flash | html/css | java | javascript |
mobile dev | .net | perl | php | python | ruby | software dev | vb.net | visual basic | xml
it questions:
access | apache | careers | db2 | iis | macosx | mysql | networking | oracle | postgresql | sql server | unix | windows

About Bytes | Copyright 1995-2009 BYTES. All rights Reserved