Thread: Mergesort error!!

  1. #1
    Registered User
    Join Date
    May 2012
    Posts
    13

    Mergesort error!!


    i am trying hard to make my mergesort algorithm but at the moment, syntaxically it is correct, but while executing it stops at the split function. please chek this program, its the third one, am trying to simplify mergesort. if you can run the program please tell me what you are doing. am using Borland C/C++ 5 on windows 7.

    Code:
    #include<iostream.h>#include<conio.h>
    #include<stdlib.h>
    char a[1000];
    void merge(int b[],int c[])
    {
        char str;
        if(b<c){
           str=(char)b;
          strcat(a,(const char*)str);
          str=(char)c;
          strcat(a,(const char*)str);
          }
       else if(b==c){
           str=(char)b;
          strcat(a,(const char*)str);
          }
       else{
           str=(char)c;
          strcat(a,(const char*)str);
          str=(char)b;
          strcat(a,(const char*)str);
          }
    
    
    
    
    }
    
    
    void copy(int x[], int s, int e, int y[])
    {
        int i,j=0;
        for(i=s;i<=e;i++){
           j++;
           y[j]=x[i];
          }
    }
    void split(int a[],int l, int h)
    {
        int b[100],c[100],mid;
       mid=(l+h)/2;
       copy(a,l,mid,b);
       copy(a,mid+1,h,b);
       while(h>1)
       {
           split(b,0,mid+1);
          split(c,0,mid+1);
          }
       merge(b,c);
    }
    
    
    void main()
    {
        int n, a[1000];
       cout<<"Enter the number of elements";
       cin>>n;
       for(int i=0;i<n;i++)
           a[i]=(rand()%1000);
       if(n>1)
       split(a,0,n);
       cout<<a;
       }

    i can post my previous program also if required.
    it is popping up in the assembly language area and i am not understanding wer the error is happening.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > str=(char)b;
    > strcat(a,(const char*)str);
    > str=(char)c;
    > strcat(a,(const char*)str);
    What on earth are you trying to achieve here!?

    If you're casting and you don't know why, then you're doing it wrong.

    strcat needs a nul-terminated array of chars, and str just isn't that.

    Since this is C++, then drop the char arrays, and figure out how to do this using std::string instead.


    > char a[1000];
    ...
    > int n, a[1000];
    Next you need to sort out scope issues, and naming global variables with pointless names like 'a'.
    For a start, you shouldn't be using any globals at all.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    May 2012
    Location
    Bonn, Germany
    Posts
    16
    Also, you compare b and c although they are arrays.
    What you do then is compare their addresses ...
    I guess you have a lot to learn still, maybe you should get a good introduction before trying things like Mergesort.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    "copy" and "split" are vaguely alright, though "split" should not contain a while loop, which is the cause of your infinite loop.
    b and c are too small.

    "merge" on the other hand is 100% wrong. Every line, including the prototype, is totally wrong.
    Why on earth would you involve string manipulation functions when you are not sorting strings?

    Remove the global variable.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    May 2012
    Posts
    13
    i hve to use global wats rong with tat?!? am trying to copy the number in the array into the string or character without the compiler mistaking it to be ASCII!?!

  6. #6
    Registered User
    Join Date
    May 2012
    Posts
    13
    buddy, i have learn much, but the point wen ur ready to try anything is this, i am trying quite a lot to make this ........ work coz at my ADA(analysis of design of algorithms) lab they gave a ........ty rong program. so now the only way is to get one of the net or rite my own...

  7. #7
    Registered User
    Join Date
    May 2012
    Posts
    13
    @Tomas am comparing 2 arrrays and pushing it into a string. tats merge. if b[i] is smaller, it goes first els c[i] goes first. assuming tat while h<=1 it would have split the array into 1 element each. but am not getting how to merge without i. i is not required coz it is just b and c. no other numbers. but how to get wat happened to the array?
    @all am not actually merging the arrays. am just putting into a string. so its much easier. ill just output the string in the end. and its c++ but it can be in c also.

  8. #8
    Registered User
    Join Date
    May 2012
    Posts
    13
    @salem: am casting coz i dont wnat the output to be ascii'd. like if u store char x=65 then it will print 'a' right!!?! so im trying to make the compiler treat it as a string. i dint know tat bout strcat. ok then how do i add b[i] or c[i] or b and c into the string? and its a trail prgram please lets not focus on names ..!!

  9. #9
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    O_o

    i cma buy 2 hlp but dcided not 2 coz i cn't ........ing unnerstans nething u sayd.

    Soma

  10. #10
    Registered User
    Join Date
    May 2012
    Posts
    13
    @iMalc: hey if there is no while loop then how does it terminate?? how do u control the recursive function cal.. it keeps on quiting i think of infinite looping, but then how to fix tat?!? and wat it is it with global variable all?? i though it was cool to use tat. not 'cool' cool but just no problem. my teachers seem to be cool with tat.

  11. #11
    Registered User
    Join Date
    May 2012
    Posts
    13
    @Tomas: sory man, ur right, i mised it.

    33 22 1 55 11 5 6
    33 22 1 | 55 11 5 6
    33| 22 1| 55 11| 5 6
    33| 22| 1| 55| 11| 5| 6
    ^ ^ ^ ^ ^ ^ ^


    how to address or get these? tats y i tried b<c. should be at least b[0] <c [0], just misd it while typing. in all the confusion....

  12. #12
    Registered User
    Join Date
    May 2012
    Posts
    13
    @soma sory man. i split the array and and push it into string while sorting it. then i o/p the string, simple right. write the prgram..

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Alright I'm in a good mood so I'm going to be kind here and help out as best I can.

    Look at lines 3 and 55. You have two variables named 'a' and are confusing the two. I suggested you delete the global one because locals are preferable.

    if there is no while loop then how does it terminate?? how do u control the recursive function cal.
    Adding a loop isn't going to make it any more likely to terminate, just like adding fuel into your car isn't going to make it more likely to stop. It's actually quite the opposite. In any case if the body of the loop does nothing to change the value of the while loop condition (and it is initialy true), then it will loop forever. Nothing changes h, so it's going to forever stay greater than 1.
    If you don't yet understand recursive functions, then put this problem asside for a bit and try some practice examples such as writing a recursive factorial function, and perhaps a recursive fibonacci function.

    am not actually merging the arrays. am just putting into a string
    That might be your intention, but your code is not doing anything remotely like that.

    am casting coz i dont wnat the output to be ascii'd. like if u store char x=65 then it will print 'a' right!!?! so im trying to make the compiler treat it as a string.
    Okay, but you can't magically change an array of integers into a string just because you threw some casts in there. At the level of ones and zeros, casts don't actually do anything. If the underlying data wasn't a string already then it wont be a string after casting. Besides, if you wanted to make a string, you'd have to actually have a char array somewhere to put it.
    What you're actually doing is defending your very broken merge function, when what you probably mean to be doing is defending your intentions. We don't doubt your intentions, but we know very well that the code you have wont do anything like what you want. That's just how it is.

    Once you've taken that all in and had a go at fixing it, you may wish to post some updated code.
    Last edited by iMalc; 05-19-2012 at 10:30 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    am casting coz i dont wnat the output to be ascii'd. like if u store char x=65 then it will print 'a' right!!?! so im trying to make the compiler treat it as a string.
    iMalc's response to this is serviceable but I just want to make it abundantly clear, even if you want to store small numbers using the char data type (as a zero terminated string or otherwise) the data will still be interpreted like a character would by C++'s standard functions and even C++'s operators, and not like an integer. Your comparisons with strcmp() don't make any sense for a couple of reasons. One is even if you were using it correctly, it compares alphabetically, not numerically. strcmp() also involves an entire array in the comparison, deciding whether one string comes before another alphabetically; it doesn't help you order the elements of the array. I don't think there is a reason anymore to store small numbers with char. There is no reason for you to insist to use char either in response to me because it actually makes your job significantly harder.
    Last edited by whiteflags; 05-19-2012 at 11:06 PM. Reason: clarification and trains

  15. #15
    Registered User
    Join Date
    May 2012
    Posts
    13
    @i malc oh i really f*king missed that.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ MergeSort
    By Jesse20ghet in forum C++ Programming
    Replies: 14
    Last Post: 06-15-2011, 01:24 PM
  2. my mergeSort
    By Soulzityr in forum C Programming
    Replies: 41
    Last Post: 03-29-2010, 12:27 PM
  3. Mergesort in C
    By Oduig in forum C Programming
    Replies: 2
    Last Post: 09-14-2008, 11:30 AM
  4. Mergesort
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 10-26-2005, 11:45 PM
  5. mergesort
    By AmazingRando in forum C++ Programming
    Replies: 14
    Last Post: 02-29-2004, 09:35 AM

Tags for this Thread