Newsgroup: it.comp.lang.c++
Titolo: algoritmo merge sort

Spero di non essere troppo Off-Topic.
Sul mio libro "Introduzione agli algoritmi" di Cormen-Leiserson-Rivest c'č
una spiegazione su come creare un algoritmo di Merge-Sort. Orbene, intuendo
che sicuramente qualcuno di voi lo conosce, avrei bisogno di visionare il
codice per la funzione/procedura che si occupa di unire due array ordinati.
In pratica ho la funzione cosě impostata (in pseudocodice):
function mergesort (Array, p, q, r)
    if p<r then
        q=(p+r)/2 /*arrotondato per difetto */
        mergesort (Array, p,q)
        mergesort (Array, q+1, r)
        merge (Array,p, q, r)
end function
Se qualcuno č in grado di farlo e di postare il codice relativo gliene sarei
immensamente grato, perchč sul libro non c'č scritto e io non posso
verificare l'efficienza del codice da me scritto.
--
San Vegeta from Hell
http://www.geocities.com/Area51/Dungeon/8436
(da visitare con un browser della Netscape)

(da visitare con un browser della Netscape)
proc Merge (Array, p, q, r)
    //    declarations
    array V[ p..r ]
    int i= p;
    int j= q;
    int k= p;
    while ( i < y ) or ( j <= r ) do
        if ( i >= q ) {
            V[ k ] = Array [ j ];
            j = j + 1;
        }
        if ( j > r )    {
            V[ k] = Array [ i ];
            i = i + 1;
        }
        if ( Array [ i ] <= Array [ j ] )    {
            V [ k ] = Array [ i ];
            i = i + 1;
        }
        else {
            V [ k ] = Array [ j ];
            j = j + 1;
        }
        k = k + 1;
    end while
    Copy array V [ p .. r ] into the array Array [ p..r ]
endproc
Ogni operazione svolta all'interno di un ramo if ha complessità costante O
(1)
e il loop del while può essere eseguito al massimo O (n) volte, dove n
rappresenta
la lunghezza massima dell'array Array. Infatti, gli indici i e j vengono
inizialmente posti
in corrispondenda del primo indice dei due sottoarray da fondere e,
all'interno del loop,
sia i, sia j vengono sempre solo incrementati. Quindi tutta la procedura
Merge ha
complessità lineare, come richiesto dall'algoritmo.
Spero che non ci siano errori di battitura, nè di codifica. Non sarà
stilisticamente bella
da vedere, ma dovrebbe funzionare. Tempo fa ricordo di averla adattata al
pascal e al
C. Purtroppo ora non ho il tempo di verificare. Se hai problemi fammi un
fischio.
Ciao.

Sei fortunato. Cercando una cosa ne ho trovata un'altra. Ho beccato una
versione di Merge generica implementata in C++ che sfrutta i template, così
puoi usarla per ordinare array di qualsiasi cosa. Forse ti sarà utile. Vedi
tu,
template <class T>
void merge ( T x[ ], int l, int m, int r, int (*cmp) (T, T) )
{
    T *  a = x + l;
    T *  b = x + m + 1;
    T *  c = new T [r - l + 1];
    int aindx= 0;
    int bindx= 0;
    int cindx= 0;
    int alim = m - l + 1;
    int blim= r - m;
    while ( (aindx < alim) && (bindx < blim) )    {
        if ( ( * cmp) (a [ aindx ], b [ bindx ]) < 0 )
            c [ cindx++ ] =  a [ aindx++ ];
        else
            c [ cindx++ ] =  b [ bindx++ ];
    }
    // copy rest of a
    while ( aindx < alim)
        c [ cindx++ ] = a [ aindx++ ];
    // copy rest of b
    while ( bindx < blim)
        c [ cindx++ ] = b [ bindx++ ];
    for ( aindx = cindx = 0; aindx <= r - l; a [ aindx++ ] = c [ cindx++ ] )
    ;    // copy back
    delete c
}
Anche qui spero di non aver fatto errori di battitura. Ad ogni modo, se vuoi
dei ragguagli sulla porzione di codice che ti ho mandato, sappi che l'ho
reperita dal testo "Computational Geometry and Computer Graphics in C++" di
Michael J. Laszlo, Prentice Hall.