uint as indices

Question

EDIT: Originally I had transcribed i++ not i--

The code now is as it was, and the code in the code block compiles and works.

Why, if unsigned int i; is used instead of int i; in the code snippet below, does using the function result in a segfault?

void insertion_sort_int_array(int * const Ints, unsigned int const len) {
     unsigned int pos;
     int key;
     int i;

     for (pos = 1; pos < len; ++pos) {
         key = Ints[pos];
         for (i = (pos - 1); (i >= 0) && Ints[i] > key; i--) {
          Ints[i + 1] = Ints[i];
         }
         Ints[i + 1] = key;
     }
}

Answer 1

What keeps i+1 within the bounds of your array 'ints'? It looks like badly formed data in your array will cause you to index into areas of memory which you shouldn't be in.

Answer 2

THe posted code will fail in either case (possibly with a segfault, possibly only corrupting memory).

The inner loop starts at pos-1 and scans upwards in memory until some random condition is met - it does not check if it has passed the end of the array, so will run merrily on until it crashes or the end condition happens to be met by the (undefined) contents of the memory it is corrupting.

You probably meant to scan downwards in memory (using i-- in the loop), in which case it would fail because the loop will reach 0. Subtracting 1 from 0 gives you a very large positive number in an unsigned, so the loop will never end (i>=0 is always true) and it will access some memory somewhere in the region of Pluto.

Answer 3

i will [wraparound] causing access beyond the array limits.

Importing limits and comparing to UINT_MAX instead of the previous (i >= 0) fixes the issue:

#include <limits.h>

void insertion_sort_int_array(int * const Integers, unsigned int const N)
{
     unsigned int o;
     int target;
     unsigned int i;

     for (o = 1; o < N; o++) {
         target = Integers[o];
         for (i = (o - 1); (i != UINT_MAX) && (Ints[i] > target); i--) {
             Integers[i + 1] = Integers[i];
         }
         Integers[i + 1] = key;
     }
}

Answer 4

insertionSort(array A)
begin
    for x := 1 to length[A]-1 do
    begin
        value := A[x];
        i := x - 1;
        while i >= 0 and A[i] > value do
        begin
            A[i + 1] := A[i];
            i := i - 1;
        end;
        A[i + 1] := value;
    end;
end;

The only difference between the standard insertion sort algorithm and your code is that you're incrementing i instead of decrementing. That's your problem. I bet that in the code you're actually compiling and running, you have i-- instead of i++ in the inner loop. That's why the unsigned i makes a difference - it cannot be negative, so the inner loop will never end. Did you copy the code wrong when you posted?

EDIT:

Well, now that you changed the posted code, it all makes sense, right? An unsigned i will simply underflow to INT_MAX when you decrement it past 0, which will cause you to access memory outside of the array bounds.

Answer 5

Why, if unsigned int i; is used instead of int i; in the code snippet below, does using the function result in a segfault?

Because for unsigned int i, i >= 0 is always true, so your for loop is unlikely to terminate when you want.

You should always be extremely careful when looping backwards (from high to low) if your counter is unsigned.