Почему я получаю ошибку C6385 в моей сортировке по основанию - PullRequest
Новая
       44

Почему я получаю ошибку C6385 в моей сортировке по основанию

0 голосов
/ 19 марта 2020

Я пытаюсь написать свою собственную версию сортировки radix, чтобы лучше понять алгоритм. Проблема в том, что в первом внутреннем для l oop ("j") я получаю ошибку C6385 в VS. Я понятия не имею, как перефразировать эту строку, чтобы она заработала. Что я делаю здесь не так?

Предупреждение:

предупреждение C6385: Чтение неверных данных из 'countQueues': читаемый размер составляет '400' байтов, но '4000' байты могут быть прочитаны. 


void radixSort(int arr[], int arraySize)
{
    int countDigits = GetMax(arr, arraySize);   //max number of digits
    queue<int> countQueues[10];
    int modulo = 1;

    for (int i = 0; i < countDigits; i++)
    {
        modulo *= 10;
        for (int j = 0; j < arraySize; j++)     //store the values in the queues
        {
            countQueues[arr[j] % modulo].push(arr[j]);  //error here
        }


        for (int k = 0; k < 10; k++)        // move them back in the array
        {
            while (!countQueues[k].empty())
            {
                arr[i] = countQueues[k].front();
                countQueues[k].pop();
            }
        }
    }
}

1 Ответ

1 голос
/ 20 марта 2020

Рассмотрим вторую итерацию первой l oop, когда по модулю = 100. Тогда эта строка кода: 

            countQueues[arr[j] % modulo].push(arr[j]);  //error here

может пытаться получить доступ к countQueues [до 99], но countQueues имеет размер 10.

Эта проблема связана с попыткой сначала реализовать радикальную сортировку наиболее значимых ди git. 1-я итерация использует 10 очередей, 2-я итерация - 100 очередей, 3-я итерация - 1000 очередей ..., которые можно упростить с помощью рекурсии, но при этом потребуется много места, 10 будет увеличено до мощности countDigits.

Реализация Наименьшее значение di git радикальной сортировки сначала позволяет избежать этой проблемы. Можно использовать матрицу [countDigits] [10]. Начальный проход генерирует счетчики и сохраняет их в матрице, где matrix [i] [] - это массив из 10 счетчиков для числа вхождений каждого di git, от 0 до 9. Счетчик конвертируется в начальные индексы для каждая логическая ячейка матрицы [i]. Затем радикальная сортировка выполняется в проходах countDigits, сначала наименее значащая цифра / корзина.

...