Merging arrays help

This is a discussion on Merging arrays help within the C Programming forums, part of the General Programming Boards category; Hello all. I'm having trouble merging arrays here. So first I allow the user to enter the size of the ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    13

    Merging arrays help

    Hello all. I'm having trouble merging arrays here. So first I allow the user to enter the size of the array, followed by the elements. Then I use a bubble sort to get them in ascending order. And I do this for two sets of values. But I can't seem to get them to merge. Please look at my code and help if you can ...

    Code:
    #include<stdio.h>
    #include<conio.h>
    #define SIZE 4
    
    int bubble_sort(int array[],int w);
    int merge(int array1[], int w1, int array2[], int w2);
    
    int main(void)
    {
        /*Accept values for Values1*/
        
        int array1[10],val_1,i,x;
        
        printf("Please enter the array size of Values1.\n");
        scanf("%d",&i);
        
        printf("Please enter the elements of Values1.\n");
        for(x = 0; x < i; x++)
        {
              scanf("%d",&val_1);
              array1[x] = val_1;
        }
        
        
        bubble_sort(array1,i);
        
    
        /*Accept values for Values2*/
        
        int array2[10],val_2,y,z;
        
        printf("Please enter the array size of Values2.\n");
        scanf("%d",&y);
        
        printf("Please enter the elements of Values2.\n");
        for(z = 0; z < y; z++)
        {
              scanf("%d",&val_2);
              array2[z] = val_2;
        }
        bubble_sort(array2,y);
        
        printf("The sorted elements of Values1 are:");
        for(x = 0; x < i; x++)
        {
              printf("%d",array1[x]);
        }
        
        printf("\n");
        printf("The sorted elements of Values2 are:");
        for(z = 0; z < y; z++)
        {
              printf("%d",array2[z]);
        }
        
        merge(array1,i,array2,y);
        
        getch();
        
        
        
    }
    
    int bubble_sort(int array[],int w)
    {
        int c1,c2,hold;
        for (c1 = 1; c1 < w; c1++)
        {
            for (c2 = 0; c2 < w-1; c2 ++) 
            {
                 if (array[c2] > array[c2+1])
                 {
                          hold = array[c2];
                          array[c2] = array[c2+1];
                          array[c2+1] = hold;
                 }
                 }
        }
    }
    
    int merge(int array1[], int w1, int array2[], int w2)
    {
        int f,c, array3[20];
        
        for(f = 0; f < (w1+w2) ; f++)
        {
                
              if(array1[f] < array2[f])
              {
                 
                 array3[f] = array1[f]; 
                 array3[f+1] = array2[f];                     
              }
              else 
              {
                 array3[f] = array2[f];
                 array3[f+1] = array1[f];
              }
        }    
        
        
            
    
        printf("The final values are:\n");
        for(f = 0; f < (w1+w2); f++)
        {
              printf("%d ",array3[f]); 
        }
    }
    I keep getting hexidecimal digits for the output of the final 3 numbers. I think its because the values for each half to be merged are less than the counter for the loop, and so when it loops they have no value in that array element.
    Last edited by key4life; 12-04-2009 at 08:43 PM. Reason: Adding extra info

  2. #2
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Do you want the merged array to be in sorted order? If so, then you'll have to call bubblesort function again after calling merge function.
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  3. #3
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    One more mistake. Suppose the size of both the arrays is 3, then your for loop in merge() will run till 5 iterations but what will the value of array1[4], array1[5] and same for array2. So the loop should run till the array with more elements in it.
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  4. #4
    Registered User
    Join Date
    Nov 2009
    Posts
    13
    I dont think I would need to run the bubble sort again in merge() because the arrays are already sorted, so no need to re-sort. I would just be comparing sorted values. So it would come out in ascending order either way.

    Ok, thanks for the advice Ben. I made it so that the larger value is used as the criteria for the for loop. Now it outputs the first 3, followed by the last number of the second set and a zero.


    Code:
    #include<stdio.h>
    #include<conio.h>
    #define SIZE 4
    
    int bubble_sort(int array[],int w);
    int merge(int array1[], int w1, int array2[], int w2);
    
    int main(void)
    {
        /*Accept values for Values1*/
        
        int array1[10],val_1,i,x;
        
        printf("Please enter the array size of Values1.\n");
        scanf("%d",&i);
        
        printf("Please enter the elements of Values1.\n");
        for(x = 0; x < i; x++)
        {
              scanf("%d",&val_1);
              array1[x] = val_1;
        }
        
        
        bubble_sort(array1,i);
        
    
        /*Accept values for Values2*/
        
        int array2[10],val_2,y,z;
        
        printf("Please enter the array size of Values2.\n");
        scanf("%d",&y);
        
        printf("Please enter the elements of Values2.\n");
        for(z = 0; z < y; z++)
        {
              scanf("%d",&val_2);
              array2[z] = val_2;
        }
        bubble_sort(array2,y);
        
        printf("The sorted elements of Values1 are:");
        for(x = 0; x < i; x++)
        {
              printf("%d",array1[x]);
        }
        
        printf("\n");
        printf("The sorted elements of Values2 are:");
        for(z = 0; z < y; z++)
        {
              printf("%d",array2[z]);
        }
        
        merge(array1,i,array2,y);
        
        getch();
        
        
        
    }
    
    int bubble_sort(int array[],int w)
    {
        int c1,c2,hold;
        for (c1 = 1; c1 < w; c1++)
        {
            for (c2 = 0; c2 < w-1; c2 ++) 
            {
                 if (array[c2] > array[c2+1])
                 {
                          hold = array[c2];
                          array[c2] = array[c2+1];
                          array[c2+1] = hold;
                 }
                 }
        }
    }
    
    int merge(int array1[], int w1, int array2[], int w2)
    {
        int f,c, array3[20],largest = 0;
        if (w1 > w2)
        {
               largest = w1;
        }
        else
        {
               largest = w2;
        } 
        
        for(f = 0; f <= largest ; f++)
        {
                
              if(array1[f] < array2[f])
              {
                 
                 array3[f] = array1[f]; 
                 array3[f+1] = array2[f];                     
              }
              else 
              {
                 array3[f] = array2[f];
                 array3[f+1] = array1[f];
              }
        }    
        
        
            
    
        printf("The final values are:\n");
        for(f = 0; f <= largest; f++)
        {
              printf("%d ",array3[f]); 
        }
    }

  5. #5
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    You're right the whole list will come in sorted form. You dont need to call bubblesort() again. Take two counters for the two arrays and do what you're doing in your for loop in merge() but make sure to keep a mark on the counters i.e increment the counters according to the indices of the array1 and array2. Repeat this till one of the counter reaches it's end which is the size of any of the array. After it just copy the whole array1 and/or array2 beyond array3. To print the array3 you need to run the loop till the sum of the sizes of the two arrays not till the largest of the two. I know I didn't make myself much clear but be free to ask me if you get into problem
    HOPE YOU UNDERSTAND.......

    By associating with wise people you will become wise yourself
    It's fine to celebrate success but it is more important to heed the lessons of failure
    We've got to put a lot of money into changing behavior


    PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
    IDE- Microsoft Visual Studio 2008 Express Edition

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    The problem area:
    Quote Originally Posted by key4life View Post
    Code:
              if(array1[f] < array2[f])
              {
                 
                 array3[f] = array1[f]; 
                 array3[f+1] = array2[f];                     
              }
              else 
              {
                 array3[f] = array2[f];
                 array3[f+1] = array1[f];
              }
    That code isn't really very close to something that would merge arrays

    Merging arrays involves taking an item from array1 OR an item from array2, until both have no more items. You are somehow trying to take the wrong items from both and then overwrite one of those on the next loop iteration.
    The final array always has the same number of items as the sum of the number or items in the first two arrays. You haven't so much as got that part right unfortunately.
    Last edited by iMalc; 12-04-2009 at 10:35 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"

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You have 4 apples in one bowl, sorted by size. You have 4 apples in another bowl, sorted by size. You are going to put all the apples into one bowl, sorted by size.

    How'd you do that?

    Probably grab the smallest apple from each bowl, and compare them. Then put the smallest of them, into the final bowl. Then grab the next smallest apple from the bowl that you took that smallest apple of all, from, and repeat.

    Make your program, do the same thing. Start with two smallest numbers, compare them, and put the smallest one into the final array. Then get ONE more number (the next smallest from the same array that the smallest number came from), and repeat the comparison.

  8. #8
    Registered User
    Join Date
    Nov 2009
    Posts
    13
    Well I adjusted the loop size so that it loops for the combined size of the arrays to be merged. And I did what Adak suggested, I compared the two smallest, then stored the smaller in array 3, then I compared the next smallest from the array tht had the smaller with the smallest from the array tht didnt get stored from the first comparison. Still wont work =(
    What else is wrong?

    Code:
    int merge(int array1[], int w1, int array2[], int w2)
    {
        int f,array3[20];
        
        for(f = 0; f <= (w1+w2) ; f++)
        {
                
              if(array1[f] < array2[f])
              {             
                 array3[f] = array1[f];  
              }
              
              if(array1[f+1] < array2[f])
              {
                 array3[f+1] = array1[f+1];
              }                         
                        
              
        }    
        
        
            
    
        printf("The final values are:\n");
        for(f = 0; f <= (w1+w2); f++)
        {
              printf("%d ",array3[f]); 
        }
    }

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by key4life View Post
    Well I adjusted the loop size so that it loops for the combined size of the arrays to be merged. And I did what Adak suggested, I compared the two smallest, then stored the smaller in array 3, then I compared the next smallest from the array tht had the smaller with the smallest from the array tht didnt get stored from the first comparison. Still wont work =(
    What else is wrong?

    Code:
    int merge(int array1[], int w1, int array2[], int w2)
    {
        int f,array3[20];
        
        for(f = 0; f <= (w1+w2) ; f++)
        {
              
      
              if(array1[f] < array2[f])
              {             
                 array3[f] = array1[f];  
              }
              
              if(array1[f+1] < array2[f])
              {
                 array3[f+1] = array1[f+1];
              }                         
                        
              
        }    
        
        
            
    
        printf("The final values are:\n");
        for(f = 0; f <= (w1+w2); f++)
        {
              printf("%d ",array3[f]); 
        }
    }
    You have to do two things when you make your if() comparison of apples:

    1) put the smaller apple into the merged bowl and
    2) pick up the smallest apple in the same bowl that was the source for your last smallest apple (that you put into the bowl).

    Code:
    int merge(int array1[], int w1, int array2[], int w2)
    {
        int f,array3[20];
        
        for(f = 0; f <= (w1+w2) ; f++)
        {
              
              //logic for arrays of different sizes
              if(f >= w1) {
                 array3[f] = array2[f];
                 continue;
              }
              else if(f >= w2) {
                 array3[f] = array1[f];
                 continue;
              }
      
              if(array1[f] < array2[f])
              {             
                 array3[f] = array1[f];  
                 //get your next apple from the array1 bowl, right here
    
              }
              
              if(array1[f+1] <= array2[f])      //change this to include equals (one if() has to handle them).
              {
                 array3[f+1] = array1[f+1];
                //Get your array2() apple, right now
    
              }                         
                        
              
        }    
        
        
            
    
        printf("The final values are:\n");
        for(f = 0; f <= (w1+w2); f++)
        {
              printf("%d ",array3[f]); 
        }
    }
    Edit: added some code to handle arrays of uneven sizes. This is off the cuff and not tested code.
    Last edited by Adak; 12-05-2009 at 12:33 PM.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    You can't jsut grab all items from position 'f'. That's the index of where you're putting items, not the indexes of where you're taking them from.

    Say the frst five items in array1 are all less than the first item in array2. E.g.
    Code:
    int array1[] = {1,2,4,5,7,10,13,14,18}, array2[] = {8,9,11,17,20,21};
    When you finally find the the sixth item in array1 is not less than the first item in array2, does it make sense to copy the sixth item from array2 into the output array? No, that array is only up to the first item at that point.

    You need separate index variables man!

    Adak fell into the trap of trying to modify your existing code without realising how horribly broken it was and that his modifications were in vain. You really should follow through the logic using his apples example though.
    Last edited by iMalc; 12-05-2009 at 01:10 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"

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by iMalc View Post
    You can't jsut grab all items from position 'f'. That's the index of where you're putting items, not the indexes of where you're taking them from.

    Say the frst five items in array1 are all less than the first item in array2. E.g.
    Code:
    int array1[] = {1,2,4,5,7,10,13,14,18}, array2[] = {8,9,11,17,20,21};
    When you finally find the the sixth item in array1 is not less than the first item in array2, does it make sense to copy the sixth item from array2 into the output array? No, that array is only up to the first item at that point.

    You need separate index variables man!

    Adak fell into the trap of trying to modify your existing code without realising how horribly broken it was and that his modifications were in vain. You really should follow through the logic using his apples example though.
    You are right on both accounts, iMalc!

    OK, here we go. I changed your code a lot, but tried to keep it in the same framework.

    As iMalc sagely mentioned, we need separate indexes for each of the 3 arrays.

    Edit: That was my intention, but the n1+n2 indeces, ganged up on me - so no n3.

    I use n1 for the index to the array1, and n2 for the array2 index, in the merge array function.

    I also assigned the values to the arrays, because my wrists can get too carried away with keyboarding, sometimes.

    size1 is how many numbers are in the array1 not the same thing as the sizeof(array1)
    size2 is the same thing, but for array 2.

    I changed your sorter, because it called out the wrong guy!

    Code:
    #include<stdio.h>
    #include<conio.h>
    
    void bubble_sort(int array[],int w);
    void merge(int array1[], int w1, int array2[], int w2);
    
    int main(void)
    {
        int val_1,i,x,val_2,y,z, size1, size2;
    
        int array1[10] = {4,8,1,9,6,3,2,5};
        int array2[10] = {1,5,2,9,4,3};
    
        i = 0;
        while(array1[i++]); 
        size1 = i - 1;
    
        i = 0;
        while(array2[i++]); 
        size2 = i - 1;
    
        printf("\n\nsize1: %d  size2: %d", size1, size2);
        getch();
        
        bubble_sort(array1, size1);
        bubble_sort(array2, size2);
        
        printf("\n\nThe sorted elements of Values1 are: ");
        for(i = 0; i < size1; i++)
           printf("%d",array1[i]);
            
        printf("\n");
        printf("\nThe sorted elements of Values2 are: ");
        for(i = 0; i < size2; i++)
           printf("%d",array2[i]);
            
      merge(array1,size1, array2, size2);
        
      getch();
      return 0;    
    }
    
    void bubble_sort(int array[],int w)
    {
      int c1,c2,hold;
      for (c1 = 0; c1 < w-1; c1++)
      {
        for (c2 = c1+1; c2 < w; c2++) 
        {
          if (array[c1] > array[c2])
          {
             hold = array[c1];
             array[c1] = array[c2];
             array[c2] = hold;
          }
        }
      }
    }
    void merge(int array1[], int w1, int array2[], int w2)
    {
      int f, n1, n2 ,array3[20];
        
      for(n1 = 0, n2 = 0; n1 < w1 || n2 < w2; )
      {
        //logic for the tips of arrays of different sizes
        if(n1 >= w1) {
          array3[n1+n2] = array2[n2];
          ++n2;
          continue;
        }
        else if(n2 >= w2) {
          array3[n1+n2] = array1[n1];
          ++n1;
          continue;
        }
        //end of logic for tips of arrays with different sizes
      
    
       //this if statement handles all the rest
        if(array1[n1] < array2[n2])
        {             
          array3[n1+n2] = array1[n1];  
          ++n1;
        }
        else if(array2[n2] <= array1[n1]) 
        {
           array3[n1+n2] = array2[n2];
           ++n2;
        }                         
      }    
    
      printf("\n\nThe final values are:\n");
      for(f = 0; f < (w1+w2); f++)
      {
        printf("%d ",array3[f]); 
      }
    }
    This is just slightly tested, so play around with it and see if it breaks!
    Last edited by Adak; 12-05-2009 at 05:49 PM.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    This could just be an else:
    Code:
        else if(array2[n2] <= array1[n1])
    That's a very different way of doing it than I'm used to, but it looks like it should work.

    key4life: I would actually recommend using three indexes, one for each array. Try writing it yourself, doing that. The usual method is to merge the arrays until one of them reaches its ending index, and then you perform a separate loop to copy all remaining items from the other array.
    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"

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by iMalc View Post
    This could just be an else:
    Code:
        else if(array2[n2] <= array1[n1])
    That's a very different way of doing it than I'm used to, but it looks like it should work.

    key4life: I would actually recommend using three indexes, one for each array. Try writing it yourself, doing that. The usual method is to merge the arrays until one of them reaches its ending index, and then you perform a separate loop to copy all remaining items from the other array.
    I've never coded a merge array function using a for loop. Usually use two while loops (one for the main part, and one for the longer array "leftovers").

    Looking at this, it seems inefficient to have the tip portion inside the main for loop. It would be better having it outside. Keep the loops as small and tight as possible.

    Good catch on the else if.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. merging arrays
    By acohrockz21 in forum C Programming
    Replies: 28
    Last Post: 03-09-2008, 01:28 AM
  2. Replies: 16
    Last Post: 01-01-2008, 03:07 PM
  3. Merging two arrays.
    By Roaring_Tiger in forum C Programming
    Replies: 2
    Last Post: 08-21-2004, 07:00 AM
  4. Crazy memory problem with arrays
    By fusikon in forum C++ Programming
    Replies: 9
    Last Post: 01-15-2003, 08:24 PM
  5. merging arrays using pointers help!!!
    By edshaft in forum C++ Programming
    Replies: 3
    Last Post: 12-19-2001, 06:19 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21