Thread: Problem with my c++ program

My assignment was to merge 2 arrays and then sort it into ascending order using bubble sort, insertion sort, or selection sort. (I chose insertion sort) My program does do that, however, there's a lot of unnecessary text along with it. It also prints the answer 6 times instead of just once. Here's my code along with the output:

Code:

#include <iostream>#define size (sizeof(merge)/sizeof(merge[0]))
using namespace std;


int insertion_sort(int*, int);


int main()
{
  int a1[10], a2[10], merge[20], size1, size2, merged, i, j, k;
  cout<<"Enter the number of elements in the first array:";
  cin>>size1;
  
  cout<<"Enter "<<size1<<" numbers into the first array:";
  
  for(i=0;i<size1;i++)
  {
    cin>>a1[i];
  }
  
  cout<<"\nEnter the number of elements in the second array:";
  cin>>size2;


  cout<<"Enter "<<size2<<" numbers into the second array:";


  for(i=0;i<size2;i++)
  {
    cin>>a2[i];
  }
  
  for(i=0;i<size1;i++)
  {
    merge[i]=a1[i];
  }
  
  for(i=0;i<size2;i++)
  {
    merge[i]=a2[i];
  }
  merged=size2+size1;
  
  for(i=0, k=size1; k<merged && i<size2; i++, k++)
  {
    merge[k]=a1[i];
  }
  
  cout<<"The array after merging is:";
  for(i=0;i<merged;i++)
  {
    cout<<merge[i]<<" ";
  }
  cout<<endl;
  insertion_sort(merge, size);
  
  return 0;
}


int insertion_sort(int b[], int length){


    int top;
    int item;
    int i;
    for (top=1; top<length; top++){
        item=b[top];
        i=top;
        while(i>0 &&item<b[i-1]){
            b[i]=b[i-1];
            i--;


        }
        b[i]=item;
        for (i=0; i<length; i++)
        {cout<<b[i]<<" ";}
        cout<<endl;
    }
}

Enter the number of elements in the first array: 5
Enter 5 numbers into the first array: 5 3 4 2 1

Enter the number of elements in the second array: 5
Enter 5 numbers into the second array: 10 8 6 7 9
The array after merging is:10 8 6 7 9 5 3 4 2 1
8 10 6 7 9 5 3 4 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
6 8 10 7 9 5 3 4 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
6 7 8 10 9 5 3 4 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
6 7 8 9 10 5 3 4 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
5 6 7 8 9 10 3 4 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
3 5 6 7 8 9 10 4 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
3 4 5 6 7 8 9 10 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
2 3 4 5 6 7 8 9 10 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
1 2 3 4 5 6 7 8 9 10 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
1 2 3 4 5 6 7 8 9 10 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
0 1 2 3 4 5 6 7 8 9 10 4196208 6299744 0 -120706119 32757 1 0 -150142976 32764
0 1 2 3 4 5 6 7 8 9 10 4196208 6299744 0 -120706119 32757 1 0 -150142976 32764
0 0 1 2 3 4 5 6 7 8 9 10 4196208 6299744 -120706119 32757 1 0 -150142976 32764
-120706119 0 0 1 2 3 4 5 6 7 8 9 10 4196208 6299744 32757 1 0 -150142976 32764
-120706119 0 0 1 2 3 4 5 6 7 8 9 10 32757 4196208 6299744 1 0 -150142976 32764
-120706119 0 0 1 1 2 3 4 5 6 7 8 9 10 32757 4196208 6299744 0 -150142976 32764
-120706119 0 0 0 1 1 2 3 4 5 6 7 8 9 10 32757 4196208 6299744 -150142976 32764
-150142976 -120706119 0 0 0 1 1 2 3 4 5 6 7 8 9 10 32757 4196208 6299744 32764
-150142976 -120706119 0 0 0 1 1 2 3 4 5 6 7 8 9 10 32757 32764 4196208 6299744

What exactly is the "unnecessary text"? Remember, we don't know your requirements unless you state them, so to me it could be that all text save the first (before sorting) and last (after sorting) is unnecessary; but to another person it could look like everything you have shown is in fact necessary.

