Counting sort

Il counting sort fa parte degli algoritmi di sorting. $\Theta (n+k)$ in tempo e spazio

Input Sequenza di $n$ valori interi $A=<a_0,a_1,...,a_{n-1}>$ tali che $0\le a_i\le k,\forall i\in \{0,1,...,n-1\}$.

Output Permutazione $<a_0^{\prime },a_1^{\prime },...,a_{n-1}^{\prime }>$ della sequenza $A$ tale che $a_0^{\prime }\le a_1^{\prime }\le ...\le a_{n-1}^{\prime }$

title: Attenzione
Non su effettuano confronti tra gli elementi di A.

1. Si crea un array di appoggio di lunghezza $k$, con $k$ numero più alto contenuto nell’array
2. Si cicla su A e si inserisce il conteggio di ogni valore nell’array di appoggio
3. Genero la sequenza appropriata partendo dall’array di appoggio

CountingSort(A, k)
	n := A.length
	B := [0..k]

	// inizializzo array B
	for i = 0 to n-1 do
		B[i] = 0

	for i = 0 to n-1 do
		B[A[i]] = B[A[i]] + 1

	j := 0
	for i = 0 to k-1 do
		while B[i] > 0 do
			A[j] := i
			j := j + 1
			C[i] := C[i] - 1

Il costo computazionale è molto basso, perché $T(n)\in \Theta (k)+\Theta (n)+O(n+k)=O(n+k)$ e come lower bound: $T(n)\in \Omega (k)$.

Lo spazio occupato per l’array di appoggio è di $\Theta (k)$.

Questo algoritmo non è stabile! Gli elementi presenti nell'array finale non sono uguali a quelli di partenza.

Bisogna stare attenti all’ordine di grandezza di $k$.

• Se $k\in \Omega (n^t)\Rightarrow T(n)\in \Omega (n^t)\text{mbox}espazio\Omega (n^t)$

Best use: meglio usare questo algoritmo quando $k\in O(n)$ o ancora meglio quando $k\in O(1)$.

Versione stabile

La versione stabile utilizza due array di appoggio:

1. B: similmente alla versione precedente, per tenere il conto degli elementi
2. C: per copiare gli elementi di A ordinatamente, e poi ricopiarli dentro A

CountingSort(A, k)
	n := A.length
	B := [0..k]
	C := [0..n-1]

	for i = 0 to n-1 do
		B[i] = 0

	for i = 0 to n-1 do
		B[A[i]] = B[A[i]] + 1

	for i = 1 to k do
		B[i] = B[i - 1] + B[i]

	for j = n-1 downto 0 do
		C[B[A[j]] - 1] := A[j]
		B[A[j]] := B[A[j]] - 1

	for i = 0 to n-1 do
		A[i] := C[i]

Come la versione non stabile, questo algoritmo costa $\Theta (n+k)$ di tempo e di spazio.

asd_15