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

Merge Sort

computerfox
100+
P: 278
Hello everyone,

I'm having some trouble with the code for merge sort. I get what is it but the code doesn't seem to work. Here is my code:


Expand|Select|Wrap|Line Numbers
  1. ////.h
  2.  
  3. #include <iostream>
  4. #include <string>
  5. using namespace std;
  6.  
  7.  
  8. string merge(string,string);
  9. string mergeSort(string);
  10. string rest(int,int,string);
  11.  
  12. string rest(int from,int to,string phrase){
  13.     string temp;
  14.  
  15.     for(int i=from;i<=to;i++){
  16.         temp[i-1]=phrase[i];
  17.     }
  18.     return temp;
  19. }
  20. string merge(string left,string right){
  21.     string result;
  22. * * while (left.length() > 0 || right.length() > 0){
  23. * * * * if (left.length() > 0 && right.length() > 0){
  24.             if (left[0] <= right[0]){
  25. * * * * * * * * result+=left[0];
  26. * * * * * * * * left= rest(1,left.length(),left);
  27.             }
  28.             if(left[0]>right[0])
  29.             * * {
  30.                 result+=right[0];
  31.                 right= rest(1,right.length(),right);
  32.             }
  33.                 if (left.length() > 0){
  34.                     result+= left[0];
  35.                     left= rest(1,left.length(),left);
  36.                 }
  37.                 if (right.length() > 0){
  38.  
  39.                 * * result+=right[0];
  40.                     right= rest(1,right.length(),right);
  41.                 }
  42.             }
  43.         }
  44.     return result;    
  45. }
  46. string mergeSort(string a){
  47.     if(a.length()<=1)
  48.         return a;
  49.  
  50.     string left,right,result;
  51.     int middle=(a.length())/2;
  52.  
  53.     for(int i=0;i<a.length();i++){
  54.         if(i<middle)
  55.         * left+=a[i];
  56.         else*
  57.             if(i>=middle)
  58.             right+=a[i];
  59.  
  60.     }
  61.     left = mergeSort(left);
  62. * * right = mergeSort(right);
  63. * * result = merge(left, right);
  64. * * return result+left;
  65. }
  66.  
  67.  
  68.  
  69.  
  70. ////.cpp
  71.  
  72. #include "mergeSort.h"
  73. using namespace std;
  74.  
  75. int main () {
  76. * * string a,b;
  77.     int again=1;
  78.     while(again==1){
  79.  
  80.     * * cout<<"Enter string to sort: ";
  81.     * * cin>>a;        
  82.         cout<<"Before the sort: "<<a<<endl;
  83.         cout<<"After sort: ";
  84.         cout<<mergeSort(a)<<endl;
  85.     * * cout<<"1-Again* 2-Close: ";
  86.         cin>>again;
  87.     }
  88.  
  89. * * return 0;
  90. }
  91.  
Any ideas?
Oct 28 '11 #1

✓ answered by computerfox

Easy fix-

Expand|Select|Wrap|Line Numbers
  1.  
  2. ////.h
  3.  
  4. #include <iostream>
  5. #include <string>
  6. using namespace std;
  7.  
  8. char *mergeSort(char letters[], char temp[], int array_size);
  9. char *mSort(char letters[], char temp[], int left, int right);
  10. char *merge(char letters[], char temp[], int left, int mid, int right);
  11.  
  12. char *mergeSort(char letters[], char temp[], int array_size)
  13. {
  14.     return mSort( letters, temp, 0, array_size - 1);
  15. }
  16.  
  17.  
  18. char *mSort(char letters[], char temp[], int left, int right)
  19. {
  20.     int mid;
  21.  
  22.     if (right > left)
  23.     {
  24.         mid = (right + left) / 2;
  25.         mSort( letters, temp, left, mid);
  26.         mSort( letters, temp, (mid+1), right);
  27.  
  28.         merge( letters, temp, left, (mid+1), right);
  29.     }
  30.  
  31.     return letters;
  32. }
  33.  
  34. char *merge(char letters[], char temp[], int left, int mid, int right)
  35. {
  36.     int i, leftEnd, elements, tmpPos;
  37.  
  38.     leftEnd = (mid - 1);
  39.     tmpPos = left;
  40.     elements = (right - left + 1);
  41.  
  42.     while ((left <= leftEnd) && (mid <= right))
  43.     {
  44.         if ( letters[left] <=  letters[mid])
  45.         {
  46.             temp[tmpPos] =  letters[left];
  47.             tmpPos += 1;
  48.             left += 1;
  49.         }
  50.         else
  51.         {
  52.             temp[tmpPos] =  letters[mid];
  53.             tmpPos += 1;
  54.             mid += 1;
  55.         }
  56.     }
  57.  
  58.     while (left <= leftEnd)
  59.     {
  60.         temp[tmpPos] =  letters[left];
  61.         left += 1;
  62.         tmpPos += 1;
  63.     }
  64.     while (mid <= right)
  65.     {
  66.         temp[tmpPos] =  letters[mid];
  67.         mid += 1;
  68.         tmpPos += 1;
  69.     }
  70.  
  71.     for (i=0; i < elements; i++)
  72.     {
  73.         letters[right] = temp[right];
  74.         right -= 1;
  75.     }
  76.  
  77.     return temp;
  78. }
  79.  
  80.  
  81. ////.cpp
  82.  
  83.  
  84. #include "mergeSort.h"
  85.  
  86. int main()
  87. {
  88.     int max,again=1;
  89.  
  90.     while(again==1){
  91.     cout<<"Word size: ";
  92.     cin>>max;
  93.  
  94.     char arrayOne[max];
  95.     char arrayTwo[max];
  96.         string result;
  97.  
  98.     cout<<"Enter word to sort: ";
  99.  
  100.     //Enter character array
  101.     for(int i=0;i<max;i++){
  102.         cout<<"Letter"<<i+1<<"/"<<max<<": ";
  103.         cin>>arrayOne[i];
  104.     }
  105.  
  106.     //Before the sort    
  107.     cout<<"Before the sort: ";
  108.     for(int i=0;i<max;i++)
  109.         cout<<arrayOne[i]<<" ";
  110.     cout<<endl;
  111.  
  112.     //Sort
  113.     result=mergeSort(arrayOne, arrayTwo, max);
  114.  
  115.     //After the sort
  116.  
  117.     cout<<"After the sort: ";
  118.     for(int i=0;i<max;i++)
  119.         cout<<result[i]<<" ";
  120.     cout<<endl;
  121.  
  122.         cout<<"1-Again  2-Close: ";
  123.         cin>>again;
  124.     }
  125.  
  126.     cout<<endl;
  127.     return 0;
  128. }
  129.  