What my teacher wanted us to do was to have 2 arrays where the user enters how many elements (up to 10) they want in the array. After that, we're supposed to merge the 2 arrays together and sort the new merged array in ascending order using either bubble sort, insertion sort, or selection sort. I chose to use insertion sort. The unnecessary text that I was talking about is all the random numbers that are appearing with each iteration of the insertion sort.

Ex: (the numbers in red text is what the unnecessary text is and the green is the sorted answer printed out 10 times and the blue text​ is where the answer should've stopped at )​

Enter the number of elements in the first array: 5
Enter 5 numbers into the first array: 5 3 4 2 1

Enter the number of elements in the second array: 5
Enter 5 numbers into the second array: 10 8 6 7 9
The array after merging is: 10 8 6 7 9 5 3 4 2 1

8 10 6 7 9 5 3 4 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
6 8 10 7 9 5 3 4 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
6 7 8 10 9 5 3 4 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
6 7 8 9 10 5 3 4 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
5 6 7 8 9 10 3 4 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
3 5 6 7 8 9 10 4 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
3 4 5 6 7 8 9 10 2 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
2 3 4 5 6 7 8 9 10 1 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
1 2 3 4 5 6 7 8 9 10 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
1 2 3 4 5 6 7 8 9 10 4196208 0 6299744 0 -120706119 32757 1 0 -150142976 32764
01 2 3 4 5 6 7 8 9 104196208 6299744 0 -120706119 32757 1 0 -150142976 32764
01 2 3 4 5 6 7 8 9 104196208 6299744 0 -120706119 32757 1 0 -150142976 32764
0 01 2 3 4 5 6 7 8 9 104196208 6299744 -120706119 32757 1 0 -150142976 32764
-120706119 0 01 2 3 4 5 6 7 8 9 104196208 6299744 32757 1 0 -150142976 32764
-120706119 0 01 2 3 4 5 6 7 8 9 1032757 4196208 6299744 1 0 -150142976 32764
-120706119 0 0 11 2 3 4 5 6 7 8 9 1032757 4196208 6299744 0 -150142976 32764
-120706119 0 0 0 11 2 3 4 5 6 7 8 9 1032757 4196208 6299744 -150142976 32764
-150142976 -120706119 0 0 0 11 2 3 4 5 6 7 8 9 1032757 4196208 6299744 32764
-150142976 -120706119 0 0 0 11 2 3 4 5 6 7 8 9 1032757 32764 4196208 6299744

Code:

int a1[10], a2[10], merge[20],

what if's, what if you got an array[10] but only using 3 elements, what happens to the rest of them?

10 + 10 = 20
5 + 5 = 10
20 - 10 = 10
count the red, what you got left over?

Code:

int * array;
cout << " what size? " <<endl;
cin >> size1 ;
array = new int[size1];

If I were you, I would write two functions:

Code:

void insertion_sort(int b[], int length);
int merge_arrays(int result[], int a1[], int a2[], int size1, int size2);

You have already written insertion_sort, except that you declared it as returning int when you don't actually return anything, hence its return type should have been void. merge_arrays would "merge" the content of a1 and a2 (i.e., the elements in use for each array, the number of which is denoted by size1 and size2 respectively) such that the elements of result would be a copy of the elements of a1 followed by a copy of the elements of a2, i.e., a2 appended to the back of a1. merge_arrays would return the number of elements in use for result. (Note that this isn't typically what is meant by "merge": a "merge" usually means combining sorted sequences such that the result is a sorted sequence. If you really wanted to perform a merge, you should sort a1 and a2, and then merge, but it appears that this is not the algorithm you were asked to implement.)

I suggest that you hold off from userxbw's suggestion of using new[] for now. Yes, it is a solution that can be free from the constraints of a too low or an excessively high bound on the number of elements, but if so you should be using std::vector<int> instead.

This way, you can keep to your original declaration of a1 and a2 having 10 elements, and the result array having 20 elements, and also benefit from having functions that do one thing and do it well. The problem with your original code lies in this snippet:

Code:

for(i=0;i<size2;i++)
{
    merge[i]=a2[i];
}

Notice that instead of appending to the result, you overwrite what was previously written to the result from a1.

Additionally, I would write another function to print the elements of an array:

Code:

void print_array(int a[], int length);

This way, instead of repeating the loop when you want to print an array, you just call this function with the appropriate arguments. I also think insertion_sort should not print the array; you probably want to print the array once after calling insertion_sort.

