Insertion sort algorithm, weird behaviour-CodePudding

I am learning C programming and I'm currently on a classic one, the insertion sort algorithm.

For contextualization, I have a set of 3 arrays to test on :

the first one which is disordered
the second one is in a descending order
and the last one is is the ordered one but with a swap between 2 elements.

Here is my code :

int insertionSort(int* tab, int n){
    int i;
    for (i=1; i<n; i  ){
        int j = i;
        while(tab[j] < tab[j-1]) {
            swap(&tab[j-1], &tab[j]);
            j-=1;
        }
    }
    affiche(tab, n);
    return 0;
}

For the 2 last arrays, it works fine. But for the first one I got :

6 6 7 8 10 32521 14 15 17 19 20 21 23 25 26 28 28 28 32 32 34 35 38 38 39 43 44 46 48 49 50 58 59 62 64 65 69 71 75 79 79 79 81 84 86 89 92 93 97 99

instead of

3 6 6 7 8 10 14 15 17 19 20 21 23 25 26 28 28 28 32 32 34 35 38 38 39 43 44 46 48 49 50 58 59 62 64 65 69 71 75 79 79 79 81 84 86 89 92 93 97 99

As you can see, the algorithm works fine for a big part of the array, but for the sixth minimal values, I have random values (sometimes there are 92,93,97... for the first ones).

I don't have any core dump, which means that I am in the array's space in memory, but some values like 32521 let me think that my index j goes too far in memory.

Frankly, I don't see where the problem is.

CodePudding user response：

Look at this loop

    while(tab[j] < tab[j-1]) {
        swap(&tab[j-1], &tab[j]);
        j-=1;
    }

j can run happily all over the place. There needs to be something that detects that j isnt < 0 (actually < 1 since you access 'tab[j-1]')

maybe

while((j >= 1) && (tab[j] < tab[j-1]) ) {
        swap(&tab[j-1], &tab[j]);
        j-=1;
    }