Insertion sorting algorithm in C++

Question

I am creating an insertion algorithm for sorting in C++. Here it is:

void mySort2(int a[], const int num_elements)
{
    int x[num_elements];
    bool inserted(false);

    x[0] = a[0];

    for(int i = 1; i < num_elements; i++)
    {
        inserted = false;
        for(int j = 0; j < i; j++)
        {
            if(a[i] < x[j])
            {
                inserted = true;
                memmove(x + j + 1, x+j, (num_elements - j - 1)*sizeof(int*));
            x[j]=a[i];
                break;
            }
        }
        if(!inserted)
        {
            x[i] = a[i];
        }
    }

    print(x, num_elements);
}

When tested with the data set:

int num_elements(7);
int a[] = {2, 1, 3, 7, 4, 5, 6};

The code works as expected, printing 1, 2, 3, 4, 5, 6, 7 However, when I make the input any bigger than 7, the program has a Segmentation Error and dumps the core. I have tried data sets smaller than 7 elements and it again works as expected.

Do I need to be using dynamically allocated memory, or is there and error in my algorithm?

Thanks!

Run it in your debugger to find the line which causes the seg fault. Use vectors which will be bounds checked in good debug compilers. — Neil Kirk
– Neil Kirk, Commented Apr 9, 2015 at 18:01
If you are using C++ you should not be using a non standard VLA int x[num_elements]; — NathanOliver
– NathanOliver, Commented Apr 9, 2015 at 18:01

David · Accepted Answer · 2015-04-09 18:17:01Z

3

sizeof(int*) may not equal sizeof(int). Whether it does or not, you meant to write sizeof(int). You may be moving too much data and stomping over some random memory.

Oh and just for fun here's a suboptimal (but so little code!) insertion sort:

for(auto i = first; i != last; ++i)
    std::rotate(std::upper_bound(first, i, *i), i, std::next(i));

edited Apr 9, 2015 at 18:17

answered Apr 9, 2015 at 17:57

David

28.3k18 gold badges94 silver badges141 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Krab Over a year ago

depends on what cpu architecture he has

Mateusz Grzejek Over a year ago

Are you sure, that's the problem? In many compilers on 32-bit architectures sizeof(int) will be equal to sizeof(pointer_type).

David Over a year ago

I'm not completely sure that's the problem, it's definitely a mistake though.

Neil Kirk Over a year ago

@MateuszGrzejek What about architectures in which it isn't? A bug is a bug, even if it's currently sleeping.

Collectives™ on Stack Overflow

Insertion sorting algorithm in C++

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related