Esercizi di programmazione in Pascal->CountingSort

CountingSort

In questo piccolo tutorial verrà spiegato l'implementazione del classico ordinamento CountingSort.
Questo algoritmo è famoso perchè riesce a ordinare un array di numeri interi in tempo O(n). Per poter applicare questo algoritmo i numeri devono essere compresi nel'intervallo [0, k] dove k è un numero abbastanza piccolo (soprattutto più piccolo di n).
Dato un vettore A di elementi da ordinare, l'algoritmo si basa sul calcolo di un vettore di ricorrenze C in modo che C[v] sia la somma di tutte le occorrenze di valori uguali o più piccoli di "v" nel vettore A. In pratica con C[v] possiamo ricavare l'utima posizione del valore "v" all'interno del vettore A. Il risultato viene archiviato nel vettore B.

Di seguito la definizione del vettore:
Nella procedura di seguito possiamo vedere che il vettore B viene costruito in questo modo: se l'utima posizione del valore "v" all'interno del vettore A è C[v] allora possiamo inserire v nella posizione C[v] del vettore B. Decrementando il valore in C[v], in pratrica vuol dire che ad ogni altra corrisponza di v in A viene scalata una posizione.

Vediamo il codice:

Il corpo del programma crea un vettore con numeri generati casualmente, richiama la procedura di ordinamento e quindi stampa il risultato.
Vediamo di seguito il codice.



Scarica sorgente (480 byte)