DOMANDA Merge sort in c++

Pubblicità
O

olegfresi

Nuovo Utente
Messaggi
102
Reazioni
2
Punteggio
38
Devo implementare l'algoritmo di merge sort in c++. Ho scritto la funzione mergeSort ma non ho capito come funziona la merge. Potreste aiutarmi a capire come funziona la merge?
Codice: 
void mergeSort(int v[], int sinistra, int destra)
{
    if (sinistra < destra)
    {
        int centro = (sinistra + destra) / 2;
        mergeSort(v, sinistra, centro);
        mergeSort(v, centro + 1, destra);
        merge(v, sinistra, centro, destra);
    }

void merge(int v[], int sinistra, int centro, int destra)
{
    int dim = destra - sinistra + 1;
    int *u = new int[dim];
    int i;
    int i_s = sinistra;
    int i_d = centro + 1;

    for (i = 0; i < dim; ++i)
    {
        if (i_s <= centro)
        {
            if (i_d <= destra)
            {
                if (v[i_s] < v[i_d])
                {
                    u[i] = v[i_s++];
                }
                else
                {
                    u[i] = v[i_d++];
                }
            }
            else
            {
                u[i] = v[i_s++];
            }
        }
        else
        {
            u[i] = v[i_d++];
        }
    }
    for (i = 0; i < dim; ++i)
    {
        v[sinistra + i] = u[i];
    }
    delete[] u;
}

}
 