Merge sort can not be done with strings, you need a list of either characters or arrays. Despite strings being character arrays, it treats it differently.

Share this Question
Share on Google+
1 Reply


computerfox
100+
P: 278
Easy fix-

Expand|Select|Wrap|Line Numbers
  1.  
  2. ////.h
  3.  
  4. #include <iostream>
  5. #include <string>
  6. using namespace std;
  7.  
  8. char *mergeSort(char letters[], char temp[], int array_size);
  9. char *mSort(char letters[], char temp[], int left, int right);
  10. char *merge(char letters[], char temp[], int left, int mid, int right);
  11.  
  12. char *mergeSort(char letters[], char temp[], int array_size)
  13. {
  14.     return mSort( letters, temp, 0, array_size - 1);
  15. }
  16.  
  17.  
  18. char *mSort(char letters[], char temp[], int left, int right)
  19. {
  20.     int mid;
  21.  
  22.     if (right > left)
  23.     {
  24.         mid = (right + left) / 2;
  25.         mSort( letters, temp, left, mid);
  26.         mSort( letters, temp, (mid+1), right);
  27.  
  28.         merge( letters, temp, left, (mid+1), right);
  29.     }
  30.  
  31.     return letters;
  32. }
  33.  
  34. char *merge(char letters[], char temp[], int left, int mid, int right)
  35. {
  36.     int i, leftEnd, elements, tmpPos;
  37.  
  38.     leftEnd = (mid - 1);
  39.     tmpPos = left;
  40.     elements = (right - left + 1);
  41.  
  42.     while ((left <= leftEnd) && (mid <= right))
  43.     {
  44.         if ( letters[left] <=  letters[mid])
  45.         {
  46.             temp[tmpPos] =  letters[left];
  47.             tmpPos += 1;
  48.             left += 1;
  49.         }
  50.         else
  51.         {
  52.             temp[tmpPos] =  letters[mid];
  53.             tmpPos += 1;
  54.             mid += 1;
  55.         }
  56.     }
  57.  
  58.     while (left <= leftEnd)
  59.     {
  60.         temp[tmpPos] =  letters[left];
  61.         left += 1;
  62.         tmpPos += 1;
  63.     }
  64.     while (mid <= right)
  65.     {
  66.         temp[tmpPos] =  letters[mid];
  67.         mid += 1;
  68.         tmpPos += 1;
  69.     }
  70.  
  71.     for (i=0; i < elements; i++)
  72.     {
  73.         letters[right] = temp[right];
  74.         right -= 1;
  75.     }
  76.  
  77.     return temp;
  78. }
  79.  
  80.  
  81. ////.cpp
  82.  
  83.  
  84. #include "mergeSort.h"
  85.  
  86. int main()
  87. {
  88.     int max,again=1;
  89.  
  90.     while(again==1){
  91.     cout<<"Word size: ";
  92.     cin>>max;
  93.  
  94.     char arrayOne[max];
  95.     char arrayTwo[max];
  96.         string result;
  97.  
  98.     cout<<"Enter word to sort: ";
  99.  
  100.     //Enter character array
  101.     for(int i=0;i<max;i++){
  102.         cout<<"Letter"<<i+1<<"/"<<max<<": ";
  103.         cin>>arrayOne[i];
  104.     }
  105.  
  106.     //Before the sort    
  107.     cout<<"Before the sort: ";
  108.     for(int i=0;i<max;i++)
  109.         cout<<arrayOne[i]<<" ";
  110.     cout<<endl;
  111.  
  112.     //Sort
  113.     result=mergeSort(arrayOne, arrayTwo, max);
  114.  
  115.     //After the sort
  116.  
  117.     cout<<"After the sort: ";
  118.     for(int i=0;i<max;i++)
  119.         cout<<result[i]<<" ";
  120.     cout<<endl;
  121.  
  122.         cout<<"1-Again  2-Close: ";
  123.         cin>>again;
  124.     }
  125.  
  126.     cout<<endl;
  127.     return 0;
  128. }
  129.  
Merge sort can not be done with strings, you need a list of either characters or arrays. Despite strings being character arrays, it treats it differently.
Oct 28 '11 #2

Post your reply

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