Implementazioni di algoritmi/Counting sort
Il Counting sort è un algoritmo di ordinamento per valori numerici interi con complessità lineare O(n+m), dove n è la lunghezza dell'array e m è pari a max(A)-min(A)+1 (max(A) e min(A) sono rispettivamente l'elemento più grande e l'elemento più piccolo dell'array) ovvero è il range dei valori contenuti nell'array. Non è basato su confronti e scambi e conviene utilizzarlo quando il valore di m è piccolo rispetto a n, altrimenti risulterebbero più veloci altri algoritmi.
L'algoritmo è semplice ed intuitivo: si calcolano i valori max(A) e min (A) e si prepara un array C di dimensione pari all'intervallo dei valori con C[i] che rappresenta la frequenza dell'elemento i+min(A) nell'array di partenza A. Si visita l'array A aumentando l'elemento di C corrispondente. Dopo si visita l'array C in ordine e si scrivono su A, C[i] copie del valore i+min(A).
Pseudocodice
[modifica | modifica sorgente]countingSort(A[])
//Cacolo degli elementi max e min
max ← A[0]
min ← A[0]
for i ← 1 to length[A] do
if (A[i] > max) then
max ← A[i]
else if(A[i] < min) then
min ← A[i]
//Costruzione dell'array C
* crea un array C di dimensione max - min + 1
for i ← 0 to length[C] do
C[i] ← 0 //inizializza a zero gli elementi di C
for i ← 0 to length[A] do
C[A[i] - min] = C[A[i] - min] + 1 //aumenta il numero di volte che si è incontrato il valore
//Ordinamento in base al contenuto dell'array delle frequenze C
k ← 0 //indice per l'array A
for i ← 0 to length[C] do
while C[i] > 0 do //scrive C[i] volte il valore (i + min) nell'array A
A[k] ← i + min
k ← k + 1
C[i] ← C[i] - 1
Implementazioni
[modifica | modifica sorgente]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ITEM unsigned long
void CountingSort(ITEM *,int );
int main(int argc, char **argv) {
ITEM *Array=NULL,*p;
unsigned int SizeArray,j;
if (argc<2){printf("Devi passare come parametro il numero di elementi da elaborare\n");return(1);};
SizeArray=atoi(argv[1]);
if (SizeArray<2){printf("Gli elementi da elaborare devono essere maggiori di uno\n");return(1);};
if (!(Array=malloc(SizeArray*sizeof(long)))){printf("Memoria Insufficiente\n");return(1);};
memset(Array,0,(SizeArray*sizeof(long)));
// Riempimento dell'Array con numeri casuali
srand((unsigned)time(NULL));
j=SizeArray;p=Array;while (j--) *(p++)=((unsigned long)((rand() % 0XFFFFFFFFL)+0X01L));
printf("Stampa l'Array disordinato\n");
j=SizeArray;p=Array;while (j--) printf("%d ",*(p++));printf("\n");
// richiama la funzione di ordinamento
CountingSort(Array,SizeArray);
printf("\nStampa l'Array ordinato\n");
j=SizeArray;p=Array;while (j--) printf("%d ",*(p++));printf("\n");
return(0);
};
// Funzione di ordinamento Counting Sort
void CountingSort(ITEM *Array,int SizeArray){
ITEM *p=Array;
ITEM max,min;
int SizeAux,*Aux=NULL; // Vettore Ausiliario
int k; // indice per l'array Array[]
int i;
//Calcolo degli elementi max e min, questa tecnica riduce di un controllo la scansione del vettore
min=max=*Array;
for(p=Array+SizeArray;--p!=Array;){ // verifica se i valori compresi tra Array[1] e Array[SizeArray-1] siano maggiori o minori di Array[0] (già assegnato a min e max)
if (*p>max) max=*p;
else if(*p<min) min=*p;
};
//Creazione dell'array Ausiliario Aux e sua inizializzazione a zero degli elementi
if(!(Aux=(int *)calloc((SizeAux=max-min+1),sizeof(int)))) return;
for(i=0; i<SizeArray; i++) Aux[Array[i]-min]++; //aumenta il numero di volte che si è incontrato il valore
//Ordinamento in base al contenuto dell'array delle frequenze Aux
for(k=i=0; i!=SizeAux; i++){
while(Aux[i]>0){ //scrive Aux[i] volte il valore (i+min) nell'array Array[]
Array[k]=i+min;
k++;
Aux[i]--;
};
};
};
#include <vector>
#include <algorithm>
/*
Per ordinare una sequenza in base a una chiave intera avente un range noto,
si deve definire un oggetto funzione che, dato un elemento, rende tale chiave
con il range che parte da 0.
L'ordinamento si effettua chiamando il template di funzione "counting_sort",
passando la sequenza, il numero massimo di chiavi, e l'oggetto-funzione.
Se la sequenza deve essere comunque copiata in un'altra sequenza,
è più efficiente chiamare "counting_sort_copy", passandole i suddetti
argomenti e in più un puntatore o iteratore all'inizio della sequenza
di destinazione.
Se l'ordinamento deve essere effettuato più volte, è ulteriormente più efficiente chiamare
"counting_sort_copy_with_counters", passandole i suddetti argomenti e in più
un puntatore o iteratore all'inizio dello spazio ausiliario usato dall'algoritmo.
*/
/* Template di funzione "counting_sort_copy_with_counters".
Input:
- La sequenza da ordinare compresa tra i puntatori o iteratori bidirezionali
"begin_to_sort" e "end_to_sort".
- La sequenza in cui copiare gli elementi ordinati, che inizia dal puntatore
o iteratore random "sorted", e ha tanti elementi quanti ce ne sono
nella sequenza da ordinare.
- La sequenza in cui porre i contatori temporanei, che inizia dal puntatore
o iteratore random "counters", e contiene n_keys elementi.
- Il numero massimo di chiavi "n_keys".
- L'oggetto-funzione "get_key" che, dato un elemento della sequenza,
rende la sua chiave come numero intero compreso in [0, n_keys - 1].
Output:
- La sequenza che inizia da "sorted", ordinata in base alla chiave.
Esempio di utilizzo, in cui si assume che "arr" contenga solo
numeri interi compresi tra 1000 e 1039:
struct get_key {
int operator()(const int& i) const { return i - 1000; }
};
int arr[100];
int sorted[100];
int counters[40];
counting_sort_copy_with_counters(arr, arr + 100, sorted, counters, 40,
get_key());
altro esempio, in cui si assume che "lst" contenga solo strutture
il cui campo "i" ha un valore compreso tra 1000 e 1039:
struct S { double d; int i; };
int get_key(const S& s) { return s.i - 1000; }
std::list<S> lst;
S sorted[100];
int counters[40];
counting_sort_copy_with_counters(lst.begin(), lst.end(), sorted,
counters, 40, get_key);
*/
template<typename BidIt, typename RanIt, typename IntRanIt, class Functor>
void counting_sort_copy_with_counters(
BidIt begin_to_sort, BidIt end_to_sort,
RanIt sorted, IntRanIt counters,
size_t n_keys, Functor get_key)
{
std::fill_n(counters, n_keys, 0);
for (BidIt it = begin_to_sort; it != end_to_sort; ++it) {
++counters[get_key(*it)];
}
for (IntRanIt it = counters + 1; it != counters + n_keys; ++it) {
*it += *(it - 1);
}
for (BidIt it = end_to_sort; it != begin_to_sort; ) {
sorted[--counters[get_key(*--it)]] = *it;
}
}
/* Template di funzione "counting_sort_copy".
Input:
- La sequenza da ordinare compresa tra i puntatori o iteratori bidirezionali
"begin_to_sort" e "end_to_sort".
- La sequenza in cui copiare gli elementi ordinati, che inizia dal puntatore
o iteratore random "sorted", e ha tanti elementi quanti ce ne sono
nella sequenza da ordinare.
- Il numero massimo di chiavi "n_keys".
- L'oggetto-funzione "get_key" che, dato un elemento della sequenza,
rende la sua chiave come numero intero compreso in [0, n_keys - 1].
Output:
- La sequenza che inizia da "sorted", ordinata in base alla chiave.
Internamente, viene creato un vector temporaneo che contiene n_keys
elementi di tipo int.
Esempio di utilizzo, in cui si assume che "arr" contenga solo
numeri interi compresi tra 1000 e 1039:
struct get_key {
int operator()(const int& i) const { return i - 1000; }
};
int arr[100];
int sorted[100];
counting_sort_copy(arr, arr + 100, sorted, 40, get_key());
altro esempio, in cui si assume che "lst" contenga solo strutture
il cui campo "i" ha un valore compreso tra 1000 e 1039:
struct S { double d; int i; };
int get_key(const S& s) { return s.i - 1000; }
std::list<S> lst;
S sorted[100];
counting_sort_copy(lst.begin(), lst.end(), sorted, 40, get_key);
*/
template<typename BidIt, typename RanIt, class Functor>
void counting_sort_copy(
BidIt begin_to_sort, BidIt end_to_sort,
RanIt sorted,
size_t n_keys, Functor get_key)
{
std::vector<int> counters(n_keys);
counting_sort_copy_with_counters(begin_to_sort, end_to_sort, sorted,
counters.begin(), n_keys, get_key);
}
/* Template di funzione "counting_sort".
Input:
- La sequenza da ordinare compresa tra i puntatori o iteratori bidirezionali
"begin_to_sort" e "end_to_sort".
- Il numero massimo di chiavi "n_keys".
- L'oggetto-funzione "get_key" che, dato un elemento della sequenza,
rende la sua chiave come numero intero compreso in [0, n_keys - 1].
Output:
- La sequenza compresa tra "begin_to_sort" e "end_to_sort",
ordinata in base alla chiave.
Internamente, viene creato un vector temporaneo contenente la copia
ordinata della sequenza, e un altro vector temporaneo che contiene n_keys
elementi di tipo int.
Esempio di utilizzo, in cui si assume che "arr" contenga solo
numeri interi compresi tra 1000 e 1039:
struct get_key {
int operator()(const int& i) const { return i - 1000; }
};
int arr[100];
counting_sort(arr, arr + 100, 40, get_key());
altro esempio, in cui si assume che "lst" contenga solo strutture
il cui campo "i" ha un valore compreso tra 1000 e 1039:
struct S { double d; int i; };
int get_key(const S& s) { return s.i - 1000; }
std::list<S> lst;
counting_sort(lst.begin(), lst.end(), 40, get_key);
*/
template<typename BidIt, class Functor>
void counting_sort(
BidIt begin_to_sort, BidIt end_to_sort,
size_t n_keys, Functor get_key)
{
std::vector<typename std::iterator_traits<BidIt>::value_type>
sorted(std::distance(begin_to_sort, end_to_sort));
counting_sort_copy(begin_to_sort, end_to_sort, sorted.begin(), n_keys,
get_key);
copy(sorted.begin(), sorted.end(), begin_to_sort);
}
void countingSort(int[] arr) {
//Cacolo degli elementi max e min
int max = arr[0];
int min = arr[0];
int i = 1;
for(; i < arr.length; i++) {
if(arr[i] > max)
max = arr[i];
else if(arr[i] < min)
min = arr[i];
}
int[] arr2 = new int[max-min+1];
for(i = 0; i < arr2.length; i++)
arr2[i]=0; //inizializza a zero gli elementi di C
for(i=0; i < arr.length; i++)
arr2[arr[i]-min]++; //aumenta il numero di volte che si è incontrato il valore
//Ordinamento in base al contenuto dell'array delle frequenze C
int k=0; //indice per l'array A
for(i=0; i<arr2.length; i++) {
while(arr2[i]>0){ //scrive C[i] volte il valore (i+min) nell'array A
arr[k]=i+min;
k++;
arr2[i]--;
}
}
}
Altri progetti
[modifica | modifica sorgente]
Wikipedia contiene una voce su questo algoritmo
