Thread: 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.

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.

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.

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

The problem area:

Originally Posted by key4life

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.

Originally Posted by key4life

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.

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.

Originally Posted by iMalc

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!

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.