Merge 2 arrays in C

linux_GNUbie · 12-11-2003, 01:28 AM

Hello all!
I'm having problems merging two arrays in C. I'm working on a problem from one
of my books that deals with arrays as function arguments. The problem deals with
two integer arrays representing weights. I've solved much of the problem (I think!),
even bubble-sorting the two arrays. However, I can't find any good references for
writing functions that specifically merge two integer arrays. And my book doesn't
explain this very well at all. Could someone here offer any suggestions/hints?
Sorry if the code is long!
As you can see, I've spent some time on this already.

Code:

#include <stdio.h>

/* max size of each array to be merged */
#define MAXSIZE 10

int Merge(int array1[], int sizeofArray1,
          int array2[], int sizeofArray2,
          int mergedArray[], int sizeofMergedArray);

void SortArray(int array[], int sizeofArray);

int main() {

   int i,
      weights1[MAXSIZE],
      sizeofWeights1,
      weights2[MAXSIZE],
      sizeofWeights2,
      mergedWeights[2 * MAXSIZE],
      sizeofMergedWeights,
      mergeResult;

   /* input size of first table of animal weights; check its validity */
   scanf("%d", &sizeofWeights1);
   if((sizeofWeights1 < 1) || (sizeofWeights1 > MAXSIZE)) {
      printf("Sorry: size of Weights 1 must be 1 - %d\n Bye\n", MAXSIZE);
      return(1);
   }

   /* input (and echo to output) first set of weights */
   printf("\n\n   FIRST ARRAY (BEFORE SORTING)\n");

   /* input and echo first table */
   for(i = 0; i < sizeofWeights1; i++) {
      scanf("%d", &weights1[i]);
      printf("Weights1[%2d] is %d\n", i, weights1[i]);
   }

   /* sort first set of weights */
   SortArray(weights1, sizeofWeights1);

   /* output first set of weights after sorting */
   printf("\n\n   FIRST ARRAY (AFTER SORTING)\n");

   /* input and echo first table */
   for(i = 0; i < sizeofWeights1; i++) {
      printf("Weights1[%2d] is %d\n", i, weights1[i]);
   }

   /* input size of second table of animal weights; check its validity */
   scanf("%d", &sizeofWeights2);
   if((sizeofWeights2 < 1) || (sizeofWeights2 > MAXSIZE)) {
      printf("Sorry: size of Weights 2 must be 1 - %d\n Bye\n", MAXSIZE);
      return(2);
   }

   printf("\n\n   SECOND ARRAY BEFORE SORTING\n");

   /* input second table of weights */
   for(i = 0; i < sizeofWeights2; i++) {
      scanf("%d", &weights2[i]);
      printf("Weights2[%2d] is %d\n", i, weights2[i]);
   }

   /* sort the second array of weights */
   SortArray(weights2, sizeofWeights2);

   printf("\n\n   SECOND ARRAY (AFTER SORTING)\n");

   /* input and echo first table */
	 for(i = 0; i < sizeofWeights2; i++) {
      printf("Weights2[%2d] is %d\n", i, weights2[i]);
   }

   sizeofMergedWeights = sizeofWeights1 + sizeofWeights2;

   /* merge the contents of two weight tables */
   mergeResult = Merge(weights1, sizeofWeights1,
                    weights2, sizeofWeights2,
                    mergedWeights, sizeofMergedWeights);

   /* output results of the merge */
   switch(mergeResult) {
      case 0:
         printf("\n\n   MERGED ARRAY\n");
         for (i = 0; i < sizeofMergedWeights; i++)
            printf("MergedWeights[%2d] is %d\n", i, mergedWeights[i]);
         break;
      case 1:
         printf("Main: merge failed; Weights1 not in ascending order.\n");
         return(3);
         break;
      case 2:
         printf("Main: merge failed; Weights2 not in ascending order.\n");
         return(3);
         break;
			default:
         printf("Main: merge failed; merge returned unknown error.\n");
         return(4);
         break;
   }

   return (0);

}

void SortArray(int array[], int sizeofArray) {

   void Swap(int *, int *);

   int i, j;

   /* this sorts the array into ascending order */
   for(i = 0; i < sizeofArray; i++) {
      for(j = 1; j < (sizeofArray-i); j++) {
         if(array[j-1] > array[j])
            Swap(&array[j-1], &array[j]);
      }
   }
}

int Merge(int array1[], int sizeofArray1,
          int array2[], int sizeofArray2,
          int mergedArray[], int sizeofMergedArray) {

   int x;

   /* test if array1 is in ascending order; if not, stop processing and return 1 */
   for(x = 0; x < sizeofArray1; x++) {
      if(array1[x] > array1[x + 1]);
      return (1);
   }

   /* test if array2 is in ascending order; if not, stop processing and return 2 */
   for(x = 0; x < sizeofArray2; x++) {
      if(array2[x] > array2[x + 1]);
      return (2);
   }

   /* merge array1 and array2, return 0 */
   /* this is where I'm stuck                    */

}

