В настоящее время я работаю над алгоритмом сортировки подсчетом. Я создал два временных массива 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;
int C[k + 1];
не является допустимым C++. ВЛА нет. Вместо этого вы можете использовать std::vector. - person n. 1.8e9-where's-my-share m.   schedule 18.10.2017