CODEWITHSUNDEEP
c++arraysfor-loopundefined-behaviorinsertion-sort
Niso
Niso

Reputation: 21

Insertion sort algorithm behaves differently when put in a function

I have the following code to implement insertion sort:

int main()
{   
    const int SIZE = 10;
    int a[SIZE] = {8, 6, 10, 2, 16, 4, 18, 14, 12, 10};

    //insertionSort(a, SIZE);

    // The following code is used in the insertionSort() function call above. To use the function, uncomment the function call above, and comment out the code below

    // Start of code used by insertionSort() function
    int temp;
    for (int i=1; i < SIZE; i++)
    {
        for (int j=i; a[j] < a[j-1]; j--)
        {
            temp = a[j];
            a[j] = a[j-1];
            a[j-1] = temp;
        }
    }
    // End of code used by insertionSort() function

    return 0;   
}

void insertionSort(int a[], const int SIZE)
{
    int temp;
    for (int i=1; i < SIZE; i++)
    {
        for (int j=i; a[j] < a[j-1]; j--)
        {
            temp = a[j];
            a[j] = a[j-1];
            a[j-1] = temp;
        }
    }
}

The algorithm works fine when the code is used in main(), but it produces wrong results when it's called via insertionSort().

I've determined that the issue is this: the inner loop condition (a[j] < a[j-1]) does not stop the loop when j reaches 0, so it continues to access the array using the negative index. Changing the condition to (j > 0 && a[j] < a[j-1]) works as expected.

I would like to know why this behaviour only exhibits when the loop runs inside insertionSort() but not when it runs in main().

Upvotes: 1

Views: 87

Answers (1)

Vlad from Moscow
Vlad from Moscow

Reputation: 311058

This loop

    for (int j=i; a[j] < a[j-1]; j--)
    {
        temp = a[j];
        a[j] = a[j-1];
        a[j-1] = temp;
    }

invokes undefined behavior because there is no check that j shall be greater than 0.

Otherwise when for example j is equal to 0 then there is access beyond the array using the index -1

a[0] < a[-1]

Here is a demonstrative program with the updated loop

#include <iostream>
#include <utility>

int main() 
{
    int a[] = { 8, 6, 10, 2, 16, 4, 18, 14, 12, 10 };
    const size_t SIZE = sizeof( a ) / sizeof( *a );

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    for ( size_t i = 1; i < SIZE; i++ )
    {
        for ( size_t j = i; j != 0 && a[j] < a[j-1]; --j )
        {
            std::swap( a[j-1], a[j] );
        }
    }

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    return 0;
}

Its output is

8 6 10 2 16 4 18 14 12 10 
2 4 6 8 10 10 12 14 16 18

And including the algorithm in a function

#include <iostream>
#include <utility>

void insertionSort( int a[], size_t n )
{
    for ( size_t i = 1; i < n; i++ )
    {
        for ( size_t j = i; j != 0 && a[j] < a[j-1]; --j )
        {
            std::swap( a[j-1], a[j] );
        }
    }
}

int main() 
{
    int a[] = { 8, 6, 10, 2, 16, 4, 18, 14, 12, 10 };
    const size_t SIZE = sizeof( a ) / sizeof( *a );

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    insertionSort( a, SIZE );

    for ( const auto &item : a ) std::cout << item << ' ';
    std::cout << '\n';

    return 0;
}

The output is the same as shown above

8 6 10 2 16 4 18 14 12 10 
2 4 6 8 10 10 12 14 16 18

Upvotes: 3

Related Questions