Вставка сортировка ничего не делая

Question

Я написал следующий вид вставки вчера (я начал изучать C 3 дня назад). По какой-то причине сортировка не изменяет массив ВСЕ.

#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;
}

Я думаю, что это может быть мой компилятор, так как я работаю на компиляторе не на Unix-машине: lcc-win, но я не уверен. Есть ли здесь какая-то фундаментальная вещь, по которой я скучаю?

Answer 1

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

В этой функции sizeof(arr) фактически возвращает размер указателя, а не размер массива.

В C специальное правило гласит, что параметр массива фактически настроен на параметр соответствующего типа указателя.

То есть:

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

эквивалентно этому:

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

Чтобы это исправить, добавьте в вашу функцию новый параметр, который принимает размер массива:

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

Answer 2

Первая проблема, как было указано, заключается в том, что функция isort использует оператор указателя sizeof. То, как С обрабатывает массивы, на первый взгляд немного странно. Имя массива является указателем на его первый элемент. Итак, когда вы звоните isort, как это:

int *b = isort(a);

Вы просто помещаете указатель на массив в стек. В определении isort

int *isort(int arr[])

объявляет arr указателем на int, как

int *isort(int *arr)

С еще более запутанным в этом отношении: если бы вы сказали:

int *isort(int arr[17])

переменная arr все еще просто указатель на int... здесь "17" отбрасывается! Даже с этим синтаксисом sizeof(arr) все равно будет размером указателя на int.

В 32-битной системе (ILP32) sizeof(arr) всегда будет равен 4, как бы велик ни был массив.

Следовательно, вам нужно передать размер массива в isort. Хороший общий способ сделать это - определить макрос следующим образом:

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

Это рассчитает количество элементов в массиве любого типа.

Ваша следующая проблема - скорее проблема стиля, чем фактическая ошибка:

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

Это вызывает функцию вставки со ссылкой на "обр". Массив изменяется через эту ссылку, а затем возвращается указатель на этот массив. Это всегда будет тот же самый указатель, который вы отправили в первую очередь, так что это назначение на самом деле ничего не делает, безвредно. Как я уже сказал, проблема стиля, а не ошибки кода.

Последняя проблема заключается в том, что ваша функция isort останавливается на одну короткую позицию (после того, как вы исправили проблему sizeof), поскольку вы перешли от 1 к sizeof-1. Вот исправленная версия:

#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;
}