Implementazioni di algoritmi/Counting sort

Wikibooks, manuali e libri di testo liberi.

Sommario
Categoria · Copertina · Sviluppo · modifica il template

Copertina Implementazioni di algoritmi/Copertina


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).

Indice

[modifica] 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

[modifica] Implementazioni

[modifica] C

 void countingSort(int v[], int dim, int ris[])
  {
    int i, occ[M+1];
 
    for(i=0;i<=M;i++)          //Inizializza array per le occorrenze
        occ[i]=0;
    for(i=0;i<dim;i++)         // Inserisce nell'array occ il numero di occorrenze
        occ[v[i]]++;
    for(i=1;i<=M;i++)         // occ[i] contiene il numero di elementi <=i in v
        occ[i]+=occ[i-1];
    for(i=dim-1;i>=0;i--) {    // Dispone gli elementi di v in ris
        ris[occ[v[i]]-1]=v[i];
        occ[v[i]]--;
    }
 }

[modifica] 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);
}

[modifica] Java

 void countingSort(int[] A)
 {  
    //Cacolo degli elementi max e min
    int max=A[0];
    int min=A[0];
    int i=1;
    for(; i<A.length; i++){
       if(A[i]>max) max=A[i];
       else if(A[i]<min) min=A[i];
    }
    //Costruzione dell'array C
    int[] C=new int[max-min+1];           //crea l'array C
    for(i=0; i<C.length; i++) C[i]=0;    //inizializza a zero gli elementi di C
    for(i=0; i<A.length; i++)
       C[A[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<C.length; i++){
       while(C[i]>0){                     //scrive C[i] volte il valore (i+min) nell'array A
          A[k]=i+min;
          k++;
          C[i]--;
       }
    }
 }

[modifica] Altri progetti

Ricavato da "http://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Counting_sort"
Strumenti personali
Altre lingue