algorithm


This draft deletes the entire topic.

expand all collapse all

Examples

  • 0

    Counting sort is an integer sorting algorithm for a collection of objects that sorts according to the keys of the objects.

    Steps

    1. Construct a working array C that has size equal to the range of the input array A.
    2. Iterate through A, assigning C[x] based on the number of times x appeared in A.
    3. 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.
    4. 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

    Counting Sort

    Auxiliary Space: O(n+k)
    Time Complexity: Worst-case: O(n+k), Best-case: O(n), Average-case O(n+k)

  • 0

    Constraints:

    1. Input (an array to be sorted)
    2. Number of element in input (n)
    3. Keys in the range of 0..k-1 (k)
    4. 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
    
  • -1
    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...

Syntax

Syntax

Parameters

Parameters

Remarks

Remarks

Still have a question about Counting Sort? Ask Question

Topic Outline