Я реализовал алгоритм сортировки отсчетов из псевдокода. В псевдокоде последний цикл уменьшается C[A[j]]
после первого прохода. Это смещало все вправо, поэтому я отлаживал и уменьшал перед первым проходом, чтобы получить правильные результаты. Но я не вижу причины, кроме того, что это работает, почему я должен уменьшать до, а не после.
Вот результат, когда я уменьшаю после:
10 1 0 6 8 3 2 0 9 4
0 0 0 1 2 3 4 6 8 9
И когда я снимаю раньше:
10 1 0 6 8 3 2 0 9 4
0 0 1 2 3 4 6 8 9 10
Очевидно, поскольку изначально все было смещено вправо, я переместил все влево, но почему бы не быть в правильном положении в первую очередь?
int* counting_sort(int A[], int size, int k)
{
int* B = new int[size];
int* C = new int[k+1];
for(int i = 0; i <= k; i++)
C[i] = 0;
for(int j = 0; j < size; j++) {
C[A[j]]++;
}
for(int i = 1; i <= k; i++) {
C[i] += C[i-1];
}
//print(C,k+1);
for(int j = size-1; j >= 0; j--) {
B[--C[A[j]]] = A[j];
}
delete [] C;
return B;
}
for(int j = size-1; j >= 0; j--) {
B[--C[A[j]]] = A[j];
}
эквивалентно:
for(int j = size-1; j >= 0; j--) {
int element = A[j];
int pos = C[element] - 1;
B[pos] = element;
C[element]--;
}
Представьте массив 1 0 1
, Теперь количество элементов будет следующим:
0
— 1 раз
1
— 2 раза
Подготовка приращений позиций рассчитывается по количеству элементов, предшествующих им:
0
— 1
1
— 3
Положение элементов в новом (отсортированном) массиве теперь (count — 1):
положение 0
= 1 — 1 = 0
позиция первой 1
= 3 — 1 = 2
положение второго 1
= 2 — 1 = 1
делая это 0 1 1
,
Других решений пока нет …