algorithm
Tellen sorteren

Tellen Sorteer Basisinformatie

Telsortering is een integer sorteeralgoritme voor een verzameling objecten die sorteert op basis van de sleutels van de objecten.

Stappen

1. Construeer een werkarray C met een grootte gelijk aan het bereik van de invoerarray A.
2. Doorloop A en wijs C [x] toe op basis van het aantal keren dat x in A verscheen.
3. Transformeer C in een array waarbij C [x] verwijst naar het aantal waarden ≤ x door de array te doorlopen, waarbij aan elke C [x] de som van de eerdere waarde en alle waarden in C die eraan voorafgaan, wordt toegewezen.
4. Herhaal achteruit door A en plaats elke waarde in een nieuwe gesorteerde array B bij de index die is geregistreerd in C. Dit wordt gedaan voor een gegeven A [x] door B [ C [ A [x]]] toe te wijzen aan A [x] en C [ A [x]] te verlagen in het geval dat er dubbele waarden in de oorspronkelijke ongesorteerde array waren.

Voorbeeld van telsortering

Hulpruimte: O(n+k)
Tijd Complexiteit: Worst-case: O(n+k) , Best-case: O(n) , Average-case O(n+k)

Implementatie van Psuedocode

beperkingen:

1. Input (een te sorteren array)
2. Aantal elementen in invoer (n)
3. Toetsen in het bereik van 0..k-1 (k)
4. Count (een reeks getallen)

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

C # Implementatie

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