ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
Distribution: Red Hat, Debian, now Gentoo and SUSE
Posts: 13
Rep:
Merge 2 arrays in C
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;
}
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.
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..
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);"
Distribution: Red Hat, Debian, now Gentoo and SUSE
Posts: 13
Original Poster
Rep:
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.?.?.?
Distribution: Red Hat, Debian, now Gentoo and SUSE
Posts: 13
Original Poster
Rep:
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);
}
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.