[DOMANDA] Merge sort in c++

#1
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:
398
254
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
#2
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:
398
254
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
#4
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:
#5
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;
}
 
398
254
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
#6
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.
 
#8
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?
 
398
254
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
#9
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:

 
#10
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?
 
398
254
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
#11
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...