How to convert java merge sort algo to cpp

Question

Problem

I have a source code in Java for sorting array elements using the merge sort algorithm. The principle uses a loop to compare an element in the array with the element in the next index in the array. If the earlier is bigger than the later then the numbers are swapped logically to reassign the array elements in the indices. My problem is that the Java algo works but the C++ algo does not. The logic is the same, what am I doing wrong....

Code

Working Java Code

static void sort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

C++ Code built on the same merge sort pseudocode as the Java Source code but fails to work

void sorting(int d[]) {
    for (int i = 0; i < sizeof(d); i++) {
        for (int j = i + 1; j < sizeof(d); j++) {
            if (d[i] > d[j]) {
                int temp = d[i];
                d[i] = d[j];
                d[j] = temp;
            }
        }
    }
}

Input Format

Both methods got parameters from arrays initialized to a fixed size and then a loop was used to get input from user and asign to the array, the user has to enter the size of the array first.

Reliability of the merge sort algo in other languages

I have applied the mergesort pseudocode in JavaScript, Python and C# and they all worked. I do not know why C++ would be an exception, please help...

`sizeof(d)` is not the size of the array. You are going to need to pass the array length in as a parameter. Or just use `std::vector`. — Richard Critten, Nov 21 '21 at 18:47
I checked online and they said to check size of array we need to use `sizeof` — Son of Man, Nov 21 '21 at 18:48
Use `std::array` if you know the size of the array before hand, or `std::vector` if you don't. — infinitezero, Nov 21 '21 at 18:49
Does this answer your question? [size of array passed to C++ function?](https://stackoverflow.com/questions/3062005/size-of-array-passed-to-c-function) — Lev Leontev, Nov 21 '21 at 18:50
@Albin Paul, why would I need to divide, isn't there a built in array function to yield the size like other static languages? — Son of Man, Nov 21 '21 at 18:50
@AlbinPaul not with a parameter of type `int d[]` as `d` has decayed to a pointer and is no longer an array type. `sizeof(d)` will return the size of a pointer. — Richard Critten, Nov 21 '21 at 18:51
@KINYUATIMOTHYNJIRU Whatever source you found that says `sizeof(array)` gives you the size once that array has decayed to a pointer is wrong. Even if it hasn't it would give you the size in bytes, not the size in elements. Use `std::array` or `std::vector` in C++. — Retired Ninja, Nov 21 '21 at 18:52
@Leo Leontev, no because the context of the problem is different though the root cause is related. — Son of Man, Nov 21 '21 at 18:52
@Retired Ninja, now that expressed in form of something that I can paste in my code editor is greatly appreciated — Son of Man, Nov 21 '21 at 18:53
@KINYUATIMOTHYNJIRU pass the length of the array in as a 2nd parameter. — Richard Critten, Nov 21 '21 at 18:55

Vlad from Moscow · Accepted Answer · 2021-11-21T19:07:19.193

For starters there is no merge sort algorithm in your question.

In fact there is a modified selection sort algorithm.

This function declaration

void sorting(int d[])

is adjusted by the compiler to the declaration

void sorting(int *d)

That is the parameter has a pointer type.

So the expression

sizeof(d)

yields the size of a pointer not the number of element in the passed array.

You need also to pass to the function the number of elements in the array.

The function can look the following way

void sorting( int a[], size_t n )
{
    for ( size_t i = 0; i < n; i++ )
    {
        size_t min = i;

        for ( size_t j = i + 1; j < n; j++ )
        {
            if ( a[j] < a[min] ) min = j;
        }

       if ( i != min ) std::swap( a[i], a[min] );
    }
}

Another approach is using a template function that accepts an array by reference.

For example

template <size_t N>
void sorting( int ( &a )[N] )
{
    for ( size_t i = 0; i < N; i++ )
    {
        size_t min = i;

        for ( size_t j = i + 1; j < N; j++ )
        {
            if ( a[j] < a[min] ) min = j;
        }

       if ( i != min ) std::swap( a[i], a[min] );
    }
}

Here is a demonstration program that shows usage of the two functions.

#include <iostream>
#include <utility>

void sorting( int a[], size_t n )
{
    for (size_t i = 0; i < n; i++)
    {
        size_t min = i;

        for (size_t j = i + 1; j < n; j++)
        {
            if (a[j] < a[min]) min = j;
        }

        if (i != min) std::swap( a[i], a[min] );
    }
}

template <size_t N>
void sorting( int ( &a )[N] )
{
    for (size_t i = 0; i < N; i++)
    {
        size_t min = i;

        for (size_t j = i + 1; j < N; j++)
        {
            if (a[j] < a[min]) min = j;
        }

        if (i != min) std::swap( a[i], a[min] );
    }
}

int main()
{
    int a[] = { 5, 4, 3, 2, 1 };
        
    for (const auto &item : a)
    {
        std::cout << item << ' ';
    }

    std::cout << '\n';

    sorting( a, sizeof( a ) / sizeof( *a ) );

    for (const auto &item : a)
    {
        std::cout << item << ' ';
    }

    std::cout << '\n';

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

    for (const auto &item : b)
    {
        std::cout << item << ' ';
    }

    std::cout << '\n';

    sorting( b );

    for (const auto &item : b)
    {
        std::cout << item << ' ';
    }

    std::cout << '\n';
}

The program output is

Your second function worked, I did not understand anything due to the many variables used but i copied and pasted and added a size argument and it worked — Son of Man, Nov 21 '21 at 19:07

infinitezero · Answer 2 · 2021-11-21T18:57:17.297

1

In general you should use std::array or std::vector instead of raw arrays (int[]). They also offer more functions that you might know from Java or other languages. Also checkout std::swap.

#include <iostream>
#include <vector>
void sorting(std::vector<int>& d)
{
    for (int i = 0; i < d.size(); i++)
    {
        for (int j = i + 1; j < d.size(); j++)
        {
            if (d[i] > d[j])
            {
                std::swap(d[i], d[j]);
               /*
                int temp = d[i];
                d[i] = d[j];
                d[j] = temp;
              */
            }
        }
    }
}

int main()
{
    std::vector<int> test = {5,1,4,3,2};
    sorting(test);
    for( auto const& elem : test )
    { 
        std::cout << elem << " ";
    }
    std::cout << "\n";
    return EXIT_SUCCESS;
}

edited Nov 21 '21 at 18:57

answered Nov 21 '21 at 18:54

infinitezero

1,610
3
14
29

Thanks, this was really helpful, why would we need a pointer after the parameter type declaration ? – Son of Man Nov 21 '21 at 18:56
That's not a pointer, that's a reference. If you don't give a reference, a copy will be made, and the original array will not be changed. – infinitezero Nov 21 '21 at 18:58
C++ is tough, almost these other languages implement algos without so much hustle – Son of Man Nov 21 '21 at 19:04

How to convert java merge sort algo to cpp

2 Answers2