Подсчет ошибки сортировки сортировки в C

Question

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

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

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

Answer 1

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

int countArray[INT_MAX] = {0};

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

values[sortedIndex] = j;

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

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

Answer 2

Как я уже говорил ранее, вам не нужен отдельный цикл для 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;
    }
   }
}