Сортировка подсчётом - C (СИ)
Формулировка задачи:
Добрый вечер! Помогите, пожалуйста, найти ошибку в коде. Приведенный ниже код выводит неверный результат.
Сортировка подсчетом.
P.S. вот тут доступно объясняется про сортировку подсчетом.
/** * Используются следующие обозначения: * a[1..n] - входная последовательность; * c[1..k] - вспомогательный массив из k элементов; * b[1..n] - выходная отсортированная последовательность. */ void counting_sort(int a[], int n) { int i; int min, max; /* минимальный и максимальный элементы из входного массива a[1..n] */ int k; /* кол-во элементов в вспомогательном массиве с[1..k] */ int *c; /* c[1..k] - вспомогательный массив из k элементов */ int *b; /* b[1..n] - выходная отсортированная последовательность */ /* Находим макс. и мин. элементы */ min = max = a[0]; for(i = 1; i < n; i++) { if (a[i] < min) min = a[i]; else if (a[i] > max) max = a[i]; } k = max - min + 1; c = malloc(sizeof(int)); b = malloc(sizeof(int)); /* Заполняем вспомогательный массив нулями */ for(i = 0; i < k; i++) c[i] = 0; /* Заполняем выходной массив нулями */ for(i = 0; i < n; i++) b[i] = 0; /* Заполняем вспомогательный массив частотами (!!!!) Предполагаю, что ошибка тут! */ for(i = 0; i < n; i++) c[ a[i] - min ]++; /* Находим частичные суммы */ for(i = 1; i < k; i++) { c[i+1] = c[i] + c[i+1]; } /** * После этого каждый элемент a[i] из входного массива помещается * в выходной массив b на позицию, равную значению элемента c[a[i]] */ for(i = 0; i < n; i++) { b[ c[ a[i]-1 ]-1 ] = a[i]; c[ a[i]-1 ]--; } free(b); free(c); }
Решение задачи: «Сортировка подсчётом»
textual
Листинг программы
while(s != '.') { if(s == ' ') i++; else array[i] = array[i]*10 + atoi(&s); s = fgetc(f); }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д