Bugged C Implementation of Straight Insertion sorting

Question

A beginner in C, i'm attempting to implement a Straight Insertion sort. My code has a bug, but i struggle to put my finger on it. If someone experience could point me in the right direction, it'd be much appreciated !!

A few points :

• The variable sizeTable is the dimension of the array (10). It shouldn't change at any stage, yet when exiting the sorting algorithm, it's worth 100.
• The code was running fine with values from 10 down to 1 (i.o. 100 down to 10).
• I use different variable names (namely aSize, mySize & sizeTable for the array dimension argument on purpose (making sure i understand passing arguments to functions). However using one single variable name doesn't change anything (thankfully!).
• When i run in CodeChef, i get a runtime error whereas in CodeBlocks, i obtain a 100-elements array, 10 first ones being the initial array properly sorted, and the balance random values from the memory. Why so ? (that's a subsidiary question...)

Thanks in advance !

#include <stdio.h>
#include <stdlib.h>


void printTable(int myTable[], int aSize);
void straightInsertion(int myTable[], int mySize);

int main()
{

    int sizeTable = 10;
    int myTable[10] = {100, 90, 80, 70, 60, 50, 40, 30, 20, 10};

    printTable(myTable, sizeTable);
    straightInsertion(myTable, sizeTable);
    printf("\n");
    printTable(myTable, sizeTable);


    return 0;
}

//Loop to display the array
void printTable(int myTable[], int aSize)
{
    int  i = 0;

    for (i = 0; i < aSize; i++)
    {
        printf("%d ", myTable[i]);
    }
}

//Sorting algo
void straightInsertion(int myTable[], int mySize)
{
    int i = 0, j = 0, temp = 0;
    for(j = 1; j<= mySize; j++)
    {
        temp = myTable[j];
        i = j-1;
        while(i>=0 && myTable[i] > temp)
        {
            myTable[i+1] = myTable[i];
            i--;
        }
        myTable[i+1] = temp;
    }
}

Answer 1

Refactoring and correcting your straightInsertion function

void straightInsertion(int myTable[], int mySize) {
    int i, j;
    for (i = 1; i < mySize; ++i) {
        int tmp = myTable[i];
        for (j = i; j > 0 && myTable[j - 1] > tmp; j--)
            myTable[j] = myTable[j - 1];
        myTable[j] = tmp;
    }
}

Answer 2

In your loop, you used:

for(j = 1; j<= mySize; j++)

Remember that arrays in C are zero-indexed, meaning an array's first index is at 0, not 1, so its last index is going to be mySize - 1. That means that accessing myTable[mySize] is always going to be out of bounds, and accessing that address is undefined behavior.

If you change the line to

for(j = 1; j < mySize; j++)

the code works perfectly.

Answer 3

Simple bounds error. You have:

for(j = 1; j<= mySize; j++)

You should be using:

for (j = 1; j < mySize; j++)

to avoid overwriting the end of the array.

Good work on the use of the printing function. May I recommend that you add putchar('\n'); in the function to avoid needing to use printf("\n"); in the calling code.