When I was reading about counting sort in Introduction to Algorithms for the first time, I stopped reading after the step where they calculate the number of each element in the input array. It's the first thing we do after allocating an auxiliary array.
I was sure the algorithm would look like this:
public static int[] countingSort2(int[] input, int k) {
// 0 <= input[i] < k
int[] result = new int[input.length];
int[] auxiliary = new int[k];
for (int j = 0; j < input.length; j++) {
auxiliary[input[j]] = auxiliary[input[j]] + 1;
}
int resultIndex = 0;
for (int i = 0; i < auxiliary.length; i++) {
if (auxiliary[i] != 0) {
for (int m = 0; m < auxiliary[i]; m++) {
result[resultIndex++] = i;
}
}
}
return result;
}
But of course, the canonical implementation is different:
public static int[] countingSort(int[] a, int k) {
int c[] = new int[k];
for (int i = 0; i < a.length; i++)
c[a[i]]++;
for (int i = 1; i < k; i++)
c[i] += c[i - 1];
int b[] = new int[a.length];
for (int i = a.length - 1; i >= 0; i--)
b[--c[a[i]]] = a[i];
return b;
}
I wonder why they needed to fill the auxiliary array again and then put elements of the input array to the output array.
Carobjects. You could sort them using this algorithm by mileage or color or any other attribute that is reducible to an integer value. $\endgroup$