Counting Sort
Counting sort is a non-comparison-based sorting algorithm that works by counting the occurrences of each distinct element. It is efficient when the range of input is small. Time O(n + k) where k is range of values, space O(k). Stable when implemented carefully.
Java implementation:
public static void countingSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int range = max - min + 1;
int[] count = new int[range];
int[] output = new int[arr.length];
for (int num : arr) count[num - min]++;
for (int i = 1; i < range; i++) count[i] += count[i - 1];
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
System.arraycopy(output, 0, arr, 0, arr.length);
}
Two Minute Drill
- Counting sort: O(n + k) time, O(k) space.
- Non-comparison sort; works best for small integer ranges.
- Stable if implemented correctly.
- Used as subroutine in radix sort.
Need more clarification?
Drop us an email at career@quipoinfotech.com