Combining multiple sorted arrays in C

Question

Trying to combine 8 pre-sorted arrays. I am new to C, but so far this is what I came up with. Needless to say, this will not work. I can’t understand why. I based it on the implementation of C ++ merging here and tried to expand it to 8 dimensions and simplify it a bit, but for some reason it tends to give me elements from the first array, followed by 34, 30, then it repeats 23 to the end . He doesn't even realize that 21 is the smallest value in the first iteration.

int test1[5] = {23, 24, 25, 33, 51}; int test2[5] = {21, 34, 44, 50, 62}; int test3[5] = {34, 36, 41, 44, 46}; int test4[5] = {30, 31, 32, 35, 40}; int test5[5] = {54, 56, 57, 58, 60}; int test6[5] = {31, 33, 36, 51, 52}; int test7[5] = {44, 46, 76, 78, 79}; int test8[5] = {23, 33, 43, 54, 63}; int output[40]; int t1, t2, t3, t4, t5, t6, t7, t8; t1 = 0; t2 = 0; t3 = 0; t4 = 0; t5 = 0; t6 = 0; t7 = 0; t8 = 0; int p = 0; int temp1; int temp2; while(p < 40) { if (t1 < 5) { temp1 = 1; temp2 = test1[t1]; }else if (test2[t2] <= test1[t1] && t2 < 5) { temp1 = 2; temp2 = test2[t2]; }else if (test3[t3] <= temp2 && t3 < 5) { temp1 = 3; temp2 = test3[t3]; }else if (test4[t4] <= temp2 && t4 < 5) { temp1 = 4; temp2 = test4[t4]; }else if (test5[t5] <= temp2 && t5 < 5) { temp1 = 5; temp2 = test5[t5]; }else if (test6[t6] <= temp2 && t6 < 5) { temp1 = 6; temp2 = test6[t6]; }else if (test7[t7] <= temp2 && t7 < 5) { temp1 = 7; temp2 = test7[t7]; }else if (test8[t8] <= temp2 && t8 < 5) { temp1 = 8; temp2 = test8[t8]; } switch(temp1) { case 1: output[p] = temp2; t1++; break; case 2: output[p] = temp2; t2++; break; case 3: output[p] = temp2; t3++; break; case 4: output[p] = temp2; t4++; break; case 5: output[p] = temp2; t5++; break; case 6: output[p] = temp2; t6++; break; case 7: output[p] = temp2; t7++; break; case 8: output[p] = temp2; t8++; break; } printf("%d\n", output[p]); p++; } 

Thanks for any help you can offer.

Answer 1

This is why you get the first 5 elements of the first array:

 if (t1 < 5) { temp1 = 1; temp2 = test1[t1]; 

Your code specifically guarantees that the first 5 elements of the first array will be selected first. You should compare the value of the next element in test1 with the next element in other arrays, and not just blindly select it. Also, your use of if .. then..sese if .. else if ... is wrong. If you find that the next array 2 is smaller than the next element of array 1, you still need to check if arrays 3, 4, and 5 are smaller.

Try to structure your code as follows

 int temp1 = -1; if (t1 < 5) { temp1=1; temp2=test1[t1]; } if ((t2 < 5) && ((temp1 < 0) || (test2[t2] < temp2))) { temp1=2; temp2=test2[t2]; } if (t3... 

followed by an existing switch statement.

Answer 2

hatchet already told you what went wrong if ... else if ... will execute the second block if and only if the second condition is valid and the first is invalid.

However, I believe that your switch() and if-else based program is a bit complicated to extend, since you need to change all fixed fields and values ​​to sort another set of arrays. The following program / function provides the same as yours, but it is easier to expand. It uses an extra cursor array to save the current position (similar to your t1 , t2 , ...) ( Perfect demo ).

 #include <stdio.h> #include <stdlib.h> #include <limits.h> int multimerge( int * const * const arrays, // arrays holding the data int const * const arraysizes, // sizes of the arrays in `arrays` int number_of_arrays, // number of arrays int * const output // pointer to output buffer ){ int i = 0; // output cursor int j = 0; // index for minimum search int min; // minimum in this iteration int minposition; // position of the minimum // cursor for the arrays int * cursor = calloc(number_of_arrays,sizeof(int)); if(cursor == NULL) return -1; while(1){ min = INT_MAX; minposition = -1; // invalid position // Go through the current positions and get the minimum for(j = 0; j < number_of_arrays; ++j){ if(cursor[j] < arraysizes[j] && // ensure that the cursor is still valid arrays[j][cursor[j]] < min){ // the element is smaller min = arrays[j][cursor[j]]; // save the minimum ... minposition = j; // ... and its position } } // if there is no minimum, then the position will be invalid if(minposition == -1) break; // update the output and the specific cursor output[i++] = min; cursor[minposition]++; } free(cursor); return 0; } int main() { int i = 0; int test1[5] = {23, 24, 25, 33, 51}; int test2[5] = {21, 34, 44, 50, 62}; int test3[5] = {34, 36, 41, 44, 46}; int test4[5] = {30, 31, 32, 35, 40}; int test5[5] = {54, 56, 57, 58, 60}; int test6[5] = {31, 33, 36, 51, 52}; int test7[5] = {44, 46, 76, 78, 79}; int test8[5] = {23, 33, 43, 54, 63}; int *test[] = {test1, test2, test3, test4, test5, test6, test7, test8}; int testsizes[] = {5,5,5,5,5,5,5,5}; int output[40]; multimerge(test,testsizes,8,output); while(i < 30){ printf("%i\n",output[i++]); } return 0; } 

Answer 3

What I did in the (remote) past is to sort the first element of each list with sorting tags, select the first in the sorted list to add to the combined list, and then replace the moved element with the next from its list (that’s why you need a tag type for some taste, to determine where the replacement should come from) and re-sort. Sorting the head elements can be with bubble sorting, since after the initial sorting you only need one pass to properly reorder things after removal / replacement.