Sorting two arrays into a combined array

Question

I haven't done any programming classes for a few years, so please forgive any beginner mistakes/methods of doing something. I'd love suggestions for the future. With the code below, I'm trying to check the values of two arrays (sorted already) and put them into a combined array. My solution, however inefficient/sloppy, is to use a for loop to compare the contents of each array's index at j, then assign the lower value to index i of the combinedArray and the higher value to index i+1. I increment i by 2 to avoid overwriting the previous loop's indexes.

int sortedArray1 [5] = {11, 33, 55, 77, 99};
int sortedArray2 [5] = {22, 44, 66, 88, 00};
combinedSize = 10;
int *combinedArray;
combinedArray = new int[combinedSize];
    for(int i = 0; i <= combinedSize; i+=2)
{
    for(int j = 0; j <= 5; j++)
    {
        if(sortedArray1[j] < sortedArray2[j])
        {
            combinedArray[i] = sortedArray1[j];
            combinedArray[i+1] = sortedArray2[j];
        }
        else if(sortedArray1[j] > sortedArray2[j])
        {
            combinedArray[i] = sortedArray2[j];
            combinedArray[i+1] = sortedArray1[j];
        }
        else if(sortedArray1[j] = sortedArray2[j])
        {
            combinedArray[i] = sortedArray1[j];
            combinedArray[i+1] = sortedArray2[j];
        }
    }
}

for(int i = 0; i < combinedSize; i++)
{
    cout << combinedArray[i];
    cout << " ";
}

And my result is this

Sorted Array 1 contents: 11 33 55 77 99
Sorted Array 2 contents: 0 22 44 66 88
5 77 5 77 5 77 5 77 5 77 Press any key to continue . . .

In my inexperienced mind, the implementation of the sorting looks good, so I'm not sure why I'm getting this bad output. Advice would be fantastic.

Answer 1

Slightly different approach, which is IMHO a bit cleaner:

//A is the first array, m its length
//B is the second array, n its length
printSortedAndMerged(int A[], int m, int B[], int n){
    int c[n+m];
    int i=0, j=0;

    for(int k=0; k < n+m; k++){

        if(i < m && j < n){
            if(A[i] < B[j]){
                c[k] = A[i];
                i++;
            }
            else{
                c[k] = B[j];
                j++;
            }
            continue; //jump to next iteration
        }

        if(i < m){ // && ~(j < n)
        //we already completely traversed B[]
            c[k] = A[i];
            i++;
            continue;
        }

        if(j < n){ // %% ~(i < m)
        //we already completely traversed A[]
            c[k] = B[j];
            j++;
            continue;
        }

        //we should never reach this
        cout << "Wow, something wrong happened!" << endl;
}//for

for(int i=0; i<n+m; i++){
    cout << c[i] << endl;
}
}

Hope it helps.

Answer 2

So, I modified your code to make it work. Actually it would be good idea to have two pointer/index for two sorted arrays. So that you can update your corresponding pointer after adding it to your combinedArray. Let me know if you don't understand any part of this code. Thanks.

    int sortedArray1 [5] = {11, 33, 55, 77, 99};
    int sortedArray2 [5] = {0, 22, 44, 66, 88}; 
    int combinedSize = 10;
    int *combinedArray;
    combinedArray = new int[combinedSize];
    int j = 0;
    int k = 0;
    for(int i = 0; i < combinedSize; i++)
    {
            if (j < 5 && k < 5) {
                    if (sortedArray1[j] < sortedArray2[k]) {
                            combinedArray[i] = sortedArray1[j];
                            j++;
                    } else {                  
                            combinedArray[i] = sortedArray2[k];
                            k++;
                    }                         
            } 
            else if (j < 5) {
                    combinedArray[i] = sortedArray1[j];
                    j++;
            }                         
            else {
                    combinedArray[i] = sortedArray2[k];
                    k++;
            }                         
    }

    for(int i = 0; i < combinedSize; i++)
    {
        cout << combinedArray[i];
        cout << " ";
    }
    cout<<endl;

Answer 3

what about this:

int i=0,j=0,k=0;
while(i<5 && j<5)
     {
        if(sortedArray1[i] < sortedArray2[j])
         {
           combinedArray[k]=sortedArray1[i];
            i++;
          }
       else
         {
           combinedArray[k]=sortedArray2[j];
           j++;
          }
      k++;
     }
   while(i<5)
     {
           combinedArray[k]=sortedArray1[i];
           i++;k++;
          }
   while(j<5)
     {
           combinedArray[k]=sortedArray2[j];
           j++;  k++;

          }

Answer 4

Firstly, there are some immediate problems with how you use C++:

• You use = instead of == for equality check (hence causing undesired value assignments and the if-condition to return true when it shouldn't);
• Your outer loops upper boundary is defined as i <= 10, while the correct boundary check would be i < 10;
• You have a memory leak at the end of the function because you fail to de-allocate memory. You need a delete [] combinedArray at the end.

Secondly, your outer loop iterates through all values of the destination array, and in each step uses an inner loop to iterate through all values of the source arrays. That is not what you want. What you want is one loop counting from j=0 to j<5 and iterating through the source arrays. The positions in the destination array are then determined as 2*j and 2*j+1, and there is no need for an inner loop.

Thirdly, as explained in the comment, a correct implementation of sorted-list merge needs two independent counters j1 and j2. However, your current input is hardwired into the code, and if you replace 00 with 100, your current algorithm (after the corrections above are made) will actually work for the given input.

Finally, but less importantly, I wonder why your destination array is allocated on the heap using new. As long as you are dealing with small arrays, you may allocate it on the stack just like the source arrays. If, however, you allocate it on the heap, better use a std::unique_ptr<>, possibly combined with std::array<>. You'll get de-allocation for free then without having to think of putting a delete [] statement at the end of the function.

Answer 5

Before even looking at the implementation, check the algorithm and write it down with pen and paper. The first thing that pops is that you are assuming that the first two elements in the result will come one from each source array. That need not be the case, consider two arrays where all elements in one are smaller than all elements in the other and the expected result:

int a[] = { 1, 2, 3 };
int b[] = { 4, 5, 6 };

If you want the result sorted, then the first three elements come all from the first array. With that in mind think on what you really know about the data. In particular, both arrays are sorted, which means that the first elements will be smaller than the rest of the elements in the respective array. The implication of this is that the smaller element is the smaller of the heads. By putting that element into the result you have reduced the problem to a smaller set. You have a' = { 2, 3 }, b = { 4, 5, 6 } and res = { 1 } and a new problem that is finding the second element of res knowing that a' and b are sorted.

Figure out in paper what you need to do, then it should be straight forward to map that to code.

Answer 6

The else if(sortedArray1[j] = sortedArray2[j]), did you mean else if(sortedArray1[j] == sortedArray2[j])?

The former one will assign the value of sortedArray2[j] to sortedArray1[j] -- and that's the reason that why you get 5 77 5 77...

But where's the 5 come from? There's no 5 in either sortedArray, yet I find for(int j = 0; j <= 5; j++) must be something wrong. The highest index of a size N array is N-1 rather than N in C/C++(but not in Basic).. so use j<5 as the condition, or you may fall into some situation which is hard to explain or predict..

After all, there's problem in your algorithm itself, every time the outer loop loops, it will at last compare the last elements in the two arrays, which makes the output to repeat two numbers.

So you need to correct your algorithm too, see Merge Sort.