algorithm Counting Sort Counting Sort Basic Information
Example
Counting sort is an integer sorting algorithm for a collection of objects that sorts according to the keys of the objects.
Steps
- Construct a working array C that has size equal to the range of the input array A.
- Iterate through A, assigning C[x] based on the number of times x appeared in A.
- Transform C into an array where C[x] refers to the number of values ≤ x by iterating through the array, assigning to each C[x] the sum of its prior value and all values in C that come before it.
- Iterate backwards through A, placing each value in to a new sorted array B at the index recorded in C. This is done for a given A[x] by assigning B[C[A[x]]] to A[x], and decrementing C[A[x]] in case there were duplicate values in the original unsorted array.
Example of Counting Sort
Auxiliary Space: O(n+k)
Time Complexity: Worst-case: O(n+k), Best-case: O(n), Average-case O(n+k)
