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

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

C

 
#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]--;
    };
  };
};

C++

#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);
}

Java

 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

Altri progetti

• Wikipedia

• Wikipedia contiene una voce su questo algoritmo