Loading…
Loading…
Sorts without a single comparison by tallying how often each key appears, then writing the keys back in order — O(n + k).
The largest key is 100, so allocate a tally table of 101 counters — one per possible value.
1void countingSort(int[] arr) {2 int k = 0;3 for (int x : arr) k = Math.max(k, x);4 int[] count = new int[k + 1]; // one counter per key5 for (int x : arr) count[x]++; // tally in one pass6 int pos = 0;7 for (int v = 0; v <= k; v++) // ascending key order8 while (count[v]-- > 0) arr[pos++] = v; // for satellite data, use cumulative counts and place from the right to stay stable9}