Newsgroup: it.comp.lang.c++
Titolo: Counting Sort

Salve,
c'č qualcuno che mi potrebbe fornire una versione (implementata e
funzionante) dell'algoritmo di ordinamento interno Counting Sort?
Grazie.
Max.

 funzionante) dell'algoritmo di ordinamento interno Counting Sort?
Sono ben felice di aiutarti, perche` e` un algoritmo importante
e il C++ Standard rende molto semplice presentarlo (se lo vuoi
in C invece che in C++ dovrai chiedere su it.comp.lang.c).
La template function seguente e` una piccola generalizzazione
del vero e proprio counting_sort:
template<class Seq, class Map>
void counting_sort(Seq& s, Map& m)
{
    Seq::iterator sit = s.begin();
    while(sit != s.end()) {
        ++(m[*sit]);
        ++sit;
    }
    sit = s.begin();
    Map::iterator mit = m.begin();
    while(mit != m.end()) {
        int count = mit->second;
        while(count--)
            *sit++ = mit->first;
        ++mit;
    }
    m.clear();
}
Un uso tipico (che non e` strettamente un counting sort
poiche` operator[] e` qui O(log(N))!) sarebbe ad es:
    std::vector<std::string> vis;
    char* aos[] = {"primo", "secondo", "terzo", "quarto"};
    for(int i=0; i<4; ++i)
        vis.push_back(aos[i]);
    std::map<std::string, int> maux;
    counting_sort(vis, maux);
    std::vector<std::string>::iterator it = vis.begin();
    while(it != vis.end())
        std::cout << *it++ << "\n";
Naturalmente, si ha il vero counting_sort se e solo se
operator[] e` O(1), e quindi il tipo Map non e` davvero
una mappa, bensi` un vettore (e quindi la counting_sort
va modificata, poiche` operator* applicato a Map::iterator
non tornera` una std::pair...!).  Non occorre dunque che
questo 'tipo d'appoggio' sia esplicitamente passato, e
si puo` semplificare counting_sort a questo overload:
template<class Seq>
void counting_sort(Seq& s)
{
    std::vector<int> v;
    Seq::iterator sit = s.begin();
    while(sit != s.end()) {
        int i = *sit++;
        if(i>=v.size()) v.resize(i+1);
        ++v[i];
    }
    int siz = v.size();
    sit = s.begin();
    for(int i=0; i<siz; ++i) {
        int count = v[i];
        while(count--)
            *sit++ = i;
    }
}
con usi tipici come:
    std::vector<int> vi;
    int ios[] = {22, 39, 61, 54, 30, 48, 25, 04, 34, 61, 39, 54, 0};
    for(int j=0; ios[j]; ++j)
        vi.push_back(ios[j]);
    counting_sort(vi);
    std::vector<int>::iterator ito = vi.begin();
    while(ito != vi.end())
        std::cout << *ito++ << " ";
    std::cout << "\n";
Naturalmente, questa versione si applica solo a sequenze
che contengono interi non negativi (e ha caratteristiche
di prestazioni assurde se la gamma di interi da sortare
e` ampia, ma, d'altronde, cosi` e` appunto counting_sort).
Ma _e`_ O(N) come desiderato, poiche` in ciascuno dei
due cicli (ognuno O(N)) si usano solo operazioni O(1)
(O(!) _ammortizzato_ per .resize in questo caso, ma non
e` difficile, passando a 3 cicli [uno preliminare con
lo scopo di trovare minimo e massimo di s] avere O(1)
rigorosamente... e tra l'altro generalizzare al sort
di interi in qualsiasi [stretta] gamma, non necessariamente
non-negativi... ma questo lo lasciamo come esercizio!-).
Alex

         int count = mit->second;
Una domanda: definendo una variabile all'interno di un ciclo ci si può
aspettare una minore efficienza rispetto al caso della sua definizione
prima del cliclo stesso oppure il compilatore comunque la definisce una
volta sola?
EMG

 volta sola?
Dipende dal compilatore, ma non ne conosco nessuno che presenta
differenze di efficienza fra i due casi.
Alex