something like this

Code:

#include <iostream>
#include <new>

int main()
{ 
    int * arr, size1, n;

    std::cout<< "how many?"<<std::endl;
    std::cin>>size1;
    arr = new (std::nothrow) int[size1];
   
    std::cout << size1 << std::endl;
   
    if ( arr == nullptr)
         std::cout << "Error: memory could not be allocated";
    else
     for (n=0; n<size1; n++)
        arr[n] = n+1;
   
    std::cout << "You get what you ask for: ";
    for (n=0; n<size1; n++)
        std::cout << arr[n] << ", ";
        
    delete[] arr;
    printf("\n");

return 0;
}

output

Code:

  [userx@void frist-one]$ ./a.out
how many?
30
30
You get what you ask for: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,

Dynamic memory - C++ Tutorials

Originally Posted by userxbw

something like this

(...)

Dynamic memory - C++ Tutorials

That won't help. You identified the problem correctly, but on its own dynamic memory allocation does not solve this problem: if you dynamically allocate 20 elements, use 10 because on the second loop you overwrite the 10 from the first sequence with 10 from the second sequence, and then treat it as if you're using 20 elements, you still have the same problem. The solution is to append correctly for the "merge". Dynamic memory allocation solves a different problem, i.e., the problem of having to decide how big the arrays should be in advance.

EDIT:
Eh, and it would be advisable not to use nothrow new unless you have special considerations. Note that if we do assume that nothrow new returns a null pointer, your code has a bug: you potentially allow for the dereferencing of a null pointer. Consider the critical part of your code rewritten to use braces even when unnecessary:

Code:

arr = new (std::nothrow) int[size1];

std::cout << size1 << std::endl;

if (arr == nullptr)
{
    std::cout << "Error: memory could not be allocated";
}
else
{
    for (n=0; n<size1; n++)
    {
        arr[n] = n+1;
    }
}

std::cout << "You get what you ask for: ";
for (n=0; n<size1; n++)
{
    std::cout << arr[n] << ", ";
}
delete[] arr;

As you can see, you access arr[n] even if arr == nullptr. If you used normal new instead, this could have been avoided. But then you might as well use std::vector<int>.

Originally Posted by laserlight

That won't help. You identified the problem correctly, but on its own dynamic memory allocation does not solve this problem: if you dynamically allocate 20 elements, use 10 because on the second loop you overwrite the 10 from the first sequence with 10 from the second sequence, and then treat it as if you're using 20 elements, you still have the same problem. The solution is to append correctly for the "merge". Dynamic memory allocation solves a different problem, i.e., the problem of having to decide how big the arrays should be in advance.

how about something like this?

Code:

#include <iostream>
#include <new>

void insertion_sort(int b[], int length)
{
    
    
       int top;
       int item;
       int i;

       for (top=1; top<length; top++){
           item=b[top];
           i=top;
           while(i>0 &&item<b[i-1]){
               b[i]=b[i-1];
               i--;
    
    
           }
           b[i]=item;
           for (i=0; i<length; i++)
           { std::cout<<b[i]<<" "; }
            
           std::cout<<std::endl;
       }
       
   }

   int * murge_array( int a1[], int a2[], int size1, int size2)
   {
       int * merge;
       int i,k;
       merge = new (std::nothrow) int [size1+size2];

    if ( merge == nullptr)
        std::cout << " cannot get memory" << std::endl;
    
        //checks to see if I got good
        //data in
        for (i = 0; i < size1; i++)
            std::cout<< a1[i];
            std::cout<<std::endl;
        for (i = 0; i < size2; i++)
            std::cout << a2[i];
            std::cout<<std::endl;

    for(i=0;i<size1;i++)
    {
      merge[i]=a1[i];
    }
     
    for(i=0;i<size2;i++)
    {
      merge[i]=a2[i];
    }
   int merged=size2+size1;
     
    for(i=0, k=size1; k<merged && i<size2; i++, k++)
    {
      merge[k]=a1[i];
    }
  return merge;
   }


