Radix сортировка не сортируется должным образом, когда дано много чисел - PullRequest
Новая
       48

Radix сортировка не сортируется должным образом, когда дано много чисел

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

Я должен реализовать сортировку Binary Radix для своего задания. Хотя я заставил его работать, он перестает правильно сортировать (на самом деле не сортирует их), как только он достигает большего числа чисел (обычно 300+). Кто-нибудь знает, в чем проблема? 

vector<unsigned char> A; //gets input from file that we have been given, containing 1000 numbers
vector<unsigned char> C(2);
vector<unsigned char> B(A.size());

for (int i = 0; i < A.size(); i++) {
    B.push_back(0);
}

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

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

    C[1] += C[0];

    for (int j = A.size() - 1; j >= 0; j--) {
        B[--C[(int)(A[j] >> k) & 1]] = (int)A[j];
    }

    std::swap(A, B);
}

После некоторого тестирования кажется, что ограничение составляет 256 номеров. Поэтому, когда число превышает 256, алгоритм больше не может его сортировать

1 Ответ

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

Посмотрите на объявления и использование 

vector<unsigned char> C(2);
B[--C[(int)(A[j] >> k) & 1]]

Любой элемент C[i] содержит N от 0 до 255. Таким образом, индекс --C[(int)(A[j] >> k) & 1] всегда меньше 255.

Решение: 

vector<size_t> C(2);
...