Newsgroup: it.comp.lang.c++
Titolo: Ordinare una lista nella maniera piu' veloce

 blocchi sono gia' ordinati
Se il codice e' codice C++, spero che tu abbia una std::list<A>; in
quel caso avrai iteratori, non puntatori, e bastera' chiamare il
metodo sort della Standard Library.
Se il codice e' in C, le liste in genere si ordinano col "mergesort";
grosso modo, la lista si divide ricorsivamente in parti che vengono
ordinate separatamente (sort) e poi unite (merge).  Se ti interessa
l'algoritmo, puoi dare un'occhiata allo Knuth, al Cormen o al
Sedgewick (in ordine decrescente della mia opinione personale); codice
gia' pronto lo puoi trovare sotto la URL
http://wwwcdf.pd.infn.it/MLO/llist.tar.gz
 ; viene da lezioni di C che
ho tenute a suo tempo, e c'e' enche una piccola appendice C++.
-- 
Maurizio Loreti  - Linux Is Not UniX -  
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it

 blocchi sono gia' ordinati
ci sono varie tipologie di risposta a questa domanda;
--- RISPOSTA C++ facile ---
per usare la lista non crearti una tua struttura dati ma usa quelle gia` 
pronte; ad esempio:
        struct Dato {
                int valore;
                // altri dati;
        };
        std::list<Dato> mia_lista;
giunti a questo punto e` facile ordinare la lista:
        mia_lista.sort();
--- RISPOSTA C++ difficile ---
Se vedendo la risposta alla domanda precedente hai pensato "si, ma io 
devo assolutamente usare la struct che ho scritto, non posso usare 
std::list" ma vuoi lo stesso usare le facilitazioni della libreria 
standard puoi provare a fare cosi` (nota che se non consci bene la 
libreria standard potrebbe essere difficile da capire):
// nota -- programma non testato
struct A { ... };
class A_iterator {
        A* ptr;
public:
        A_iterator(A* p): ptr(p) { }
        A& operator*() { return *ptr; }
        A* operator->() { return ptr; }
        A_iterator& operator++() {
                ptr = ptr->next;
                return *this;
        }
        A_iterator operator++(int) {
                A_iterator tmp(*this);
                ++(*this);
                return tmp;
        }
};
class A_less: public binary_function<bool, A, A> {
public:
        bool operator()(const A& a, const A& b) {
                return a.valore < b.valore;
        }
};
A* head; // testa della lista
std::vector<A> v(head, (A*)0);
std::sort(v.begin(), v.end(), A_less());
a questo punto in v dovrebbe esserci la tua lista ordinata.
Ovviamente questa non e` la tecnica consigliata (anzi!) pero` non sapevo 
che fare e mi sono divertito a scriverla (sperando di non aver fatto 
troppi errori - non ha provato neppure a compilare)
--- RISPOSTA DA TEORIA DEGLI ALGORITMI ---
Solitamente per ordinare una list si usa il mergesort; vedi anche la 
risposta di Maurizio al riguardo
--- RISPOSTA PRAGMATICA ---
Visto che sai che nella maggior parte dei casi la lista e` gia` ordinata 
(in un modo o nell'altro) fai cosi`:
1) prima di tutto guardi se la lista e` ordinata al contrario: se lo e`, 
la rovesci e hai finito
2) se non e` ordinata al contrario la ordini usando un algoritmo che 
funziona bene su sequenze gia` ordinate o quasi ordinate; il piu` 
semplice che mi viene in mente e` il bubblesort, ma probabilmente ne 
esistono di migliori
Nota che dal punto di vista della complessita` computazionale il passo 
(1) e` ininfluente, ma viste le precondizioni puo` consentirti un grosso 
guadagno in termini di tempo.
Probabilmete la risposta a te piu` utile e` quest'ultima, cmq a te la 
scelta.
ciao Anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.73, higher than 99% of all previous test takers.
C Language: 3.79, higher than 92% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

 ordinerà la lista?
in effetti genera un errore di compilazione. Per far si che funzioni il 
metodo list::sort devi fare almeno uno tra questi:
1) definire operator< per il tipo Dato
2) specializzare il template std::less per il tipo Dato (soluzione 
sconsigliata)
3) crearti un predicato e passarlo a sort (come ho fatto nell'esempio di 
vector)
