CODEWITHSUNDEEP
c++algorithmsortinginsertion-sort
user3618747
user3618747

Reputation: 5

Insertion sorting algorithm in C++

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!

Upvotes: 0

Views: 151

Answers (1)

David
David

Reputation: 28178

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));

Upvotes: 3

Related Questions