merge sort question

[west oak]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For more information use !howto ask.

[sterile elbow]

merge sort question

[shell herald]

variable length arrays are not standard c++: ```cpp
int foo[lengthofA];
int foo2[lengthofB];

[sterile elbow]

Ah so how would I implement the arrays being of lengthofleft and length of right size?

[shell herald]

you could use std::vector

or if that's not allowed, you can use new

the larger issue here is that you have not implemented mergeSort and in main, you're calling merge instead of mergeSort

you need to sort the two subarrays and then merge the sorted versions

[sterile elbow]

Sorry just got back to my pc

SO I'll replace this code with the full code, the first part ofmain is just to make usre my merge works

There we go

BUt what i struggled with was how to split the array b as parameter *a into two subarrays

in the merge function

[shell herald]

got it

at the start, you said "I'm getting this output from this code" - what output are you getting, and what's the input?

[sterile elbow]

I was struggling w it for a while and gave up and jsut made two arrays to distribute b[0,lengthofa] and b[lengthofb,end]

uh

0
32765
-1132638936
32765
0
0
-1132656496
32765
-1133755072

output

and the input is just my line

for(int i = 0; i < lengthofA + lengthofB; i++)
        cout << temp[i] << endl;

[shell herald]

ok, i'm gonna try it locally and see if i can repro

[sterile elbow]

sure sure

[shell herald]

i get a crash due to out-of-bounds array indexing here:

foo has size 4, so the maximum valid index is 3, but you're trying to access index 4

[sterile elbow]

oh wait i should have made j < lengthofB+lengthofA

[shell herald]

you need to handle the cases where you run out of elements in one of the subarrays

[sterile elbow]

hmm could i make

[shell herald]

btw, this was one of the standard interview questions my officemate used to ask at my last job

"merge two sorted arrays"

so there's potential monetary value in studying this 😀

[sterile elbow]

ok I was starting to think I was incredibly dumb for not being able to do this haha

or well im not certain i'm not but im rather less stressed abt it

so

I'm assumign I would handle the cases where elements in one array run out

is an else?

making two ifs and an else for this

[shell herald]

in a nutshell, when you run out of elements in foo, then you need to copy all the remaining elements of foo2, and vice versa

yeah basically two extra if/else's

[sterile elbow]

so i'm assuming my else is the part I copy the array w extra elements

or does it not work that way

[shell herald]

i don't think while (j < lengthofB) { is the best way to start, what if lengthOfB is smaller than lengthOfA? Then you'll quit before you copy all the elements

[sterile elbow]

hmm right

is using this whole method fine to accomplish my task thus far?

I should start there

I feel as if I'm going about merging two sorted arrays really barbarically

Alright I looked into it and found this

this is how they deal with one array being empty, i'm not actualyl sure why this works though

[shell herald]

that's just copying whatever is left in arrayA or ArrayB, whichever one still has elements - notice that at most one of those two loops will actually execute, because by the time you get to the top of the second screenshot, at least one of the arrays has been depleted

[sterile elbow]

This does make sense i'm sorry for the late reply

I got caught up ins tuff

[sterile elbow]

void merge(int *a, int lengthofA, int lengthofB)
{
  
    int temp[100];

    //a should be the pointer to the first element in your array and lengthofA/
    //lengthofB should indicate how the array is divided into two sorted subarrays.
    //Merge the two sorted subarrays into the temp array, resulting a sorted temp.
    int foo[lengthofA];
    int foo2[lengthofA];
    cout <<lengthofA<< endl;
    int iA=0;
    int iB=0;
    int iC=0;
    for(int i=0;i<lengthofA; i++){
        a[i]=foo[i];
    }
    for(int i=0;i<lengthofB; i++){
        a[i+lengthofA]=foo2[i];
    }
    int j=0;
    
    
    while (iA<lengthofA && iB<lengthofB){
        if (foo[iA]<foo2[iB]){
        temp[iC]=foo[iA];
        iA++;
    }  
        else {
            temp[iC]=foo[iA];
            iB++;
            iC++;
        }
    }      
    while (iA<lengthofA){
        temp[iC]=foo[iA];
        iA++;
        iC++;
    }
    while (iB<lengthofB){
        temp[iC]=foo2[iB];
        iB++;
        iC++;
    } 
       
    for(int i = 0; i < 9; i++){
        cout << temp[i] << endl;
        }

}

Im doing someting severely wrong herebecause it outputs

32765
32765
32765
32765
32765
32765
-1697820256
32765
-1698937536

[shell herald]

you've overwriting your original array a here with the contents of foo and foo2, which are uninitialized so they contain random garbage: ```cpp
int foo[lengthofA];
int foo2[lengthofA];
cout <<lengthofA<< endl;
int iA=0;
int iB=0;
int iC=0;
for(int i=0;i<lengthofA; i++){
a[i]=foo[i];
}
for(int i=0;i<lengthofB; i++){
a[i+lengthofA]=foo2[i];
}

