Sortowanie przez zliczanie to algorytm liniowy co oznacza, że jego złożoność czasowa wynosi . Polega on na zadeklarowaniu dodatkowej tablicy do której będziemy zliczać wystąpienia poszczególnych wartości, np. ile mamy na liście 0, 1 ... Następny krok polega na analizie wszystkich elementów listy zliczającej. i-tą liczbę na liście wypisujemy tyle razy jaką wartość ma lista pod indeksem i. W ten sposób uzyskujemy posortowaną listę. Jeśli listę zliczającą będziemy przeglądać od lewej do prawej to uzyskamy listę posortowaną rosnącą.
Weźmy przykładowo listę L:={5, 5, 1, 4, 2, 4}. Wiemy, że mamy na niej liczby z zakresu od 1 do 5, dlatego deklarujemy tablicę pomocniczą o długości 5 i zerujemy wszystkie jej wartości:
(pogrubieniem zostały wyróżnione elementy, które są zmieniane w danym kroku)
| Krok | Pobrany element | Lista zliczająca |
|---|---|---|
| przygotowanie | - | {0, 0, 0, 0, 0} |
| #1 | 5 | {0, 0, 0, 0, 1} |
| #2 | 5 | {0, 0, 0, 0, 2} |
| #3 | 1 | {1, 0, 0, 0, 2} |
| #4 | 4 | {1, 0, 0, 1, 2} |
| #5 | 2 | {1, 1, 0, 1, 2} |
| #6 | 4 | {1, 1, 0, 2, 2} |
Teraz przechodzimy do analizy listy zliczającej:
| Krok | Pobrany element | Odpowiada liczbie | Lista wynikowa |
|---|---|---|---|
| przygotowanie | - | - | {} |
| #1 | 1 | 1 | {1} |
| #2 | 1 | 2 | {1, 2} |
| #3 | 0 | 3 | {1, 2} |
| #4 | 2 | 4 | {1, 2, 4, 4} |
| #5 | 2 | 5 | {1, 2, 4, 4, 5, 5} |
W ten sposób uzyskaliśmy posortowaną listę L={1, 2, 4, 4, 5, 5}.
Algorytm sortowania przez zliczania posiada szereg wad, których nie odczuwa się tylko dla niektórych danych:
Niemniej warto pamiętać, że jest to algorytm, który działa w czasie co wpływa na jego wysoką efektywność sortowania. Można go na przykład zastosować do sortowania ocen, albo wyników klasówki.
Będziemy sortować listę liczb całkowitych wpisanych przez użytkownika. Od użytkownika wczytamy najpierw liczbę n, która określi ile liczb zostanie podanych. Potem zakres_od, zakres_do, które określą z jakiego przedziały liczby całkowite mamy dane na liście oraz n liczb, które zapiszemy do tablicy L.
Sortowanie odbywa się w miejscu, więc nie będziemy zwracać nowej listy - zmodyfikujemy listę, którą otrzymaliśmy. (2.) Wyliczamy długość listy zliczającej. (3.) Alokujemy pamięć pod tablicę zlicz do której będziemy zliczać wystąpienie kolejnych cyfr. (4.) Dla każdego elementu zaalokowanej pamięci (5.) ustawiamy jego wartość na 0. Musimy to zrobić, ponieważ w C++ pamięć alokowana dynamicznie nie resetuje wartości wcześniej tam zapisanych. Następnie (6.) analizujemy daną listę do posortowania. Dla każdego jej elementu zwiększamy odpowiedni element tablicy zlicz. Należy pamiętać, że liczba dana jako zakres_od ma indeks 0, więc od i-tej wartości liczby z tablicy lista musimy odjąć zakres_od.
Mamy już gotową tablicę zliczającą, więc przechodzimy do nadpisywania oryginalnej listy. (7.) Deklarujemy zmienną x, która będzie pomagała określić, który element listy wynikowej teraz zapisujemy. (8.) Dla każdego elementu tablicy zlicz powtarzamy zlicz[i] razy dopisanie do listy wynikowej wartości i+zakres_od. W ten sposób posortowaliśmy listę.
Po uruchomieniu programu należy wpisać liczbę n jak długa jest lista, a następnie najmniejszą liczbę na liście oraz największą, a potem n elementów. Przykładowo dla:
Przykładowo dla danych:
otrzymamy:
Zmodyfikuj funkcję sort(), aby przed rozpoczęciem zliczania funkcja sama znalazła wartość największą i najmniejszą na liście. Innymi słowy funkcja sort() nie może już pobierać argumentów zakres_od, zakres_do.
Zmodyfikuj funkcję main(), aby nie przyjmowała zakresu od/do i można było wprowadzić listę złożoną z małych znaków alfabetów łacińskiego. Przykładowo dla listy [a e d b c c] otrzymamy: