I'm trying implement mergesort using array in a class, but all i get are random values, mostly zeros

Question

I don't know if i can operate like this on my array, or i should create some copy of it. Still i have other algorithms to implement that's why i thought of using array in this class. I think the problem is with using this array ,,arr", because when i printed the values in the separate_and_merge function, they were mostly 0, or trashes, i don't know what i have done wrong.

#include <iostream>

template<typename TYPE, int SIZE>
class Array
{
private:
    TYPE* arr;
public:
    void DisplayArray();
    void separate_and_merge(int begin, int middle, int end);
    void merge_sorting(int begin, int end);
    void getRandomArray();
    Array();
};

template<typename TYPE, int SIZE>
Array<TYPE, SIZE>::Array()
{
    arr = new TYPE[SIZE];
}

template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::separate_and_merge(int begin, int middle, int end)
{

    int size_left = middle - begin + 1; //rozmair lewej podtablicy
    int size_right = end - middle; // rozmiar prawej podtablicy


    TYPE arr1[size_left]; // inicjacja tablic
    TYPE arr2[size_right];

    // podpisanie wartosci pod tablice
    for (int i = 0; i < size_left; i++)
    {
        arr1[i] = arr[i];
    }

    for (int j = 0; j < size_right; j++)
    {
        arr2[j] = arr[j + middle + 1];
    }

    for (int i = 0; i < SIZE; i++)
    {

    }
    //scalenie wartosci 2 podtablic w 1 tablice
    int i = 0;
    int j = 0;
    int begin1 = begin; //aktualny indeks scalanej tablicy
    while (i <= size_left && j <= size_right)
    {
        if (arr1[i] < arr2[j])
        {
            arr[begin1] = arr1[i];

            i++;
        }
        else
        {
            arr[begin1] = arr2[j];
            j++;

        }
        begin1++;
    }
}


template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::merge_sorting(int begin, int end)
{
    if (begin < end)
    {
        int middle = (begin + end) / 2; // srodek tablicy   
        merge_sorting(begin, middle);
        merge_sorting(middle + 1, end);
        separate_and_merge(begin, middle, end);
    }
}

template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::DisplayArray()
{
    for (int i = 0; i < SIZE; i++)
    {
        std::cout << arr[i] << std::endl;
    }
}


template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::getRandomArray()
{
    srand(time(NULL));
    for (int i = 0; i < SIZE; i++)
    {
        arr[i] = std::rand();
    }
}


int main() {

    const int size = 10;

    Array<int, size> tmp;

    tmp.getRandomArray();
    tmp.DisplayArray();
    std::cout << std::endl << std::endl << std::endl << std::endl;
    tmp.merge_sorting(0, size);
    tmp.DisplayArray();

    return 0;
}

`TYPE arr1[size_left];` is not standard C++. [Variables length arrays](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) are only available by compiler extensions. — Brian61354270, Mar 14 '21 at 23:52
This program exhibits undefined behavior by way of accessing an uninitialized variable. `arr2[0]` is accessed but never initialized. — Igor Tandetnik, Mar 14 '21 at 23:52
Further, the program accesses `arr1[size_left]` and `arr2[size_right]` - this exhibits undefined behavior by way of accessing an index out of bounds. — Igor Tandetnik, Mar 14 '21 at 23:54
`arr2[j]=arr[j]` ... `j` on the rhs might be okay, but not on the lhs. — ChrisMM, Mar 14 '21 at 23:55
If you formatted the code more neatly and consistently, people might find it easier to provide help. — Galik, Mar 15 '21 at 00:02
So how can i change these arrays? I know that i could use std::vector, but I'm not really interested in it, because I'm planning to extend my array into two-dimensional array, and test it out for 100 arrays of 10000000 elements. That's my task, that's why I want to allocate memory on stack instead of heap like vector does. Is there any way i Can do it on normal stack arrays? If I would use dynamic alocated arrays it would be ok or do i have to pass it somehow-but if so, i kinda don't know how using class, because i can't asign class into passed array? — 77jt777, Mar 15 '21 at 09:07
Sorry! I tried to run the code through an online pretty-print, but after I pasted it and saved it, I realized the formatter changed the code for the wrong. **I reverted the edit.** — selbie, Mar 15 '21 at 09:22
@selbie: I agree! the code is a mess, I gave up trying to pretty print it. In an exam, it would get a fail before even testing for correctness. — chqrlie, Mar 15 '21 at 09:23
Ok, better format to the edit has been made. Visual Studio does a decent job formatting. — selbie, Mar 15 '21 at 09:26
Sorry, but i'm pretty new to stackoverflow and coding, how can i help? I mean what do you mean by sentence ,,format" code? — 77jt777, Mar 15 '21 at 09:36