probably you meant to copy the other way (from a to foo and foo2)

[sterile elbow]

so foo[i] =a[i]

but the otehrway does not?

[shell herald]

the compiler can help you to avoid making mistakes like this. if you aren't going to modify the contents of a then make it a pointer to const: ```cpp
void merge(const int *a, int lengthofA, int lengthofB)

[shell herald]

a[i] = foo[i] takes whatever is in foo[i] (random junk) and copies it to a[i]

foo[i] = a[i] takes whatever is in a[i] (hopefully something meaningful) and copies it to foo[i]

[sterile elbow]

oh my god that amkes so much sense

thank you so mucn

now the hard part

my new output seems a bit more managaeble but i don't reall yknow wher eit'd come from I'll try to do some debugging

4
9
9
9
9
9
9
5
7
8

Man I seroiusly cannot come up with anything, any hints?

[shell herald]

can you paste your current code for the merge function?

[sterile elbow]

#include <iostream>

using namespace std;

void merge(int *a, int lengthofA, int lengthofB)
{
  
    int temp[100];

    //a should be the pointer to the first element in your array and lengthofA/
    //lengthofB should indicate how the array is divided into two sorted subarrays.
    //Merge the two sorted subarrays into the temp array, resulting a sorted temp.
    int foo[lengthofA];
    int foo2[lengthofA];
    cout <<lengthofA<< endl;
    int iA=0;
    int iB=0;
    int iC=0;
    for(int i=0;i<lengthofA; i++){
        foo[i]=a[i];
    }
    for(int i=0;i<lengthofB; i++){
        foo2[i]=a[i+lengthofA];
    }
    
    
    while (iA<lengthofA && iB<lengthofB){
        if (foo[iA]<=foo2[iB]){
        temp[iC]=foo[iA];
        iA++;
    }  
        else {
            temp[iC]=foo[iA];
            iB++;
            iC++;
        }
    }      
    while (iA<lengthofA){
        temp[iC]=foo[iA];
        iA++;
        iC++;
    }
    while (iB<lengthofB){
        temp[iC]=foo2[iB];
        iB++;
        iC++;
    } 
       
    for(int i = 0; i < lengthofA+lengthofB; i++){
        cout << temp[i] << endl;
        }

}

[shell herald]

yeah looks like there's still some garbage values being populated: ```
4
9
9
9
9
9
32759
289748
1
524432

[sterile elbow]

So I changed the

Foo2 to be length of b

since it was legnthofa for no reaosn

i've tried making line 28 <=

hmm

[shell herald]

