algorithm
Räknar sortering

Räknar sortera basinformation

Räkningssortering är en helhetssorteringsalgoritm för en samling objekt som sorteras efter objekternas nycklar.

Steg

1. Konstruera en arbetsgrupp C som har storlek som är lika med intervallet för ingångsgruppen A.
2. Iterera till och med A , tilldela C [x] baserat på antalet gånger x dykt upp i A.
3. Förvandla C till en matris där C [x] hänvisar till antalet värden ≤ x genom att iterera igenom matrisen, tilldela varje C [x] summan av dess tidigare värde och alla värden i C som kommer före den.
4. Iterera bakåt genom A , placera varje värde i en ny sorterad matris B vid indexet registrerat i C. Detta görs för en given A [x] genom att tilldela B [ C [ A [x]]] till A [x], och minska C [ A [x]] om det fanns duplikatvärden i den ursprungliga osorterade matrisen.

Exempel på räkningssortering

Hjälputrymme: O(n+k)
Tidskomplexitet: Värsta fall: O(n+k) , Bästa fall: O(n) , Medelfall O(n+k)

Psuedocode-implementering

begränsningar:

1. Input (en matris som ska sorteras)
2. Antal element i ingången (n)
3. Nycklar i intervallet 0..k-1 (k)
4. Räkna (ett antal nummer)

pseudo:

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

C # Implementering

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;
    }
}