Insertion Sort Doing Nothing

Question

I wrote the following insertion sort yesterday (I started learning C 3 days ago). For some reason, the sort does not modify the array AT ALL.

#include <stdio.h>
int *insert(int arr[], int index, int item);
int *isort(int arr[]);
int main() {
    int a[17] = {1, 2, 9, 5, 3, 2, 1, 6, 5, 9, 0, 1, 3, 4, 2, 3, 4};
    int *b = isort(a);
    for (int i = 0; i < 17; i += 1) {
        printf("%d ", b[i]);
    }
    return 0;
}
int *insert(int arr[], int index, int item) {
    --index;
    while (index >= 0 && item < arr[index]) {
        arr[index + 1] = arr[index];
        --index;
    }
    arr[index + 1] = item;
    return arr;
}
int *isort(int arr[]) {
    for (int i = 1; i < sizeof(arr) - 1; i++) {
        arr = insert(arr, i, arr[i]);
    }
    return arr;
}

I'm thinking it could be my compiler, as I'm running a compiler that is on a non unix machine: lcc-win, but I'm not sure. Is there some fundamental thing I'm missing here?

[Why sizeof(param_array) is the size of pointer?](http://stackoverflow.com/questions/11622146/) — Blastfurnace, Aug 14 '12 at 20:53
@Blastfurnace Because in C an array reference without an index *is* a pointer. — Peter Gluck, Aug 14 '12 at 20:59
@PeterGluck: I know, sorry I should have made it more clear that my comment was a link. This question about passing arrays has been asked many times so I found a similar related question with answers. — Blastfurnace, Aug 14 '12 at 21:01

score 3 · Accepted Answer · answered Aug 14 '12 at 20:49

3

int *isort(int arr[]) {
    for (int i = 1; i < sizeof(arr) - 1; i++) {
        arr = insert(arr, i, arr[i]);
    }
    return arr;
}

In this function sizeof(arr) actually returns the size of the pointer and not the size of the array.

In C a special rule says an array parameter is actually adjusted to a parameter of the corresponding pointer type.

That is:

int *isort(int arr[]) { /* ... */ }

is equivalent to this:

int *isort(int *arr) { /* ... */ }

To fix this, add a new parameter in your function that takes the size of the array:

int *isort(int arr[], size_t size) { /* ... */ }

answered Aug 14 '12 at 20:49

ouah

142,963
15
272
331

So what should I put instead of sizeof? – Bobby Tables Aug 14 '12 at 20:52
@BobbyTables, Arrays in C need a size parameter with them. – chris Aug 14 '12 at 20:56
Thanks a lot, worked! Just wondering, why size_t rather than an int or long? Never seen that type before – Bobby Tables Aug 14 '12 at 21:03
1

@BobbyTables because `sizeof` yields a value of type `size_t` but `int` or `long` would be also OK in your program. – ouah Aug 14 '12 at 21:05

score 1 · Answer 2 · answered Aug 14 '12 at 23:15

The first problem, as has been pointed out, is that the isort function uses the sizeof operator on a pointer. The way C treats arrays is a little strange at first glance. The name of an array is a pointer to its first element. So when you call isort like this:

int *b = isort(a);

you are simply pushing a pointer to the array onto the stack. In the definition of isort,

int *isort(int arr[])

declares arr to be a pointer to int just like

int *isort(int *arr)

C is even more confusing in this respect: if you had said:

int *isort(int arr[17])

the arr variable is still just a pointer to int ... the "17" here is discarded! Even with this syntax, sizeof(arr) will still be the size of a pointer to int.

On a 32-bit system (ILP32), sizeof(arr) will always be 4, however big the array is.

Therefore, you need to pass the size of the array to isort. A good general way to do this is to define a macro like this:

#define NITEMS(arr) (sizeof(arr)/sizeof(arr[0]))

This will calculate the number of elements in an array of any type.

Your next problem is more a style one than an actual error:

arr = insert(arr, i, arr[i]);

This calls the insert function with a reference to "arr". The array is modified through this reference, and then a pointer to that array is returned. It will always be the same pointer as you sent in the first place, so this assignment actually does nothing, harmlessly. Like I say, a style problem, not a code error.

The final issue is your isort function stops one short (after you correct the sizeof problem), since you went from 1 to sizeof-1. Here is a fixed version:

#include <stdio.h>
#define NITEMS(arr) (sizeof(arr)/sizeof(arr[0]))

int *insert(int arr[], int index, int item);
int *isort(int arr[], size_t nitems);
int main() {
    int a[17] = {1, 2, 9, 5, 3, 2, 1, 6, 5, 9, 0, 1, 3, 4, 2, 3, 4};
    int *b = isort(a, NITEMS(a));
    for (int i = 0; i < NITEMS(a); i += 1) {
        printf("%d ", b[i]);
    }
    printf("\n");
    return 0;
}

int *insert(int arr[], int index, int item) {
    --index;
    while (index >= 0 && item < arr[index]) {
        arr[index + 1] = arr[index];
        --index;
    }
    arr[index + 1] = item;
    return arr;
}

int *isort(int arr[], size_t nitems) {
    for (int i = 1; i < nitems; i++) {
        insert(arr, i, arr[i]);
    }
    return arr;
}

Insertion Sort Doing Nothing

2 Answers2