Sortowanie przez zliczanie ma jedną potężną zaletę i jedną równie potężną wadę:

• Zaleta: działa w czasie liniowym (jest szybki)
• Wada: może sortować wyłącznie liczby całkowite

Obydwie te cechy wynikają ze sposobu sortowania. Polega ono na liczeniu, ile razy dana liczba występuje w ciągu, który mamy posortować. Następnie wystarczy utworzyć nowy ciąg, korzystając z danych zebranych wcześniej. Np. mamy posortować ciąg: 3,6,3,2,7,1,7,1. Po zliczeniu (w jednym korku) operujemy danymi na temat liczności poszczególnych liczb:

• Liczba 1 występuje 2 razy
• Liczba 2 występuje 1 raz
• Liczba 3 występuje 2 razy
• Liczba 4 występuje 0 razy
• Liczba 5 występuje 0 razy
• Liczba 6 występuje 1 raz
• Liczba 7 występuje 2 razy

Na podstawie tych danych tworzymy ciąg: 1,1,2,3,3,6,7,7. Jest to ciąg wejściowy, ale posortowany. Należy zauważyć trzy ważne rzeczy:

1. Proces zliczania odbył się w jednym kroku
2. Nie doszło do ani jednej zamiany elementów
3. Proces tworzenia tablicy wynikowej odbył się w jednym kroku

Algorytmy ten posiada jednak również wady:

1. Do przechowywania liczby wyrazów ciągu musimy użyć tablicy, o liczbie elementów równej największemu elementowi ciągu
2. Sortować można jedynie liczby całkowite

Komentarze