Ynjxsjmh · Accepted Answer · 2021-03-15T16:02:04.653

Some problems I found

int main() {
    ...
    tmp.merge_sorting(0, size);
    ...

    return 0;
}

From above, you are passing 0, size to merge_sorting() method. C++ is zero based indexing, so that the index of last element of tmp array is size-1. You'd better do tmp.merge_sorting(0, size-1);.

void Array<TYPE, SIZE>::separate_and_merge(int begin, int middle, int end)
{
    ...

    // podpisanie wartosci pod tablice
    for (int i = 0; i < size_left; i++)
    {
        arr1[i] = arr[i];
    }

    ...
}

arr1[i] = arr[i] should be arr1[i] = arr[begin + i]. Because in this function, you are considering the [begin, end) part of the arr.

    TYPE arr1[size_left]; // inicjacja tablic
    TYPE arr2[size_right];

    while (i <= size_left && j <= size_right)
    {
        if (arr1[i] < arr2[j])
        {
            arr[begin1] = arr1[i];
            i++;
        }
        else
        {
            arr[begin1] = arr2[j];
            j++;

        }
        begin1++;
    }

It shouldn't have = in i <= size_left && j <= size_right. Take i=size_left as an example, since the size of arr1 is size_left and C++ is zero indexed, it will cause index out of range error.

Moreover, have you considered the case that size_left != size_right? Take size_left > size_right as an example. After the above while loop, there remain some elements in arr1. So you need consider the remaining elements of arr1 and arr2.

    // Copy the remaining elements of arr1[],
    // if there are any
    while (i < size_left) {
        arr[begin1] = arr1[i];
        i++;
        begin1++;
    }

    // Copy the remaining elements of arr2[],
    // if there are any
    while (j < size_right) {
        arr[begin1] = arr2[j];
        j++;
        begin1++;
    }

The whole code is

#include <iostream>

template<typename TYPE, int SIZE>
class Array
{
private:
    TYPE* arr;
public:
    void DisplayArray();
    void separate_and_merge(int begin, int middle, int end);
    void merge_sorting(int begin, int end);
    void getRandomArray();
    Array();
};

template<typename TYPE, int SIZE>
Array<TYPE, SIZE>::Array()
{
    arr = new TYPE[SIZE];
}

