Не удается получить правильный отсортированный массив с сортировкой подсчета

В настоящее время я работаю над алгоритмом сортировки подсчетом. Я создал два временных массива C и B. C должен подсчитать, сколько раз появляется число в исходном массиве. Затем он использует элементы в C, чтобы поместить элементы в A (исходный массив) в правильное место в B. Моя функция countingSort выводит C после каждого цикла, чтобы убедиться, что в ней есть правильные значения (что она и делает, я тестирую ее с небольшим размером выборки). Проблема возникает, когда я иду вставлять элементы A в B с помощью C.

Вот моя функция для countingSort:

Примечание. Я передаю в функцию массив из 10 целых чисел 2 0 3 2 5 4 3 6 10, временный массив B, значение maximum (чтобы я знал, какой размер сделать C) и размер массива A

void countingSort(int A[], int B[], int k, int size){
    int C[k + 1];
    cout << "K: " << k << endl;

    for(int i = 0; i < k + 1; i++){
        C[i] = 0;
    }



    for(int i = 0; i < k + 1; i++){
        cout << C[i] << " ";
    }


    for(int i = 0; i < size; i++){
        C[A[i]] = C[A[i]] + 1;
    }

    cout << endl;


    for(int i = 0; i < k + 1; i++){
        cout << C[i] << " ";
    }


    for(int i = 0; i < k + 1; i++){
        C[i] = C[i] + C[i - 1];
    }


    cout << endl;
    for(int i = 0; i < k + 1; i++){
        cout << C[i] << " ";
    }



    for(int i = size + 1; i > 0; i--){
        B[C[A[i]]] = A[i];
        C[A[i]] = C[A[i]] - 1;
    }


    cout << endl;
    for(int i = 0; i < size; i++){
        cout << B[i] << " ";
    }


}

Как вы можете видеть, я вывожу C после каждого цикла, поэтому после первого цикла он должен показывать, что C равен 0 0 0 0 0 0, что он печатает правильно. После следующего цикла for это C должно быть 2 1 2 2 1 1 1, что также правильно распечатывается. Затем он добавляет элементы C вверх, чтобы получить 2 3 5 7 8 9 10, который также правильно распечатывается. Теперь моя проблема возникает здесь, когда я пытаюсь поместить элементы A в B. Предполагается, что он напечатает 0 0 1 2 2 3 3 4 5 6, но вместо этого печатает 0 0 0 1 0 2 3 3 4 5.

Я пытался поиграть с моими индексами в последнем цикле for, но просто не могу понять, что делает B неправильным. Как я могу решить эту проблему? Моя общая цель — заставить сортировку по количеству работать для случайно сгенерированного массива размером 40 с числами от 1 до 25.

Изменить: Основная функция, где я вызываю countingSort:

int sizeCount1 = 10;
int countOne[10] = {2, 0, 3, 2, 5, 4, 3 ,6, 1, 0};

cout << "Counting Sort Version 1 (Pre Sort)" << endl;

for(int i = 0; i < sizeCount1; i++){
    cout << countOne[i] << " ";
}

cout << endl;


for(int i = 0; i < sizeCount1; i++){
    countTemp[i] = 0;
}



int max = 0;
for(int i = 0; i < sizeCount1; i++){
    if(countOne[i] > max){
        max = countOne[i];
    }
}

cout << "Max: " << max << endl;


countingSort(countOne, countTemp, max, sizeCount1);

cout << endl;

cout << "Counting Sort Version 1 (Post Sort)" << endl;


for(int i = 1; i < 10; i++){
    cout << countTemp[i] << " ";
}

cout << endl << endl;

person zsloan112    schedule 18.10.2017    source источник
comment
Пожалуйста, отредактируйте свой вопрос и предоставьте минимально воспроизводимый пример.   -  person Jabberwocky    schedule 18.10.2017
comment
int C[k + 1]; не является допустимым C++. ВЛА нет. Вместо этого вы можете использовать std::vector.   -  person n. 1.8e9-where's-my-share m.    schedule 18.10.2017
comment
К сожалению, мне запрещено использовать векторы   -  person zsloan112    schedule 18.10.2017
comment
Ограничено использование векторов, но не запрещено использование нестандартных непереносимых конструкций? Вы посещаете интересный урок (с точки зрения энтомологии).   -  person n. 1.8e9-where's-my-share m.    schedule 18.10.2017


