# Counting Sort

- Counting Sort Algorithm
- Counting Sort Example
- Counting Sort Algorithm Implementation
- Counting Sort Algorithm Complexity

Counting sort is a non-comparative sorting algorithm. It sorts an array by counting occurrences of each unique element. It partially hashes the count of unique elements and then performs calculations to find the index of each element in the final, sorted array. It is quite a fast algorithm but unsuitable for large datasets. It is used as a subroutine inside radix sort.

## Counting Sort Algorithm

Let us assume that we have an unsorted array `A[]`

containing `n`

elements.

##### Find out the maximum element

`max`

and minimum element`min`

inside the array.##### Initialize an array

`count`

of length`max-min+1`

with all elements set to`0`

.##### Initialize an array

`output`

of size same as the input array`A`

.##### Store the count of all elements inside the

`count`

array by subtracting`min`

and using the difference as the index.##### Cumulate the sum of elements inside the

`count`

array. The`count`

array now holds the position of each element in the sorted array.##### Starting from the end take elements from

`A`

and do the following:##### Compute elements index as

`count[A[i]-min]-1`

and store`A[i]`

in`output`

.##### decrease

`count[A[i]-min]`

by`1`

.##### Store the

`output`

elements back to original array`A`

.

## Counting Sort Example

Suppose we have the array: `(6, 3, 2, 7, 4, 5, 4, 2)`

. We will sort it using the counting sort algorithm.

`maxm`

= 7`minm`

= 2`range`

= 6`count`

and`output`

are initialized with zeros.

index | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|

value | 0 | 0 | 0 | 0 | 0 | 0 |

`count`

array after computing the count of all the elements.

index | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|

value | 2 | 1 | 2 | 1 | 1 | 1 |

`count`

array after cumulation of the sum of elements.

index | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|

value | 2 | 3 | 5 | 6 | 7 | 8 |

- First Iteration:
`A[7]=2`

`count` |
`1 3 5 6 7 8` |

`output` |
`0 2 0 0 0 0 0 0` |

- Second Iteration:
`A[6]=4`

`count` |
`1 3 4 6 7 8` |

`output` |
`0 2 0 0 4 0 0 0` |

- Third Iteration:
`A[5]=5`

`count` |
`1 3 4 5 7 8` |

`output` |
`0 2 0 0 4 5 0 0` |

- Fourth Iteration:
`A[4]=4`

`count` |
`1 3 3 5 7 8` |

`output` |
`0 2 0 4 4 5 0 0` |

- Fifth Iteration:
`A[3]=7`

`count` |
`1 3 3 5 7 7` |

`output` |
`0 2 0 4 4 5 0 7` |

- Sixth Iteration:
`A[2]=2`

`count` |
`0 3 3 5 7 7` |

`output` |
`2 2 0 4 4 5 0 7` |

- Seventh Iteration:
`A[1]=3`

`count` |
`0 2 3 5 7 7` |

`output` |
`2 2 3 4 4 5 0 7` |

- Eighth Iteration:
`A[0]=6`

`count` |
`0 2 3 5 6 7` |

`output` |
`2 2 3 4 4 5 6 7` |

Finally, we store the `output`

array inside `A`

and get the sorted array - `2, 2, 3, 4, 4, 5, 6, 7`

.

## Counting Sort Algorithm Implementation

```
#include<iostream>
using namespace std;
const int N = 10;
int maxm(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
return max;
}
int minm(int arr[], int n) {
int min = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
}
return min;
}
void countingSort(int arr[], int n) {
int min = minm(arr, n);
int max = maxm(arr, n);
int range = max - min + 1;
int count[range]={};
int output[n];
for (int i = 0; i < n; i++)
count[arr[i] - min]++;
for (int i = 1; i < range; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
int main() {
int n = 7;
int arr[7] = {3, 5, 1, 1, 4, 2, 1};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
countingSort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
```

This implementation also works for negative numbers.

## Counting Sort Algorithm Complexity

### Time Complexity

- Average Case

Counting Sort iterates through all the `n`

items twice and iterates through the `count`

array once. So, it has a time complexity of `O(n + b)`

where `b`

is the range of input. Since `b`

is often small, the counting sort’s time complexity is said to be of the order of [Big Theta]: `O(n)`

.

- Worst Case

The worst-case time complexity is [Big O]: `O(n)`

.

- Best Case

The best-case time complexity is [Big Omega]: `O(n)`

. It is the same as the worst-case time complexity.

### Space Complexity

Space Complexity for the counting sort algorithm is `O(n+b)`

, where `b`

is the range of input. It comes from `count`

&`output`

arrays. Sometimes `b`

can be larger than `n`

, but if b is small, the time complexity is said to be of `O(n)`

.