/
CountingSort.java
60 lines (56 loc) · 1.92 KB
/
CountingSort.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package com.jwetherell.algorithms.sorts;
/**
* Counting sort is an algorithm for sorting a collection of objects according
* to keys that are small integers; that is, it is an integer sorting algorithm.
* It operates by counting the number of objects that have each distinct key
* value, and using arithmetic on those counts to determine the positions of
* each key value in the output sequence.
* <p>
* Family: Counting.<br>
* Space: An Array of length r.<br>
* Stable: True.<br>
* <p>
* Average case = O(n+r)<br>
* Worst case = O(n+r)<br>
* Best case = O(n+r)<br>
* <p>
* NOTE: r is the range of numbers (0 to r) to be sorted.
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Counting_sort">Counting Sort (Wikipedia)</a>
* <br>
* @author Justin Wetherell <phishman3579@gmail.com>
*/
public class CountingSort {
private CountingSort() { }
public static Integer[] sort(Integer[] unsorted) {
int maxValue = findMax(unsorted);
int[] counts = new int[maxValue + 1];//counts number of elements
updateCounts(unsorted, counts);
populateCounts(unsorted, counts);
return unsorted;
}
//finding maximum value in unsorted array
private static int findMax(Integer[] unsorted) {
int max = Integer.MIN_VALUE;//assume minimum value(-2147483648) of interger is maximum
for (int i : unsorted) {
if (i > max)
max = i;
}
return max;
}
//Incrementing the number of counts in unsorted array
private static void updateCounts(Integer[] unsorted, int[] counts) {
for (int e : unsorted)
counts[e]++;
}
private static void populateCounts(Integer[] unsorted, int[] counts) {
int index = 0;
for (int i = 0; i < counts.length; i++) {
int e = counts[i];
while (e > 0) {
unsorted[index++] = i;
e--;
}
}
}
}