Ordinamento in tempo lineare: si può ! --- Parte 1 di 3: Counting Sort

ORDINAMENTO IN TEMPO LINEARE

Gli algoritmi basati su confronti dei dati in input sono asintoticamente ottimali – riguardo al tempo impiegato per effettuare la computazione – quando svolgono il loro compito in O(n logn), come heapsort, mergesort e quicksort.

Esistono algoritmi che effettuano l'ordinamento seguendo altri criteri, riuscendo a battere la barriera di (n logn).

Qui mostrerò, a tal proposito, il Counting Sort, mentre nei prossimi giorni parlerò di Radix Sort e di Bucket Sort.

Come ho già anticipato, Counting Sort e gli altri algoritmi di ordinamento in tempo lineare non basano il loro funzionamento sui confronti tra i valori di input, ma sfruttano altre tecniche, per le quali il limite inferiore (n logn) non vale; in particolare, Counting Sort esamina il valore degli elementi, trattandoli come indici di un array... ma andiamo con ordine.

DESCRIZIONE

Siano i nostri n elementi di input degli interi, con valori compresi tra 0 e k.

Faremo uso di 3 array: A, di n elementi, contenente l'input; B, di n elementi, contenente l'output; C, array di “appoggio”, di k locazioni.

Inizialmente, tutte le k celle di C conterranno il valore 0.

L'idea è quella di depositare, in C[i], con i che varia da 0 a k, il numero di occorrenze del VALORE i in A.

Seguirà poi un ciclo for che scansionerà l'array C e, per ogni elemento i, sommerà a C[i] il valore di C[i-1]. Ogni locazione di C conterrà, quindi, il numero di elementi minori o uguali a i.

Questo risolve il problema sia di 0 che di più occorrenze uguali per un dato valore.

In questo modo, scorrendo C, sapremo quante volte inserire, in B, un dato valore, in maniera ordinata.

Tale algoritmo è, inoltre, STABILE: numeri di uguale valore hanno, in output, la stessa posizione relativa che avevano in input; questa proprietà torna particolarmente utile quando si ha a che fare con valori di A che hanno, associati, dati “satellite” diversi tra loro.

ESEMPIO

Prima di mostrare lo pseudocodice, vediamo un esempio.

Sia A l'array di interi contenente i valori:

A = 3 4 0 0 1 2 6.

Il valore massimo è 6, quindi C avrà 7 locazioni: da 0 a 6.

Scorriamo A: esaminiamo ogni valore, A[i], ed incrementiamo di 1 la locazione A[i] di C.

Dopo questo primo ciclo, C avrà questi valori:

C = 2 1 1 1 1 0 1.

A questo punto, eseguiamo il ciclo C[i] = C[i] + C[i-1].

Adesso C avrà questi valori:

C = 2 3 4 5 6 6 7.

Adesso scorriamo A dall'ultima locazione alla prima e, per ogni cella, assegniamo il valore di tale elemento a B[C[A[i]]], e decrementiamo il valore di C[A[i]] di una unità.

PSEUDOCODICE

Vediamo finalmente lo pseudocodice:

COUNTING-SORT(A,B,k)

for(i=0 to k) C[i] = 0; // inizializzo C.

for(j=1 to length(A)) C[A[j]] = C[A[j]] + 1; // primo ciclo.

for(i=1 to k) C[i] = C[i] + C[i-1]; // secondo ciclo

for(j=length(A) to 1)

{

B[C[A[j]]] = A[j];

C[A[j]] = C[A[j]] – 1;

}

Alla prossima ! ;-)