Почему эта сортирующая сортировка возвращает ввод вместо отсортированной таблицы?

Question

Я пишу счетную сортировку в C. N - это количество элементов в таблице, которые должны быть отсортированы, k - это максимальное значение, которое может иметь любой из этих элементов. Однако этот код оставляет меня с той же таблицей, что и входные данные. Что не так?

void countingSort(int *tab, int n, int k) {
    int *counters = (int *)malloc(k * sizeof(int));
    int *result = (int *)malloc(n * sizeof(int*));
    for (int i = 0; i < k; i++) {
        counters[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        counters[tab[i]]++;
    }
    int j = 0;
    for (int i = 0; i < k; i++) {
        int tmp = counters[i];
        while (tmp--) {
            result[j] = i;
            j++;
        }
    }
    tab = result;
}

Answer 1

В вашем коде есть некоторые проблемы:

• int *result = (int *)malloc(n * sizeof(int*)); использует неправильный размер.Тип элемента массива - int, а не int*.Вы должны написать:

  int *result = (int *)malloc(n * sizeof(int));
  

  или лучше:

  int *result = (int *)malloc(n * sizeof(*result));
  

  и обратите внимание, что приведение в C бесполезно, в отличие от C ++, где оно обязательно:

  int *result = malloc(n * sizeof(*result));
  

• вы можете избежать дополнительного цикла инициализации, используя calloc():

  int *counters = calloc(n, sizeof(*counters));
  

• серьезная проблема: массив результатов никогда не возвращается вызывающей стороне: tab = result; просто изменяет значение аргумента, а не переменную вызывающего.Вместо этого вы должны использовать массив tab для непосредственного хранения результатов.

• вы не освобождаете массивы, что приводит к утечкам памяти.

• вы не проверяете на успешность выделения, вызывая неопределенное поведение, если память не доступна.Вы должны вернуть статус ошибки, указывающий на эту потенциальную проблему.

Вот исправленная версия:

// assuming all entries in tab are > 0 and < k
int countingSort(int *tab, int n, int k) {
    int *counters = calloc(k, sizeof(*counters));
    if (counters == NULL)
        return -1;
    for (int i = 0; i < n; i++) {
        counters[tab[i]]++;
    }
    int j = 0;
    for (int i = 0; i < k; i++) {
        int tmp = counters[i];
        while (tmp--) {
            tab[j++] = i;
        }
    }
    free(counters);
    return 0;
}

Answer 2

Вы передаете вкладку функции указателем.Однако вам нужно изменить не значение, а адрес переменной.Так что вы должны передать адрес указателя countingSort.

void countingSort(int **tab, int n, int k)