int main()
{ 
    int * arr1;
    int * arr2;
    int size1,size2,  n,i;
    int * sendArr;

    std::cout<< "how many?"<<std::endl;
    std::cin>>size1;
    arr1 = new (std::nothrow) int[size1];
    
    if ( arr1 == nullptr)
         std::cout << "Error: memory could not be allocated";
    else
    {
        for (n=0; n<size1; n++)
        {
            std::cout << "1: Enter number: ";
            std::cin >> arr1[n];
        }
    }
    std::cout<< "2: how many?"<<std::endl;
    std::cin>>size2;
    arr2 = new (std::nothrow) int[size1];
    
    if ( arr2 == nullptr)
         std::cout << "Error: memory could not be allocated";
    else
    {
        for (n=0; n<size2; n++)
        {

            std::cout << " 2: Enter number: ";
            std::cin >> arr2[n];
        }
    }

 
    sendArr = new (std::nothrow) int[size1+size2];
    sendArr = murge_array(arr1,arr2,size1,size2);
    insertion_sort(sendArr, (size1+size2));

   

return 0;
}

PS I forget to free the memory force of rabbit, new to C++

as far as what to be in advance if that it what he has to do then he has to put a if statement in there to stop them from going over the limit, and still prevent blank elements that give crap data back. a dynamic approach is the logical way to go when one does not know what size he needs before hand. especially in an array.

or keep the values inputted then use them so he does not over shoot the arrays elements that have good data in them, my option of course.

there is a bug in his code, could be me I did it is a hurry

Code:

[userx@void frist-one]$ ./a.out
how many?
3
1: Enter number: 1
1: Enter number: 2
1: Enter number: 3
2: how many?
4
 2: Enter number: 5
 2: Enter number: 6
 2: Enter number: 7
 2: Enter number: 8
123
5678
5 6 7 1 2 3 0
5 6 7 1 2 3 0
1 5 6 7 2 3 0
1 2 5 6 7 3 0
1 2 3 5 6 7 0
0 1 2 3 5 6 7

Originally Posted by userxbw

how about something like this?

It attempts to fix the mistake, but does so incorrectly in a rather convoluted way:

Code:

for(i=0;i<size1;i++)
{
    merge[i]=a1[i];
}

for(i=0;i<size2;i++)
{
    merge[i]=a2[i];
}
int merged=size2+size1;

for(i=0, k=size1; k<merged && i<size2; i++, k++)
{
    merge[k]=a1[i];
}

It would have been simpler to just write the elements of a1 in use to merge, then append to merge the elements of a2 in use, or vice versa. What you did was to write the elements of a1 to merge, then overwrite with the elements of a2, and then append with the elements of a1, but starting from the point where the end of the copy of a1 would have been, instead of the point where the end of the copy of a2 is.

Originally Posted by userxbw

as far as what to be in advance if that it what he has to do then he has to put a if statement in there to stop them from going over the limit, and still prevent blank elements that give crap data back.

That has to be done no matter what. Without correct boundary checking, you'll either end up incorrectly accessing unused elements of an array, or you'll go beyond the bounds of the array, both of which are bad.

Originally Posted by userxbw

a dynamic approach is the logical way to go when one does not know what size he needs before hand. especially in an array.

That's true, but it is unnecessary confusion when it would suffice to declare an array that is large enough for the largest number of elements to use, and then use a portion of that as needed. If you want to dynamically allocate an array, use a std::vector<int>, unless you're specifically trying to learn how to manually do dynamic memory allocation.

Originally Posted by laserlight

It attempts to fix the mistake, but does so incorrectly in a rather convoluted way:

Code:

for(i=0;i<size1;i++)
{
    merge[i]=a1[i];
}

for(i=0;i<size2;i++)
{
    merge[i]=a2[i];
}
int merged=size2+size1;

for(i=0, k=size1; k<merged && i<size2; i++, k++)
{
    merge[k]=a1[i];
}

It would have been simpler to just write the elements of a1 in use to merge, then append to merge the elements of a2 in use, or vice versa. What you did was to write the elements of a1 to merge, then overwrite with the elements of a2, and then append with the elements of a1, but starting from the point where the end of the copy of a1 would have been, instead of the point where the end of the copy of a2 is.


That has to be done no matter what. Without correct boundary checking, you'll either end up incorrectly accessing unused elements of an array, or you'll go beyond the bounds of the array, both of which are bad.