template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::separate_and_merge(int begin, int middle, int end)
{
    int size_left = middle - begin + 1; //rozmair lewej podtablicy
    int size_right = end - middle; // rozmiar prawej podtablicy

    TYPE arr1[size_left]; // inicjacja tablic
    TYPE arr2[size_right];

    // podpisanie wartosci pod tablice
    for (int i = 0; i < size_left; i++)
    {
        arr1[i] = arr[begin + i];
    }

    for (int j = 0; j < size_right; j++)
    {
        arr2[j] = arr[j + middle + 1];
    }

    std::cout << "+++++++[" << begin << ", " << end << ")+++++++++" << std::endl;
    std::cout << "begin: "  << begin  << std::endl;
    std::cout << "middle: " << middle << std::endl;
    std::cout << "end: "  << end    << std::endl;
    std::cout << "size_left: "  << size_left  << std::endl;
    std::cout << "size_right: "  << size_right << std::endl;
    std::cout << "+++++++++++++++++++++" << std::endl;

    std::cout << "======[0, SIZE)==========" << std::endl;
    for (int i = 0; i < SIZE; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "!!!!![begin, end)!!!!" << std::endl;
    for (int i = begin; i < end; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "!!!!!!!!!!!!!!!!!!!!!" << std::endl;

    std::cout << "@@@@@[begin, mid)@@@@" << std::endl;
    for (int i = 0; i < size_left; i++)
    {
        std::cout << arr1[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "@@@@@@@@@@@@@@@@@@@@@" << std::endl;

    std::cout << "$$$$$[mid, end)$$$$" << std::endl;
    for (int i = 0; i < size_right ; i++)
    {
        std::cout << arr2[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "$$$$$$$$$$$$$$$$$$$$$" << std::endl;

    //scalenie wartosci 2 podtablic w 1 tablice
    int i = 0;
    int j = 0;
    int begin1 = begin; //aktualny indeks scalanej tablicy
    while (i < size_left && j < size_right)
    {
        if (arr1[i] < arr2[j])
        {
            arr[begin1] = arr1[i];
            i++;
        }
        else
        {
            arr[begin1] = arr2[j];
            j++;
        }
        begin1++;
    }

    // Copy the remaining elements of
    // arr1[], if there are any
    while (i < size_left) {
        arr[begin1] = arr1[i];
        i++;
        begin1++;
    }

    // Copy the remaining elements of
    // arr2[], if there are any
    while (j < size_right) {
        arr[begin1] = arr2[j];
        j++;
        begin1++;
    }

    std::cout << "======[begin, end)=======" << std::endl;
    for (int i = begin; i < end; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "======[0, SIZE)==========" << std::endl;
    for (int i = 0; i < SIZE; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl << "=========================" << std::endl << std::endl;
}


template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::merge_sorting(int begin, int end)
{
    if (begin < end)
    {
        int middle = (begin + end) / 2; // srodek tablicy

        merge_sorting(begin, middle);
        merge_sorting(middle + 1, end);

        separate_and_merge(begin, middle, end);
    }
}

template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::DisplayArray()
{
    for (int i = 0; i < SIZE; i++)
    {
        std::cout << arr[i] << std::endl;
    }
}


template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::getRandomArray()
{
    srand(time(NULL));
    for (int i = 0; i < SIZE; i++)
    {
        arr[i] = std::rand();
    }
}


int main() {
    const int size = 12;

    Array<int, size> tmp;

    tmp.getRandomArray();
    tmp.DisplayArray();
    std::cout << std::endl << std::endl << std::endl << std::endl;
    tmp.merge_sorting(0, size-1);
    std::cout << std::endl << std::endl;
    tmp.DisplayArray();

    return 0;
}

Thank you so much. it works! But I don't know why If i'm generating big numbers it gives some random values after sorting, but when i generated numbers from 0-100 it works perfectly fine — 77jt777, Mar 15 '21 at 10:44
@77jt777 To my knowledge, it shouldn't be if the program is right. How about the code I add at the bottom, does the same thing happen with it? — Ynjxsjmh, Mar 15 '21 at 11:00
Thank you very much for helping. I accepted your solution, with code you added at the bottom it works totally fine. But i have one more question: if i change size of an array to 11 for example, all algorithm crushes, due to these sizes of arrays i guess, how could i fix that? — 77jt777, Mar 15 '21 at 14:31
@77jt777 Sorry, after re-run the code I posted, it seems that the array is not sorted. You could cancel accpeted if you can. I will give feedback after I figure out what's going wrong. — Ynjxsjmh, Mar 15 '21 at 14:58
I guess you shouldn't give size_right=end-middle-1 because if we have size=10, then indexes are 0 and 9, so: size_left=middle-begin+1=5-0+1=6, size_right=end-middle=9-5=4, and then it works that way. Still you helped me a lot, i will not cancel accepted. — 77jt777, Mar 15 '21 at 15:03
@77jt777 See my edited answer. The code should work now. But I still don't figure out what's going on when pass `0, size` to `merge_sort` and have no idea how to fix on that condition. — Ynjxsjmh, Mar 15 '21 at 16:03

I'm trying implement mergesort using array in a class, but all i get are random values, mostly zeros

1 Answers1