you're missing iC++ here: ```cpp
while (iA<lengthofA && iB<lengthofB){
if (foo[iA]<=foo2[iB]){
temp[iC]=foo[iA];
iA++;
}

with that change, and your change to fix length of b, I get the following output now: ```
4
3
3
5
5
7
7
8
8
9

that first 4 is not part of the array

[sterile elbow]

4
3
3
5
5
7
7
8
8
9
3
5
7
8
2
4
6
7
9
im getting way more numbers

[shell herald]

whoa

did you maybe add some extra couts somewhere

the loop that prints the merged array only goes to lengthA + lengthB, which should be 9

[sterile elbow]

for(int i = 0; i < lengthofA+lengthofB; i++){
cout << temp[i] << endl;
}

       
    for(int i = 0; i < lengthofA+lengthofB; i++){
        cout << temp[i] << endl;
        }

[shell herald]

yeah

that prints 9 numbers for me

they aren't quite right

the 2 is missing

and so is the 4

[sterile elbow]

ok

ig to ti to

output

4
3
3
5
5
7
7
8
8
9

[shell herald]

ah this is wrong ```cpp
else {
temp[iC]=foo[iA];
iB++;
iC++;
}

should be emp[iC]=foo2[iB];

this is so error prone

[sterile elbow]

oh man

i was wriring it out in psuedocode to see wher i was makign themistake

not sure how i did not catch that

[shell herald]

here we go ```
2
3
4
5
6
7
7
8
9

that looks right finally

[sterile elbow]

Where do my numbers come from I'm confounded

[shell herald]

here is my edited version for reference (i also added a helper function to print the various arrays)

[sterile elbow]

4
3
3
5
5
7
7
8
8
9

[shell herald]

void print_array(int* array, int len, const char* label)
{
    std::cout << label << ":\n";
    for (int i = 0; i < len; i++) {
        std::cout << array[i] << std::endl;
    }
}

void merge(int *a, int lengthofA, int lengthofB)
{
    
    int temp[100];
    
    //a should be the pointer to the first element in your array and lengthofA/
    //lengthofB should indicate how the array is divided into two sorted subarrays.
    //Merge the two sorted subarrays into the temp array, resulting a sorted temp.
    int foo[lengthofA];
    int foo2[lengthofB];
    //cout <<lengthofA<< endl;
    int iA=0;
    int iB=0;
    int iC=0;
    for(int i=0;i<lengthofA; i++){
        foo[i]=a[i];
    }
    for(int i=0;i<lengthofB; i++){
        foo2[i]=a[i+lengthofA];
    }
    
    print_array(foo, lengthofA, "foo");
    print_array(foo2, lengthofB, "foo2");
    
    while (iA<lengthofA && iB<lengthofB){
        if (foo[iA]<=foo2[iB]){
            temp[iC]=foo[iA];
            iA++;
            iC++;
        }
        else {
            temp[iC]=foo2[iB];
            iB++;
            iC++;
        }
    }
    while (iA<lengthofA){
        temp[iC]=foo[iA];
        iA++;
        iC++;
    }
    while (iB<lengthofB){
        temp[iC]=foo2[iB];
        iB++;
        iC++;
    }
    
    print_array(temp, lengthofA+lengthofB, "temp");
    
}

[sterile elbow]

#include <iostream>

using namespace std;

void merge(int *a, int lengthofA, int lengthofB)
{
  
    int temp[100];

    //a should be the pointer to the first element in your array and lengthofA/
    //lengthofB should indicate how the array is divided into two sorted subarrays.
    //Merge the two sorted subarrays into the temp array, resulting a sorted temp.
    int foo[lengthofA];
    int foo2[lengthofB];
    int iA=0;
    int iB=0;
    int iC=0;
    for(int i=0;i<lengthofA; i++){
        foo[i]=a[i];
    }
    for(int i=0;i<lengthofB; i++){
        foo2[i]=a[i+lengthofA];
    }
    
    
    while (iA<lengthofA && iB<lengthofB){
        if (foo[iA]<=foo2[iB]){
        temp[iC]=foo[iA];
        iA++;
        iC++;
    }  
        else {
            temp[iC]=foo2[iB];
            iB++;
            iC++;
        }
    }      
    while (iA<lengthofA){
        temp[iC]=foo[iA];
        iA++;
        iC++;
    }
    while (iB<lengthofB){
        temp[iC]=foo2[iB];
        iB++;
        iC++;
    } 
       
    for(int i = 0; i < lengthofA+lengthofB; i++){
        a[i]=temp[i];
        }

}


    //After a and b have been merged into temp, copy the temp values back into a.
    


void mergeSort(int *a, int n)
{
    if(n==0 || n==1){
        return;
    }
mergeSort(a,n/2);
mergeSort(&a[(n/2)+1], n-n/2);
merge(a, n/2, n-n/2);













    
    //Split the array into two, mergesort both halfs, then merge them together.  
    //You must have a base case, a recursive call(s), and a call to merge.  Pay
    //attention.  The order on these matters.  
}

int main()
{
    //In this case, b has two sorted subarrays.  Use this test example,
    //to test your merge code independent of your merge sort.  
    int b[] = {3,5,7,8,2,4,6,7,9};
    int lengthOfLeft = 4, lengthOfRight = 5;
    merge(b, lengthOfLeft, lengthOfRight);
      for(int i = 0; i < lengthOfLeft + lengthOfRight; i++)
        cout << b[i] << endl;

    cout << "----------------------" << endl;  



    //Now that you're convinced your merge works, try sorting a.  
int a[] = {3,2,8,4,5,1,2, -1, -12};
int n = 9;
int left= 4;
int right= 5;

mergeSort(a, n);

for(int i = 0; i < n; i++)
     cout << a[i] << endl;


}

Sorry it's been a minute, bunt do you know why this outputs

2
3
5
-1
-12
1
2
8
4