Реализую сортировку подсчетом. Возникла проблема в том, что моя реализация не обрабатываем один элемент массива - наибольший. Вместо него в результате выводится мусор. Вот код:
void CountingSort(int a[], int b[], int len, int k){
int *c = new int[k + 1]; //Временное рабочее хранилище c[0..k]
for(int i = 0; i < (k + 1); i++)
c[i] = 0;
for(int j = 0; j < len; j++)
c[a[j]]++;
//В c[i] хранится кол-во элементов, равных i
for(int i = 1; i < (k + 1); i++)
c[i] = c[i] + c[i - 1];
//В c[i] хранится кол-во элементов, не превосходящих i
for(int j = len - 1; j >= 0; j--){
b[c[a[j]]] = a[j];
c[a[j]]--;
}
delete[] c;
}
Я понимаю этот алгоритм так. На вход подаются числа большие или равные нулю, но не превосходящие число k. Это значит, что можно создать вспомогательный массив c[0..k], в котором можно хранить количество каждого из чисел последовательности. Это возможно, потому что все числа от 0 до k, и их можно использовать в качестве индексов.
Во втором цикле считаем количество каждого из чисел.
В третьем вычисляем количество чисел, не превосходящих i. Т.к. все индексы массива c идут по порядку и каждый соответствует одному из чисел в последовательности, то понятно, что для вычисления количества чисел, не превосходящих i (знак >=), надо к к количеству числа i прибавить количество числа i - 1. Начиная со второго элемента, постепенно мы обработаем таким образом все ячейки.
А вот последний цикл мне совсем непонятен. Какую логику реализует этот код? Каким образом все это работает?
Вызывающая функция:
int main(void){
int v[10] = {9, 0, 3, 4, 1, 2, 7, 8, 5, 6};
int u[11];
CountingSort(v, u, 10, 9);
for(int i = 0; i < 10; i++)
std::cout << u[i] << ' ';
std::cin >> v[0]; //pause
return 0;
}
Также на основе этого алгоритма надо решить такую задачу: "Модифицировать процедуру сортировки подсчетом для сортировки по отдельному (младшему, второму с конца и т.д.) байту числа."
Как выделить байты - понятно. Берем маску 1111 1111b и, сдвигая ее, вырезаем необходимые биты. А как приспособить сортировку подсчетом к такой задаче, я совсем не понимаю. Что подавать на вход алгоритму? Как сортировать по байтам?