473,322 Members | 1,409 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

merge sort help

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
2 2866
gpraghuram
1,275 Expert 1GB
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
<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

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

Similar topics

3
by: Kevin King | last post by:
I have a question about an assignment I have. I need to count the number of comparisons in my merge sort. I know that the function is roughly nlog(n), but I am definately coming up with too many...
5
by: Tom Keane | last post by:
Okay, so the deal is, I am doing a mail merge document in order to print invoices. The field I get the amount of money is "invAmount". What I would like to do is be able to manipulate this number...
1
by: Booser | last post by:
// Merge sort using circular linked list // By Jason Hall <booser108@yahoo.com> #include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> //#define debug
9
by: rkk | last post by:
Hi, I have written a generic mergesort program which is as below: --------------------------------------------------------- mergesort.h ----------------------- void MergeSort(void...
7
by: Zeba | last post by:
Hi, I have to write program in C# to merge sort a linked list (doubly linked). Is it true that the best way to do it is copy it into an array, sort it and then convert back ? I'm new to C#,...
16
by: Sam Durai | last post by:
Hello, I need to merge a small table (of rows less than 100,sometimes even 0 rows) to a big table (of rows around 4 billion). I used the PK of the big table as merge key but merge does a table scan...
5
by: Sarahger9 | last post by:
I am trying to generate a random vector of integers and sort them using merge sort. I am having trouble with the code. It is long, but I would appreciate if someone could take a look at it and see...
0
by: enigma08 | last post by:
I need to merge sort two linked lists, each has a header and the elements are all ints. I've tried adapting some generic code, but have run into a problem - errors that are similar to this one: ...
9
by: Tem | last post by:
List<inta = new List<int>(); a.Add(1); a.Add(2); a.Add(3); List<intb = new List<int>(); b.Add(3); b.Add(4); b.Add(5);
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.