Ответы (1)


for(int i = 1; i < k + 1; i++){
    C[i] = C[i] + C[i - 1];
}

В противном случае вы получаете неопределенное поведение.

Также в формировании выходного массива

for(int i = size-1; i >= 0; i--){
    B[C[A[i]]] = A[i];
    C[A[i]] = C[A[i]] - 1;
}

Вы правильно поняли алгоритм. Теперь просто немного обкатайте. Таким образом, вы можете найти такие ошибки в своем коде.

В качестве ОП использовалась 0-indexing. Я использую то же самое в своем ответе

Если вы не можете использовать вектор ..выделите память, используя new. Проверьте ссылку немного для этого.

Другое дело, всякий раз, когда вы выполняете сортировку с подсчетом кода, всегда старайтесь доказать, что вы можете удерживать диапазон во вспомогательных массивах. Это помогает.

Код сортировки подсчета:

void countingSort(int A[], int B[], int k, int size){
    int C[k + 1];
    for(int i = 0; i < k + 1; i++){
        C[i] = 0;
    }
    for(int i = 0; i < size; i++){
        C[A[i]] = C[A[i]] + 1;
    }
    for(int i = 0; i < k + 1; i++){
        C[i] = C[i] + C[i - 1];
    }
    for(int i = size-1; i >= 0; i--){
        B[C[A[i]]] = A[i];
        C[A[i]] = C[A[i]] - 1;
    }
}

основной код

int sizeCount1 = 10;
int countOne[10] = {2, 0, 3, 2, 5, 4, 3 ,6, 1, 0};

cout << "Counting Sort Version 1 (Pre Sort)" << endl;

for(int i = 0; i < sizeCount1; i++){
    countTemp[i] = 0;
}
int max = 0;
for(int i = 0; i < sizeCount1; i++){
    if(countOne[i] > max){
        max = countOne[i];
    }
}

cout << "Max: " << max << endl;


countingSort(countOne, countTemp, max, sizeCount1);
cout << "Counting Sort Version 1 (Post Sort)" << endl;
for(int i = 0; i < 10; i++){
    cout << countTemp[i] << " ";
}

cout << endl << endl;
person user2736738    schedule 18.10.2017
comment
Итак, я изменил этот раздел и все равно получил тот же результат, однако я изменил последний цикл for на for(int i = size; i >= 0; i++) и получил 0 0 0 1 2 2 3 3 4 5, который близок, но имеет дополнительный 0 в начале, а не 6 в конце. - person zsloan112; 18.10.2017
comment
@zsloan112.: i=size-1 Вы повторили один дополнительный раз, поэтому получили лишний 0. Сделайте это из i=size-1 и for(int i = size-1; i >= 0; i--) - person user2736738; 18.10.2017
comment
Как только я изменил его на i = size - 1, я получил ошибку сегментации. - person zsloan112; 18.10.2017
comment
@zsloan112.: Вы должны уменьшить i. Проверить for(int i = size-1; i >= 0; i--) - person user2736738; 18.10.2017
comment
Вот что у меня есть: for(int i = size - 1; i >= 0; i--) - person zsloan112; 18.10.2017
comment
@zsloan112.: Сидя здесь, я не могу отлаживать твой код. Просто используйте отладчик или опубликуйте полный код ... Есть много других причин, по которым ваш код не работает ... Кстати, как n.m. сказал, что вы должны использовать вектор здесь ..VLA не разрешен. - person user2736738; 18.10.2017
comment
Я добавил свою основную функцию в исходный пост - person zsloan112; 18.10.2017
comment
Работает отлично. Спасибо за вашу помощь! - person zsloan112; 18.10.2017