Counting Sort
Counting sort is a non-comparison based sorting algorithm that works by determining, for each element in an input array, the number of elements that are less than it. This information is then used to place the element in its correct position in the output array. The algorithm has a linear time complexity of O(n+k), where n is the number of elements in the input array and k is the range of values in the input array.
1//int [] A = {2, 5, 3, 0, 2, 3, 0, 3};
2int [] A = {6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2};
3int []B = new int[A.length];
4
5void setup() {
6 countingSort(A);
7 noLoop();
8}
9
10void countingSort(int arr[]) {
11
12 int k = arr.length;
13
14 // The output character array that will have sorted arr
15 int output[] = new int[k];
16
17 // Create a count array to store count of inidividual
18 // characters and initialize count array as 0
19 int count[] = new int[256];
20 for (int i=0; i<256; ++i)
21 count[i] = 0;
22
23 // store count of each character
24 for (int i=0; i<k; ++i) {
25 ++count[arr[i]];
26 print(count[i]);
27 }
28 // Change count[i] so that count[i] now contains actual
29 // position of this character in output array
30 for (int i=1; i<=255; ++i) {
31 count[i] += count[i-1];
32 }
33 println("");
34 // Build the output character array
35 for (int i = 0; i<k; ++i)
36 {
37 output[count[arr[i]]-1] = arr[i];
38 print(output[i]);
39 --count[arr[i]];
40 }
41 println("");
42 // Copy the output array to arr, so that arr now
43 // contains sorted characters
44 for (int i = 0; i<k; ++i) {
45 arr[i] = output[i];
46 print(output[i]);
47 }
48}