3

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.

8
  • Why not just dump them into one array (sorting as you go), and then sort the other array in from there?
    – pickypg
    Commented Sep 23, 2012 at 3:58
  • Could you add the code that declares/allocates combinedArray?
    – jogojapan
    Commented Sep 23, 2012 at 4:00
  • You mean making a new array, dumping all the elements into that, and resorting via my current sorting method for the sortedArrays? This is a homework assignment and it was explicitly stated that we couldn't do that.
    – Havegooda
    Commented Sep 23, 2012 at 4:01
  • One general problem with this algorithm is that in each step you decide which of two elements at position j is larger and then put them both to the results array. What if one of the elements at j+1 is actually smaller than the larger element of step j?
    – jogojapan
    Commented Sep 23, 2012 at 4:02
  • I'll give you a hint for an alternative solution: it requires one while loop and two index variables (one per array) and it's over once both indices reach the end of their respective arrays.
    – Borgleader
    Commented Sep 23, 2012 at 4:03

6 Answers 6

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++;

          }
3
  • Thank you! I found that algorithm here and applied it to my code before I refreshed this question and saw you answered it! Thank you so much, would have been very helpful in the event that I didn't find it on my own. Thanks to all the others that had suggestions for my code/techniques. As you can probably guess, I'm rather rusty.
    – Havegooda
    Commented Sep 23, 2012 at 4:45
  • Working output: Combined Array contents: 11 22 33 44 54 55 66 77 88
    – Havegooda
    Commented Sep 23, 2012 at 4:48
  • 1
    This does not work your last two while loops cause infinite loops Commented Sep 23, 2012 at 7:15
3

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.

3
  • Actually you need three independent counters. Two for the two source arrays (or rather one per source array) and one for the destination array.
    – bitmask
    Commented Sep 23, 2012 at 4:37
  • @bitmask You could determine the one for the destination array as j1+j2 I suppose.
    – jogojapan
    Commented Sep 23, 2012 at 4:38
  • Ah yes, you're right. Didn't think of that. Still, if you generalise the problem to an arbitrary number of input arrays, things would get messy.
    – bitmask
    Commented Sep 23, 2012 at 4:39
1

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.

1

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;
2
  • The i <= combinedSize condition in the first for-loop means you are running beyond the end of combinedArray. Also, the space allocated for combinedArray isn't freed, at least not within this code fragment.
    – jogojapan
    Commented Sep 23, 2012 at 7:44
  • Oh and in the first if clause, second sub-case, you want to assign sortedArray2[k], not sortedArray2[j].
    – jogojapan
    Commented Sep 23, 2012 at 7:45
0

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.

2
  • I just made that change (nice catch!), but I'm still getting the same output.
    – Havegooda
    Commented Sep 23, 2012 at 4:11
  • I used j<=5 because while I wanted i to increment all the way to combinedSize, I didn't want j to increment past 5 as the sortedArrays had nothing beyond index 4. I see where I messed up with <= and I've made the change to <, but I still get bad output. 88 99 88 99 88 99 88 99 88 99
    – Havegooda
    Commented Sep 23, 2012 at 4:20
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.