void Swap(int *onePtr, int *twoPtr) {

   int hold = *onePtr;
   *onePtr = *twoPtr;
   *twoPtr = hold;
	 
}

TIA to all!
This is FUN!

Chris//CMS

Nis · 12-11-2003, 01:39 AM

Probably your best way to go about this is to take the first element of each array and compare them. Let's say if array1[0] < array2[0], then mergedArray[0] = array1[0] else mergedArray[0] = array2[0]. Then you'll want to increment the index of whichever array had its element assigned to mergedArray. Then continue comparing array1[i] to array2[j]. As an example,after sorting, array1 = {1, 3, 7, 8} and array2 = {2, 4, 5, 9}. int i = 0, j = 0. array1[i] < array2[j] so mergedArray[0] = array1[i]. i++. Do it again. array1[i] > array2[j] so mergedArray[1] = array2[j]. j++. Do it again and so on. After three run throughs mergedArray would look like {1, 2, 3} and i = 2 and j = 1. If you get to the end of array1 or array2 you can be sure that everything in the other array comes after the last element in the finished array. I'm sure you can write the loop to do all this. The best part is that this only takes length of array1 + length of array2 comparisons in a worst case. Hope this helps.

worldmagic · 12-11-2003, 03:02 AM

I havent reed all your code, and reading the response I guess Im abit off giving this hint.. but, it depends on what you want to do (sorry for being that lazy) =) .. To merge anything, thats an array or something.. you can use memcpy, to sort it (slow) qsort can be used..

void *memcpy(void *dest, const void *src, size_t n);
void qsort(void *base, size_t nmemb, size_t size,
int(*compar)(const void *, const void *));

example:
[code]
#define SIZE 10;
int array1[SIZE];
int array2[SIZE];
int arrayFinal[SIZE*2];

int MyCompare(const void* lv, const void* rv) {

}

main() {

FillArraysWithValues(array1, array2);

memcpy(arrayFinal, array1, SIZE);
memcpy(&arrayFinal[SIZE], array2, SIZE);
qsort(arrayFinal, SIZE*2, sizeof(int), MyCompare);
}

worldmagic · 12-11-2003, 03:04 AM

mm.. Well I dont know this about the submitting things in Mozilla.. grr..anyway.. the MyCompare should ofcourse dereferend the pointers cast the result and "return (intLv < intRv);"

linux_GNUbie · 12-11-2003, 04:32 PM

Thanks to all for their suggestions, especially you Nis. I think I worked out the merge
with the two arrays using Nis's logic. I'm not far enough along to use memcpy (thanks
worldmagic, I'll do some more reading!). Although, I still have an error in my logic--I
think the error is in my Merge function where I test both arrays to see if they are in fact
sorted correctly; that is, sorted in ascending order. The program compiles fine ( gcc
array_sort_merge.c ). When I run the program with test data ( ./a.out < test.data1 ) I
get correct results from the sort function but the error message "Main: merge failed;
Weights1 not in ascending order." prints. This of course, is from my switch statement,
case 1. I can't seem to find the error though. The arrays are sorted correctly yet I can't
get past the beginning of my Merge function.?.?.?

test.data1

Code:

8
21 15 16 18 20 21 22 14
5
14 17 26 26 20

Again, TIA for all the help.

Chris//CMS

linux_GNUbie · 12-11-2003, 04:50 PM

Well, my logic is definately wrong! I changed the syntax of my Merge function
to print a message so I could see how far the program progressed before it
found an error. I also changed the test from 'greater than' to 'less than' OR
'equal to' to account for duplicate entries in the two arrays--I forgot, duplicate
entries could exist in the two arrays so 'less than' and/or 'greater than' wouldn't
test correctly.

Code:

int Merge(int array1[], int sizeofArray1,
          int array2[], int sizeofArray2,
          int mergedArray[], int sizeofMergedArray) {

   int x, y;

   /* test if array1 is in ascending order; if not, stop processing and return 1 */
   for(x = 0; x < sizeofArray1; x++) {
      if(array1[x] <= array1[x + 1])
         printf("   Sort test 1 is correct...Proceeding!\n");
      else
         return (1);
   }

   /* test if array2 is in ascending order; if not, stop processing and return 2 */
   for(y = 0; y < sizeofArray2; y++) {
      if(array2[y] <= array2[y + 1])
         printf("   Sort test 2 is correct...Proceeding!\n");
      else
         return (2);
   }

   /* merge array1 and array2, return 0 */
   x = 0, y = 0;
   while(x < sizeofArray1 || y < sizeofArray2) {
      if(array1[x] < array2[y]) {
         mergedArray[x] = array1[x];
         x++;
      }
      else {
         mergedArray[x] = array2[y];
         y++;
      }
   }

   return (0);

}

TIA

Chris//CMS

Nis · 12-11-2003, 05:28 PM

Glad it all worked out for you!