DOMANDA Merge sort in c++

olegfresi

Nuovo Utente
102
2
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:

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,208
1,845
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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:

olegfresi

Nuovo Utente
102
2
Allora, prima viene creato dinamicamente un vettore, poi non ho capito come viene usato questo vettore nella funzione
 

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,208
1,845
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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:

olegfresi

Nuovo Utente
102
2
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;
}
 

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,208
1,845
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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.
 

olegfresi

Nuovo Utente
102
2
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?
 

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,208
1,845
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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
 

olegfresi

Nuovo Utente
102
2
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?
 

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,208
1,845
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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...
 

olegfresi

Nuovo Utente
102
2
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
 

Ci sono discussioni simili a riguardo, dai un'occhiata!

Entra

oppure Accedi utilizzando
Discord Ufficiale Entra ora!

Discussioni Simili