Ошибка сегментации сортировки подсчета в C

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

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

void sort(int values[], int n)
{

    //create array of finite size (65536)
    int countArray[INT_MAX];

    //create array to eventually store sorted values
    int sortedValues[n];

    //loop through unsorted values to increment countArray index for each occurrence
    for(int i = 0; i < n; i++) {
        countArray[ values[i] ] += 1;
    }


    //starting index for sortedValues[]
    int sortedIndex = 0;

    //loop until we've reached the end of sortedValues[]
    while(sortedIndex < n) {

        //loop through each index value of countArray
        //j represents the value
        for(int j = 0; j < INT_MAX; j++) {

            //how many times does the index of countArray occur in values[]?
            int c = countArray[j];

            //only add index j as a value to sortedValues[] if it appears in values[]
            while(c > 0) {

                //append j to sortedValues[]
                //--SEGMENTATION FAULT OCCURS ON THE LINE BELOW--
                sortedValues[sortedIndex] = j;

                //decrease the count of countArray[j] once value appended to sortedValues[]
                c -= 1;

                //move to next index of sortedValues[]
                sortedIndex += 1;
            }
        } 
    }
    return;
}

c cs50 segmentation-fault counting-sort
person Finesse Upscale    schedule 04.05.2017    source источник
comment
Проверьте область действия некоторых массивов в зависимости от того, где вы их объявили.   -  person nfproductions    schedule 04.05.2017
comment
Вы никогда не инициализировали countArray. Это может привести к тому, что c будет чем угодно. Что может привести к тому, что sortedIndex перейдет к любому значению (включая отрицательное)   -  person Ajay Brahmakshatriya    schedule 04.05.2017
comment
Вы не можете передать переменную как размер массива, как вы сделали в int sortedValues[n];, вы должны выделить массив, используя int* sortedValues = malloc(sizeof(int)*n);, а затем использовать free(sortedValues); для освобождения выделенной памяти.   -  person Ahmed Akhtar    schedule 04.05.2017
comment
Какой смысл присваивать sortedValues ​​​​в цикле, если ему будет присвоено одно и то же значение?   -  person Ajay Brahmakshatriya    schedule 04.05.2017
comment
У вас также есть ошибка в логике вашей программы. Вам не нужен отдельный цикл для sortedIndex.   -  person Ahmed Akhtar    schedule 04.05.2017
comment
Интересно, ваш комментарий указывает, что вы считаете, что INT_MAX равен 16 битам (и, следовательно, sizeof(int) == 2)? В наше время такое редко встретишь.   -  person Code4aliving    schedule 04.05.2017
comment
@BradBales OP, вероятно, означает, что данные, переданные в его функцию, не превышают 2 ^ 16. Я подумал то же самое, когда увидел эту строку, но потом подумал, что 16-битные int являются как отрицательными, так и положительными, поэтому логика сломается.   -  person Sergey Kalinichenko    schedule 04.05.2017
comment
@dasblinkenlight: Спасибо ... Я только что увидел, что он использует макрос INT_MAX, который будет установлен на максимальное значение int, как его увидит компилятор C. Мне просто показалось любопытным, что он разрабатывает систему с 16-битным int; Я думал, что я единственный, кто до сих пор разрабатывает в такой среде (IBM 4690, ну, теперь Toshiba) :)   -  person Code4aliving    schedule 04.05.2017
comment
@AhmedAkhtar C поддерживает массивы переменной длины.   -  person Ajay Brahmakshatriya    schedule 04.05.2017
comment
@BradBales 16-битное целое число распространено во встроенных процессорах. 100 миллионов в год в 2016 году   -  person chux - Reinstate Monica    schedule 04.05.2017
comment
@chux: Спасибо - вау, я этого не знал, я ценю информацию.   -  person Code4aliving    schedule 04.05.2017
comment
Спасибо за вашу помощь всем! Другая ошибка заключалась в том, что код уменьшал переменную c перед увеличением переменной sortedIndex, что означает, что функция вышла из цикла (1) после установки значения values[sortedIndex], но до (2) перехода к следующему sortedIndex.   -  person Finesse Upscale    schedule 06.05.2017

Ответы (2)


arrow_upward
5
arrow_downward

Вам нужно инициализировать countArray элементов нулем, чтобы исправить сбой:

int countArray[INT_MAX] = {0};

Однако ваша функция по-прежнему бесполезна, потому что она помещает отсортированные числа в локальный массив, который никогда не выходит за пределы функции. Чтобы исправить это, удалите массив sortedValues и вместо этого используйте исходный массив values для вывода:

values[sortedIndex] = j;

Теперь вызывающий объект увидит, что массив, который он передал в вашу функцию, возвращается отсортированным.

Примечание. Внешний цикл while(sortedIndex < n) безвреден, но бесполезен, потому что цикл for гарантирует, что sortedIndex точно равно n. Вы должны удалить цикл while из своего кода.

person Sergey Kalinichenko    schedule 04.05.2017

arrow_upward
1
arrow_downward

Как я уже говорил ранее, вам не нужен отдельный цикл для sortedIndex.

И, как предложил @dasblinkenlight, вам не нужно создавать локальный массив sortedValue для хранения отсортированных значений, вместо этого вы можете отсортировать массив values на месте.

Кроме того, вам нужно инициализировать countArray всеми нулями, чтобы избежать индексации мусорных значений.

Вот код:

void sort(int values[], int n)
{
    //create array of finite size (65536)
    int countArray[INT_MAX] = {0};

    //loop through unsorted values to increment countArray index for each occurrence
    for(int i = 0; i < n; i++) {
        countArray[ values[i] ] += 1;
    }

    //starting index for sortedValues[]
    int sortedIndex = 0;

   //loop through each index value of countArray
   //j represents the value
   for(int j = 0; j < INT_MAX; j++) {

    //how many times does the index of countArray occur in values[]?
    int c = countArray[j];

    //only add index j as a value to sortedValues[] if it appears in values[]
    while(c > 0) {
     //append j to sortedValues[]
     values[sortedIndex] = j;

     //decrease the count of countArray[j] once value appended to sortedValues[]
     c -= 1;

     //move to next index of sortedValues[]
     sortedIndex += 1;
    }
   }
}
person Ahmed Akhtar    schedule 04.05.2017