Ultima modifica:
La funzione merge è abbastanza semplice: tu hai un array V di N elementi, dove nel tuo cas N = (sinistra+destra).
Quindi avrai un for che inizia da sinistra e termina quando è uguale a destra. Dovrai usare anche 2 indici: uno che inizia da sinistra, e l'altro dal centro; in questo modo se v <= v[j], l'elemento da leggere (e da inserire nell'output) sarà v; in caso contrario sarà v[j]. Letto il valore dovrai incrementare il rispettivo indice.

Se non sono stato chiaro, chiedi pure.
 
Ultima modifica:
Ho visto che hai aggiornato il primo post con il codice completo.
Puoi dare un occhio a Wikipedia, che fornisce anche dello pseudocodice: https://en.wikipedia.org/wiki/Merge_sort

Altrimenti per com'è organizzato il codice, puoi fare una cosa come questa:
- crei due nuovi elementi: il primo, L, con gli elementi da 0 al centro; il secondo, R, con gli elementi dal centro+1, alla fine.
- copi la prima metà di v[] all'interno di L, e copi la seconda parte di v[] in R.

A questo punto crei 2 indici (chiamati ad esempio i e j) per i rispettivi 2 nuovi array e li inizializzi a 0. Ora dovrai considerare gli elementi di L e di R in base alla loro grandezza; vale a dire che se L <= R[j] dovrai considerare l'elemento L.
Il valore lo salverai in v[k]; dove k=sinistra e k<destra.

Forse con uno pseucodice si comprende meglio:
Codice: 
c1 = centro - sinistra + 1;
c2 = destra - centro;

FOR  i = 0 TO c1
     L[i] = A[sinistra  + i];

FOR j = 0 TO c2
    R[j] = A[centro + j];

i = 0;
j = 0;

FOR  k = sinistra TO destra
    IF L[i] <= R[j]
        A[k] = L[i]
        i++;
    ELSE
        A[k] = R[j]
        j++;

Reminiscenze dalla bibbia sugli algoritmi; dovrebbe essere corretto.
 
Ultima modifica:
Ah si, questo metodo l'ho capito. Ho trovato anche questa implementazione aletrnativa a quella postata da me precedentemente. Potresti spiegarmela a grandi linee come funziona?
Codice: 
void merge(Item a[], int left, int center, int right)
{
    Item* aux = new int[right + 1];
    int i,j;
    for (i = center+1; i > left; i--)
        aux[i-1] = a[i-1];
    for (j = center; j < right; j++)
        aux[right+center-j] = a[j+1];
    for (int k = left; k <= right; k++)
        if (aux[j] < aux[i])
            a[k] = aux[j--];
        else
            a[k] = aux[i++];
        delete [] aux;
}
 
Fa più o meno ciò che faccio nello pseudo-codice.
Alloca memoria per un array di right+1 elementi e copia nel vettore creato tutti gli elementi del vettore originale; nel primo for scorre dal centro sino all'indice 0; nel secondo invece dal centro alla fine.
Il terzo for invece seleziona gli elementi in base all'ordinamento: quindi utilizzando le stesse variabili dichiarate sopra, scorre gli elementi. Decrementa j in quanto nel for precedente è giunta al suo valore massimo (ovvero j=right), ed incrementa i in quanto nel primo for è stata decrementata raggiungendo lo 0.
 
Scusa se riprendo questo thread, ma mi è venuto un dubbio: quando la mergesort spezza l'array di partenza fino a quando non si ottengono tutti gli elementi spezzati singolarmente, come fà la merge a unirli ordinati?
 
Perchè vengono considerati intervalli ridotti, e questi vengono ordinati; quando la chiamata ricorsiva ritorna questo intervallo cambia. Di conseguenza vengono ordinate tutte le porzioni dell'array.
Praticamente quando raggiungi il fondo, il caso base, o per dirla in altri termini quando hai tutti gli elementi singoli, si torna al chiamante.
Considera l'immagine tratta da Wikipedia:

AnimazioneMergeSort.gif
 
Non credo di aver capito bene.
Per esempio se io ho il vettore: 4 3 7 1 5 2 9
Con le prime due chiamate ricorsive il vettore si spezza e diventa: 4 3 7 1 5 2 9
Poi diventa: 4 37 15 29
E infine: 4 3 7 1 5 2 9
Lavoriamo sulla parte sinistra: ora entra in gioco la merge. Ed è qui che non capisco: quale vettore le viene passato e quali sono i valori di left right e center?
 
La ricorsione da rappresentare è un pò ostica, proprio per il meccanismo che le è proprio.

Comunque considera gli indici (sinistra, centro, destra) al momento della chiamata, in questo caso:
Codice: 
4 3 7 1 5 2 9

considera che avvengono le chiamate ricorsive, ed al termine gli indici valgono rispettivamente: 0, 0, 1. La sequenza avrà quindi questo aspetto ora:

Codice: 
3 4 7 1 5 2 9

Poi gli indici saranno: 2, 2, 3.
Sequenza:

Codice: 
3 4 1 7 5 2 9
come noti lo scambio è tra le posizioni 2 e 3 (1 è minore di 7, infatti viene ordinato alla sua sinistra).

Indici: 0, 1, 3.
Sequenza:

Codice: 
1 3 4 7 5 2 9
anche in questo caso, se guardi la sequenza precedente, lo scambio è tra gli indici: 0, 1, 2, 3; quindi le prime 4 posizioni vengono ordinate tra di loro (significa che nella parte restante dell'array gli elementi non sono necessariamente ordinati; infatti anche in questo caso non lo sono).

Proseguendo, gli indici diventano: 4 4 5
Sequenza:

Codice: 
1 3 4 7 2 5 9

fai caso agli indici e guarda sempre la sequenza sopra (non l'ultima, ovviamente): i valori erano 5 e 2, e se noti l'ultima sequenza, vedrai i valori ordinati.

Proseguendo, gli indici sono: 4 5 6.
Sequenza:

Codice: 
1 3 4 7 2 5 9

Indici: 0 3 6.
Sequenza:
Codice: 
1 2 3 4 5 7 9

Questa era l'ultima chiamata ricorsiva.
Ricordati che le chiamate ricorsive formano una "pila", come porre un piatto sopra l'altro: quando ti fermi e torni indietro, il primo piatto che togli è quello in alto (l'ultimo che hai posizionato); si chiama LIFO (Last In, First Out). Questo perchè tutte le chiamate tornano indietro al chiamante.
Quelli che sono quindi i 3 indici che ti aspetti inizialmente (0, 3, 6), sono in realtà gli ultimi.

Devi anche tener presente la condizione che interrompe la ricorsione, ovvero la condizione "sinistra >= destra".
Ti posso mostrare anche gli indici con le varie chiamate (non completo), sperando sia comprensibile (ms = mergesort; m=merge):

Codice: 
s=0, d = 6     // inizio

c = (0+6)/2 = 3;
ms(0, 3);    // d = 6

c = (0+3) / 2 = 1;
ms(0, 1);    // d = 3

c = (0+1) / 2 = 0
ms(0, 0);    // d = 1

// uscita dal ciclo: si torna alla chiamata precedente (0,1) e viene chiamata la seconda mergesort
ms(1, 1);   // il primo parametro è c, ovvero c+1 = 0+1; il secondo d = 1

// uscita dal ciclo: viene chiamata merge
m(0, 0, 1);


Ps. spero di essere stato comprensibile, ma data l'ora e la giornata lavorativa, potrei anche aver commesso strafalcioni grammaticali...
 
Ah, ok quindi quando io arrivo alla fine della ricorsione prima che agisca la merge, l'array è diviso in parti da due, non da uno come pensavo all'inizio
 
Pubblicità
Pubblicità
Indietro
Top