Sortownie przez zliczanie

Zasadniczo idea sortowania przez zliczanie jest wyjątkowo prosta - polega na sprawdzeniu ile wystąpień danego klucza występuje w sortowanej tablicy. Złożoność obliczeniowa tego algortymu wynosi O(n+k) dla n będącym wielkością zbioru i k liczbą różnych jego elementów. Wymaga O(k) dodatkowej pamięci w wersji niestabilnej, lub O(n+k) pamięci w wersji stabilnej.

Działanie algorytmu

Dla ułatwienia indeksy w tablicy wejściowej( A[]) numerujemy od 1 do n. Tablica C[] dla ułatwienia powinna być wypełniona zerami. Będzie nam ona służyła, by zapisać ile razy w tablicy A wystąpił klucz "i" i zapisanie tej liczby w komórce C[i]. Następnie w tablicy C Szukamy klucza który jako pierwszy został odnaleziony np. 3 i patrzymy ile razy został znaleziony - dostajemy np. 2, w następnej komórce wpisujemy sumę jej, oraz poprzedniej (niczym w ciągu Fibonacciego). Powstałe liczby odzwierciedlaja pozycje na ktorych konczyc sie maja dane klucze. Następnie wpisujemy do tablicy B[j] gdzie j=C[k] gdzie k=A[n…1] - zmniejszajac przy tym wartość C[k] o 1. Jako pomoc przy debuggowaniu dodam że warto na końcu wypisać tablicę C - może to pomóc w znalezieniu błędu.

Implementacja

Zasadniczo nie powinnienem wam wrzucać gotowego kodu, ale akurat ten na nic się wam nie przyda (w obecnej formie) - bo zadanie z numerami PESEL będzie wymagać radix-sorta który to używa zmienionej wersji count-sorta.
Hint: Do nieco innej pozycji będziemy się odnośić w tablicy C[] - której rozmiar w zadaniu PESEL nie będzie większy niż 10.

void zliczaj(int A,int B,int k,int n);              //funkcja pobiera tablice wejsciowa, wyjsciowa, k - górna granica wielkosci danych, n - rozmiar tablicy wejsciowej
{
     int C[max rozm. danych];
     for(int i=0;i<=k;i++)
          C[i]=0;                                //zerowanie tablicy z pomocniczej
     for(int j=1;j<=n;j++)
          C[A[j]]=C[A[j]] + 1;
     for(int i=1;i<=k;i++)
          C[i]=C[i] + C[i-1]
     for(int j=n;j>=1;j--)                    //prosciej jest wpisywac liczby od konca, majac taka tablice C
     {
          B[C[A[j]]] = A[j];
          C[A[j]]=C[A[j]]-1;
     }
}

w przeciwienstwie do innych algorytmow sortujacych stabilnie - ten jest dość prosty, jednak nie nadaje się w takiej postaci do sortowania dużych liczb.