Не получается правильно отсортированный массив с сортировкой
В настоящее время я работаю над алгоритмом подсчета сортировки. Я установил два временных массива 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, который он распечатывает правильно. После следующего цикла 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;
Решение
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;
Другие решения
Других решений пока нет …