Insertion sort - program exits with error 5

Question

I'm a beginner. I want to learn insertion sort, but in the printing I got an error. Running the code I got this output:

entrez la taille du tableau : 5
entrez les elements du tableau : 43
32
1
4
5
votre tableau ressemble a :  43  32  1  4  5 
tableau TRIE:  4  4  1  1  1
--------------------------------
Process exited after 6.303 seconds with return value 5
Press any key to continue . . .

This is my code:

#include <stdio.h>

void triinsertion(int T[], int taille)
{
    int i, j;
    for (i = 1; i < taille; i++)
    {
        int temp = T[i];
        int j = i - 1;
        while (temp > T[j] && j >= 0)
        {
            T[j + 1] = T[j];
            j--;
        }
        T[j] = temp;
    }
}

int main ()
{
    int taille, i;
    printf("entrez la taille du tableau : ");
    scanf("%d", &taille);
    
    int T[taille];
    printf("entrez les elements du tableau : ");   
    for (i = 0; i < taille; i++)
    {
        scanf("%d", &T[i]);
    }
    
    printf("votre tableau ressemble a : ");
    for (i = 0; i < taille; i++)
    {
        printf(" %d ", T[i]);
    }

    triinsertion(T, taille);
    
    printf("tableau TRIE: ");
    for (i = 0; i < taille; i++)
    {
        printf(" %d ", T[i]);
    }
}

Answer 1

There are two issues in your insertion sort function:

1. The while condition does not check whether the index j is valid before accessing T[j]. It does so after making that access, but then it is too late. If j is less than 0, then accessing T[j] leads to undefined behaviour. This could be an error that exits your program, like happened in your example.

2. The assignment at the end is wrong: T[j]=temp; is assigning temp to the wrong index. Note that j could even be -1, so this makes no sense. You should assign to T[j + 1].

Not a problem, but you never use the outer defined j, since you declare it again inside the loop block.

Here is the corrected function:

void triinsertion(int T[], int taille)
{
    for (int i = 1; i < taille; i++)
    {
        int temp = T[i];
        int j = i - 1;
        while (j >= 0 && temp > T[j])
        {
            T[j + 1] = T[j];
            j--;
        }
        T[j + 1] = temp;
    }
}