Сортировка подсчётом - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Добрый вечер! Помогите, пожалуйста, найти ошибку в коде. Приведенный ниже код выводит неверный результат. Сортировка подсчетом.
/**
 *  Используются следующие обозначения:
 *  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);
}
P.S. вот тут доступно объясняется про сортировку подсчетом.

Решение задачи: «Сортировка подсчётом»

textual
Листинг программы
while(s != '.')
{
    if(s == ' ')
        i++;
    else
        array[i] = array[i]*10 + atoi(&s);
    s = fgetc(f);
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

12   голосов , оценка 3.583 из 5
Похожие ответы