That's true, but it is unnecessary confusion when it would suffice to declare an array that is large enough for the largest number of elements to use, and then use a portion of that as needed. If you want to dynamically allocate an array, use a std::vector<int>, unless you're specifically trying to learn how to manually do dynamic memory allocation.

points taken , I did not mess with code to try and make it cleaner and such, I do not want to do all of his work, and two yes, I was just doing the how to dynamically get this done, as well as if this is class work too advance maybe too much. as well as I was not thinking out side of the box that much, as in using vector, but still for such a small array size 10 that way is not bad coding per se'.

me, I do not even know how to merge an array C++ newbie here too, just a snippet of C and BASH and Pascal - just trying to help, not hinder. nevertheless,

unless you're specifically trying to learn how to manually do dynamic memory allocation.

I was, first thing that came to my head when I seen he was over running elements. that eliminates it, pre vector for sure.

still works, for such a small amount, it loses a number and replaces it with a zero, personally I'd have to look at it closer to see why. even look into how to merge an array, that too is another reason I just ran with his code.

I was basicly trying to run with your idea on two functions and get them to work to show him how to do functions, mostly. returns and that other one needed to be void, not int.

Originally Posted by laserlight

It attempts to fix the mistake, but does so incorrectly in a rather convoluted way:

Code:

for(i=0;i<size1;i++)
{
    merge[i]=a1[i];
}

for(i=0;i<size2;i++)
{
    merge[i]=a2[i];
}
int merged=size2+size1;

for(i=0, k=size1; k<merged && i<size2; i++, k++)
{
    merge[k]=a1[i];
}

.

ok had time to actually look at his code and not just put it into a function and return whatever he did.

Code:

void insertion_sort(int b[], int length)
{
     
     // redid your insertion code
    int i, j, top;

    for (i = 1; i < length; i++)
    {
        top = b[i];
        j = i-1;
  
        while (j >= 0 && b[j] > top)
        {
            b[j+1] = b[j];
            j = j-1;
        }
        b[j+1] = top;
    }
 // here too no longer printing out more than once.
        for (i=0; i<length; i++)
              std::cout<<b[i]<<" "; 
          
        std::cout<<std::endl;
        
   }
 
   int * murge_array( int a1[], int a2[], int size1, int size2)
   {
       int * merge;
       int i,k;
       merge = new (std::nothrow) int [size1+size2];
 
    if ( merge == nullptr)
        std::cout << " cannot get memory" << std::endl;
     
    // just put the two together into a bigger array.

    for(i=0;i<size1;i++)
    {
      merge[i]=a1[i];
    }
    //get where you left off to pick up with
    //next array
    
    k = ( ( size1 + size2 ) - size1);
    int j = k;
  
    for( i=0 ; i < k;i++ )
    { 
        //j sets the element to where it left off
        // on first array. 
        merge[j]=a2[i];
        j++;
        //increment to keep it changing along with 
        // the other array.
    }
   
  return merge;
   }

as far as what he wants to do with preventing himself from over running the array(s) I'll leave up to him. it is simple math.

he can change it to vectors, or array[45] then do the math on it to prevent from over running it. He just needs to recode a little portion of it then bada bing.

Vector:
The actual size of the third array is known ahead of time and it is staying that size, not growing some time later on within the program before it ends. Vector is not really needed, it is a one time shot, not create 2 array's put them into a bigger array, then add more later before program ends. where a vector which (dynamically) can grow in size would come in.

for the first 2 arrays, if data gathering was an unknown size at start time then vector would come in, but he already asks what size do you want ahead of time. it then becomes known ahead of time, therefore, again vector is not needed. Unless he wants to learn how to grow the array(s) dynamically one at a time.

As far as what he said he had to do was just pick one out of three ways to sort it, not now to implement the arrays.

My assignment was to merge 2 arrays and then sort it into ascending order using bubble sort, insertion sort, or selection sort.

output

Code:

[userx@void just_playing_around]$ ./a.out
how many?
5
1: Enter number: 9
1: Enter number: 8
1: Enter number: 7
1: Enter number: 6
1: Enter number: 5
2: how many?
5
 2: Enter number: 1
 2: Enter number: 2
 2: Enter number: 3
 2: Enter number: 4
 2: Enter number: 5
1 2 3 4 5 5 6 7 8 9