This draft deletes the entire topic.
expand all
collapse all
Examples
-
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-caseO(n+k)
-
Constraints:
- Input (an array to be sorted)
- Number of element in input (n)
- Keys in the range of 0..k-1 (k)
- Count (an array of number)
Pseudocode:
for x in input: count[key(x)] += 1 total = 0 for i in range(k): oldCount = count[i] count[i] = total total += oldCount for x in input: output[count[key(x)]] = x count[key(x)] += 1 return output
-
-
public class CountingSort { public static void SortCounting(int[] input, int min, int max) { var count = new int[max - min + 1]; var z = 0; for (var i = 0; i < count.Length; i++) count[i] = 0; foreach (int i in input) count[i - min]++; for (var i = min; i <= max; i++) { while (count[i - min]-- > 0) { input[z] = i; ++z; } } } public static int[] Main(int[] input) { SortCounting(input, input.Min(), input.Max()); return input; } }
I am downvoting this example because it is...
Still have a question about Counting Sort?
Ask Question
Topic Outline
Sign up or log in
Save edit as a guest
Join Stack Overflow
Using Google
Using Facebook
Using Email and Password
We recognize you from another Stack Exchange Network site!
Join and Save Draft