W tym punkcie omówimy pewien algorytm sortowania, opierający się na bardzo prostym pomyśle. Nie zawsze jednak można go stosować, gdyż wymaga pewnych specjalnych założeń dotyczących danych.

Niech e₁, ..., e_n będzie n elementowym ciągiem liczb naturalnych z przedziału [0,k], kÎN. Zakładamy więc, że spełniony jest warunek

Dla każdego elementu x danego ciągu, znaleźć liczbę elementów mniejszych lub równych x. Pozwoli to ustalić właściwą pozycję elementu x w ciągu uporządkowanym. Jeżeli dla elementu x istnieje j elementów mniejszych lub równych od niego, to x należy umieścić w ciągu wynikowym na pozycji j-tej.

W przedstawionym algorytmie e jest tablicą zawierającą elementy danego ciągu, C jest tablicą pomocniczą, a B tablicą wynikową. Aby ten algorytm działał poprawnie musimy znać wartość parametru k, czyli największą z liczb znajdujących się w ciągu danych. Jeśli liczba ta nie jest znana, to możemy ustalić jej wartość szukając elementu największego w danym ciągu.

CountingSort{
	for i:=0 to k do C[i] :=0 od;
	for j:=1 to n do C[e[j]] := C[e[j]]+1 od;	// C[j] = liczba elementów ciągu równych j
	for i := 1 to k do
	C[i] := C[i]+ C[i-1] ;	// C[i] = liczba elementów ciągu £ od i
	od;	// e[i] < e[j], to C[e[i]] < C[e[j]] dla wszystkich i,j £ n
	for j := n downto 1 do	// umieszczenie elementu e[j] na właściwej pozycji w B
	B[C[e[j]]] := e[j];
	C[e[j] ]:= C[e[j]] - 1;
	od;	// B[1] £ B[2] £ ... £ B[n]
}

Niech tablica, którą chcemy posortować zawiera następujące elementy: 3,5,4,1,3,4,1,4. Ponieważ największą wartością w tej tablicy jest liczba 5, zatem potrzebna nam będzie tablica pomocnicza C o sześciu elementach. Tablica C będzie zawierała adresy w tablicy wynikowej, pod którymi powinny się znaleźć dane elementy.

W wierszach 1-3 powyższej tabeli przedstawiono stan tablicy pomocniczej po wykonaniu kolejnych trzech pętli. Kolejne wiersze tablicy C przedstawiają zmiany związane z wypełnianiem tablicy wyjściowej B. Elementy dane przekładamy pod właściwy adres, wskazany w tablicy C, zaczynając od ostatniego elementu ciągu. W każdym kroku, element wkładany, jest zaznaczony na czerwono. I tak liczba 4 powinna trafić na pozycję C[4], czyli pozycję 7 w tablicy wyjściowej (bo jest aż 7 elementów w danym ciągu mniejszych bądź równych 4). Zapisujemy 4, a adres w tablicy C modyfikujemy, tak by następną czwórkę, o ile taka znajduje się w ciągu, wpisać na odpowiednie miejsce. Zmiany adresu zaznaczyliśmy pogrubioną czcionką. Następnym elementem wstawionym do tablicy B jest 1. Jej adresem jest C[1], czyli 2. Wstawiamy jedynkę na pozycję drugą w ciągu wynikowym i modyfikujemy adres dla następnej jedynki, itd. J

Po wykonaniu pierwszych dwóch pętli, C[i] = krotność liczby i w danym ciągu. Po wykonaniu następnej pętli,

Zauważmy, że elementy tablicy pomocniczej C tworzą ciąg uporządkowany niemalejąco. Wszystkie liczby mniejsze lub równe i muszą, po uporządkowaniu, znaleźć się na pozycjach 0 do C[i]. W tablicy B, na wypełnionych pozycjach mniejszych od C[e[j]], znajdują się elementy mniejsze lub równe e[j], a na pozycjach większych - elementy większe od e[j]. Umieszczając e[j] na pozycji C[e[j]] w tablicy B, zapewniamy, że pozycje wypełnione w tablicy B tworzą ciąg uporządkowany niemalejąco.

Twierdzenie 4.1 Algorytm CountingSort jest poprawnym rozwiązaniem problemu sortowania w strukturze liczb rzeczywistych ze względu na następującą specyfikację:

wp = {e[i]ÎN, e[i] £ k dla i =1,...n},

wk = {B[i] £ B[i+1] dla i=1,...,n-1, oraz B[1],...,B[n] jest permutacją elementów e[1], ..., e[n]}

Algorytm wykonuje zatem Q(k+n) operacji. Jeżeli k = O(n), to koszt algorytmu jest liniowy w stosunku do rozmiaru danych.

Złożoność pamięciowa algorytmu zależy od wartości parametru k, i jest liniowa, gdy k=O(n).

Ze względu na użycie tablicy o długości k, algorytm CountingSort jest stosowany w przypadkach, gdy k jest niewielką liczbą naturalną, a elementy ciągu powtarzają się wielokrotnie.

Zauważmy jeszcze, że po dwóch pierwszych pętlach tego algorytmu moglibyśmy wypełnić tabelę wyjściową wpisując do niej tyle jedynek ile wynosi wartość C[1], tyle dwójek ile wynosi C[2] itd. Nie postąpimy tak jednak, bo zależy nam na tym, aby algorytm posiadał cechę stabilności.

Definicja 4.1 Powiemy, że algorytm sortowania jest stabilny wtedy i tylko wtedy, gdy elementy o tej samej wartości pojawiają się na wyjściu w takiej samej kolejności w jakiej występowały na wejściu.

Wyobraźmy sobie, że liczby 3, 2, 2, 1, 3 są kluczami, ze względu na które chcemy posortować pewne obiekty niekoniecznie liczbowe, np. Ala, Ela, Mela, Ola, Tola, które już są uporządkowane w pewien specjalny sposób. W wyniku zastosowania algorytmu ContingSort otrzymamy kolejność Ola(1), Ela(2), Mela(2), Ala(3), Tola(3). Elementy mające ten sam klucz (np. Ela i Mela), w ciągu wyjściowym występują w takim samym porządku, jak w ciągu wejściowym. J

Pytanie 5: Jaki jest stan tablicy pomocniczej po wykonaniu algorytmu CountingSort dla ciągu 3,2,1,3,4,2,1,3?

	1	2	3	4	5	6	7	8	0	1	2	3	4	5
Dane	3	5	4	1	3	4	1	4	0	0	0	0	0	0	1
									0	2	0	2	3	1	2
	tablica wynikowa B								0	2	2	4	7	8	3
							4		0	2	2	4	6	8	j=8
		1					4		0	1	2	4	6	8	j=7
		1				4	4		0	1	2	4	5	8	j=6
		1		3		4	4		0	1	2	3	5	8	j=5
	1	1		3		4	4		0	0	2	3	5	8	j=4
	1	1		3	4	4	4		0	0	2	3	4	8	j=3
	1	1		3	4	4	4	5	0	0	2	3	4	7	j=2
	1	1	3	3	4	4	4	5	0	0	2	2	4	7	j=1
									tablica pomocnicza C