algorithm
Counting Sort

Counting Sort Basic Information

Zählsortierung ist ein ganzzahliger Sortieralgorithmus für eine Sammlung von Objekten, die nach den Schlüsseln der Objekte sortiert wird.

Schritte

1. Konstruieren Sie ein Arbeitsarray C , dessen Größe dem Bereich des Eingangsarrays A entspricht .
2. Durchlaufen Sie A und weisen Sie C [x] zu, je nachdem, wie oft x in A angezeigt wurde.
3. Transformieren Sie C in ein Array, wobei C [x] auf die Anzahl der Werte ≤ x verweist, indem Sie das Array durchlaufen und jedem C [x] die Summe seines vorherigen Werts und aller davor liegenden Werte in C zuweisen.
4. Durchlaufen Sie rückwärts durch A , und platzieren Sie jeden Wert in einem neuen sortierten Array B am in C aufgezeichneten Index. Dies geschieht für ein gegebenes A [x], indem B [ C [ A [x]]] A [x] zugewiesen wird und C [ A [x]] dekrementiert wird, falls doppelte Werte im ursprünglichen unsortierten Array vorhanden waren.

Beispiel für das Zählen der Sortierung

Hilfsraum: O(n+k)
Zeitkomplexität: Schlechtester Fall: O(n+k) , Bester Fall: O(n) , Durchschnittlicher Fall O(n+k)

Psuedocode-Implementierung

Einschränkungen:

1. Eingabe (ein zu sortierendes Array)
2. Anzahl der Elemente in der Eingabe (n)
3. Tasten im Bereich von 0..k-1 (k)
4. Anzahl (ein Array von Zahlen)

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 # -Implementierung

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