algorithm
Liczenie Sortuj

Liczenie Sortuj podstawowe informacje

Liczenie sort to algorytm sortowania liczb całkowitych dla kolekcji obiektów, który sortuje według kluczy obiektów.

Kroki

1. Skonstruuj działającą tablicę C o rozmiarze równym zakresowi tablicy wejściowej A.
2. Iteruj przez A , przypisując C [x] na podstawie liczby wyświetleń x w A.
3. Przekształć C w tablicę, w której C [x] odnosi się do liczby wartości ≤ x, iterując po tablicy, przypisując każdemu C [x] sumę jego poprzedniej wartości i wszystkich wartości w C, które są przed nim.
4. Iteruj wstecz przez A , umieszczając każdą wartość w nowej posortowanej tablicy B pod indeksem zapisanym w C. Odbywa się to dla danego A [x] poprzez przypisanie B [ C [ A [x]]] do A [x] i zmniejszenie C [ A [x]] na wypadek, gdyby w oryginalnej nieposortowanej tablicy były zduplikowane wartości.

Przykład sortowania zliczającego

Przestrzeń pomocnicza: O(n+k)
Złożoność czasu: Najgorszy przypadek: O(n+k) , Najlepszy przypadek: O(n) , Średni przypadek O(n+k)

Implementacja Psuedocode

Ograniczenia:

1. Dane wejściowe (tablica do posortowania)
2. Liczba elementów na wejściu (n)
3. Klucze w zakresie 0..k-1 (k)
4. Liczba (tablica liczb)

Pseudo kod:

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

Implementacja C #

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