Problema con algoritmo merge sort
Ho trovato un'implmentazione del merge sort, ma eseguendo il codice il programma va in crash:
Funzione mergesort:
Funzione merge:
Esecuzione nel main:
E poi non o capito due cose:
1) Nel primo blocco di codice non ho capito quando viene eseguita la funzione ricorsiva
2) Non ho capito cosa fa il codice del secondo blocco dal primo ciclo for fino al delete.
Potreste aiutarmi a capire la causa del crash e spiegarmi le cose che non ho capito? Grazie in anticipo!
Funzione mergesort:
void mergeSort(int arr[], int s, int d)
{
if (s < d)
{
int c = (d - s) / 2;
mergeSort(arr, s, c);
mergeSort(arr, c + 1, d);
merge(arr, s, c, d);
}
}
Funzione merge:
void merge(int arr[], int s, int c, int d)
{
int* aux = new int[d + 1];
int i, j;
for (i = c + 1; i > s; i--)
aux[i - 1] = arr[i - 1];
for (j = c; j < d; j++)
aux[d + c - j] = arr[j + 1];
for (int k = s; k <= d; k++)
if (aux[j] < aux[i])
arr[k] = aux[j--];
else
arr[k] = aux[i++];
delete[] aux;
}
Esecuzione nel main:
int a[] = { 10, 3, 15, 2, 1, 4, 9, 0 };
cout << "Ecco l'array disordinato: " << endl;
stampaArray(a, 8);
cout << "Ecco l'array ordinato: " << endl;
mergeSort(a, 0, 7);
stampaArray(a, 8);
E poi non o capito due cose:
1) Nel primo blocco di codice non ho capito quando viene eseguita la funzione ricorsiva
mergeSort(arr, c + 1, d);
2) Non ho capito cosa fa il codice del secondo blocco dal primo ciclo for fino al delete.
Potreste aiutarmi a capire la causa del crash e spiegarmi le cose che non ho capito? Grazie in anticipo!
Risposte
Cosa significa "ho trovato"? In generale sai come funziona il merge-sort?
In ogni caso il crash è dovuto alla funzione mergeSort(). Se entriamo nella funzione con s=0 e d=3 tutto OK, ipotizziamo invece di entrare nella funzione con s=4 e d=7, ci aspettiamo le partizioni 4-5 e 6-7, ma la funzione restituisce 4-1 e 2-7... c'è evidentemente qualcosa che non va. Rifletti sul valore di "c".
Per quanto riguarda la funzione merge() ho capito cosa fa e sembra essere funzionante. Per esempio ipotizziamo di passargli s=0, d=6, c=3 e
arr={1, 3, 7, 8, 0, 2, 5}
al termine dei primi due cicli for sarà i=s, j=d e
aux={1, 3, 7, 8, 5, 2, 0}
in pratica la seconda sottosequenza viene messa in ordine inverso.
Detto questo credo che l'ultimo for sia semplice da capire.
Lo scopo di tutto ciò dovrebbe essere quello di evitare di considerare le due sottosequenze separatamente stando lì a controllare ogni volta se una delle due sottosequenze è "vuota"
Nel seguente codice ti mostro quella che potrebbe essere la strategia "classica":
Sper di essere stato chiaro, se hai qualche dubbio chiedi pure.
In ogni caso il crash è dovuto alla funzione mergeSort(). Se entriamo nella funzione con s=0 e d=3 tutto OK, ipotizziamo invece di entrare nella funzione con s=4 e d=7, ci aspettiamo le partizioni 4-5 e 6-7, ma la funzione restituisce 4-1 e 2-7... c'è evidentemente qualcosa che non va. Rifletti sul valore di "c".
Per quanto riguarda la funzione merge() ho capito cosa fa e sembra essere funzionante. Per esempio ipotizziamo di passargli s=0, d=6, c=3 e
arr={1, 3, 7, 8, 0, 2, 5}
al termine dei primi due cicli for sarà i=s, j=d e
aux={1, 3, 7, 8, 5, 2, 0}
in pratica la seconda sottosequenza viene messa in ordine inverso.
Detto questo credo che l'ultimo for sia semplice da capire.
Lo scopo di tutto ciò dovrebbe essere quello di evitare di considerare le due sottosequenze separatamente stando lì a controllare ogni volta se una delle due sottosequenze è "vuota"
Nel seguente codice ti mostro quella che potrebbe essere la strategia "classica":
void merge_(int *v, const unsigned int s, const unsigned int c, const unsigned int d)
{
unsigned int dim = d - s + 1;
int *u = new int[dim];
unsigned int i;
unsigned int i_s = s;
unsigned int i_d = c + 1;
for(i = 0; i < dim; ++i)
{
if(i_s <= c)
{
if(i_d <= d)
{
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[s + i] = u[i];
}
delete[] u;
}Sper di essere stato chiaro, se hai qualche dubbio chiedi pure.
Allora per la funzione mergeSort se scrivo int c = (d+s)/2 funziona, però guardando in rete la soluzione più classica per l'algoritmo di fusione dei vettori, ovvero la funzione merge è:
Comunque penso che ci siano molt modi di implementarlo, ma qual'è quello più efficiente? Poi volevo togliermi un altro dubbio per quanto riguarda la funzione mergeSort: la prima funzione ricorsiva lavora su una metà dell'array spezzato, l'altra lavora sull'altra metà e questo finche non si arriva ad isolare tutti gli elementi dellarray, ma come fa la funzione di "fusione" ad ordinare il ordine crescente l'array?
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
Comunque penso che ci siano molt modi di implementarlo, ma qual'è quello più efficiente? Poi volevo togliermi un altro dubbio per quanto riguarda la funzione mergeSort: la prima funzione ricorsiva lavora su una metà dell'array spezzato, l'altra lavora sull'altra metà e questo finche non si arriva ad isolare tutti gli elementi dellarray, ma come fa la funzione di "fusione" ad ordinare il ordine crescente l'array?
però guardando in rete la soluzione più classica per l'algoritmo di fusione dei vettori, ovvero la funzione merge è:...
Questa sfrutta lo stesso ragionamento della funzione che ho postato in precedenza (attento cmq che contiene VLA).
Poi volevo togliermi un altro dubbio per quanto riguarda la funzione mergeSort: la prima funzione ricorsiva lavora su una metà dell'array spezzato, l'altra lavora sull'altra metà e questo finche non si arriva ad isolare tutti gli elementi dellarray, ma come fa la funzione di "fusione" ad ordinare il ordine crescente l'array?
Non sono sicuro di aver capito la domanda, in ogni caso prima di pensare all'efficienza dell'algoritmo utilizzato, hai capito cosa fa in generale la funzione merge()? Che caratteristica hanno le due "partizioni" dell'array che riceve la funzione?
Allora provo a spiegarmi meglio: cominciamo dalla funzione mergeSort:
la prima istruzione divide l'array a metà, la seconda istruzione è il richiamo alla funzione stessa e divide a metà la prima metà dell'array finchè non arriva ad un'unica cella indivisibile, ma di queste uniche celle ce ne sono tante. La seconda istruzione è la chiamata alla funzione stessa che però va a dividere l'altra metà dell'array finchè non rimangono tante celle separate. A quel punto viene chiamata la funzione merge ed è qui che non capisco: la funzione merge deve unire tutte le celle in un array allocato dinamicamente, ma come fà a farlo in ordine. Oppure sono le istruzioni ricorsive che hanno diviso in ordine l'array? Cos'è il VLA? Se ti riferisci al fatto che ci sono due array con indici non costanti, allora sì, me ne sono accorto
la prima istruzione divide l'array a metà, la seconda istruzione è il richiamo alla funzione stessa e divide a metà la prima metà dell'array finchè non arriva ad un'unica cella indivisibile, ma di queste uniche celle ce ne sono tante. La seconda istruzione è la chiamata alla funzione stessa che però va a dividere l'altra metà dell'array finchè non rimangono tante celle separate. A quel punto viene chiamata la funzione merge ed è qui che non capisco: la funzione merge deve unire tutte le celle in un array allocato dinamicamente, ma come fà a farlo in ordine. Oppure sono le istruzioni ricorsive che hanno diviso in ordine l'array? Cos'è il VLA? Se ti riferisci al fatto che ci sono due array con indici non costanti, allora sì, me ne sono accorto
Cos'è il VLA? Se ti riferisci al fatto che ci sono due array con indici non costanti, allora sì, me ne sono accorto
VLA sta per Variable Length Array.
Si mi riferivo a quei due array, in ogni caso più che indici, si tratta di dimensioni non costanti.
Allora provo a spiegarmi meglio: cominciamo dalla funzione mergeSort:
la prima istruzione divide l'array a metà, la seconda istruzione è il richiamo alla funzione stessa e divide a metà la prima metà dell'array finchè non arriva ad un'unica cella indivisibile, ma di queste uniche celle ce ne sono tante. La seconda istruzione è la chiamata alla funzione stessa che però va a dividere l'altra metà dell'array finchè non rimangono tante celle separate. A quel punto viene chiamata la funzione merge ed è qui che non capisco: la funzione merge deve unire tutte le celle in un array allocato dinamicamente, ma come fà a farlo in ordine. Oppure sono le istruzioni ricorsive che hanno diviso in ordine l'array?
Le frecce in blu indicano la divisione dell'array in 2 partizioni, mentre quelle in arancione sono relative al merge.
Ho chiarito il tuo dubbio o intendevi altro?
Si, questo schema di funzionamento lo conoscevo e l'avevo già capito, però il mio dubbio satav in un altra cosa: segui nell'immagine la divisione del vettore di sinistra:7 6 5 4 poi continua a sinistra in: 7 6 poi sempre a sinistra 7. Ecco ora abbiamo due caselle separate: il 7 e il 6, come fa la funzione che li unisce a prenderli correttamente in ordine crescente?
Ecco ora abbiamo due caselle separate: il 7 e il 6, come fa la funzione che li unisce a prenderli correttamente in ordine crescente?
L'array a quel punto è
7 6 5 4 3 2 1
dopo la chiamata a funzione merge() con s=0, c=0 e d=1, l'array diventa
6 7 5 4 3 2 1
In pratica la funzione merge() si aspetta due partizioni ordinate e una partizione di un solo elemento risulta ovviamente ordinata.
In ogni caso continuo a non capire quale sia il tuo dubbio... ripeto la domanda fatta nel precedente post: hai capito cosa fa e come funziona la funzione merge()?
In pratica la funzione merge() si aspetta due partizioni ordinate
Ecco proprio questo non capisco: la funzione merge prende le parti già ordinate, ma chi è che le ordina? La funzione mergesort serve a dividere tutto l'array, la merge a ricomporlo, ma chi è che ordina una volta che è tutto diviso?
Non ho capito questo: dopo la chiamata a funzione merge() con s=0, c=0 e d=1, l'array diventa
6 7 5 4 3 2 1
Non è che hai frainteso il significato delle variabili? s sta per sinistra ovvero il primo elemento dell'array, c sta per centro a indicare la meta dell'array e d sta per destra a indicare l'ultimo elemento dell'array.
la funzione merge prende le parti già ordinate, ma chi è che le ordina?
Ovviamente la stessa funzione merge() che da 2 partizioni di un solo elemento (che risultano già ordinate) ricava una partizione ordinata di 2 elementi e così via (seguendo un procedimento a ritroso imposto dalla ricorsione).
Non è che hai frainteso il significato delle variabili? s sta per sinistra ovvero il primo elemento dell'array, c sta per centro a indicare la meta dell'array e d sta per destra a indicare l'ultimo elemento dell'array.
Ho inteso che considerata una generica partizione (e non l'intero array), s rappresenta l'indice del primo elemento, d l'indice dell'ultimo elemento e c l'indice dell'elemento centrale. Quindi la partizione s;d viene a sua volta divisa nelle partizioni s;c e c+1;d.
Detto questo cosa non ti convince della seguente affermazione:
dopo la chiamata a funzione merge() con s=0, c=0 e d=1, l'array diventa
6 7 5 4 3 2 1
che ti ha fatto pensare che io abbia frainteso il significato delle variabili?
Se ti può essere utile ti posto un'altra immagine in cui ho anche evidenziato l'ordine in cui vengono richiamate le funzioni merge_sort() e merge():
Io ti ringrazio tantissimo per l'impegno che stai facendo per farmi capire, ma mi sfugge sempre un pezzo, cerco di esprimermi meglio. La funzione merge prende le due partizioni da un solo elemnto, come fà a ricavarne una ordinata? Poi ho capito che procede a ritroso fino ad arrivare un'unico array ordinato, ma il mio dubbio sta proprio alla base del primo array che prende la merge.
Immagina di avere il seguente main
e prova a seguire passo passo quello che avviene una volta richiamata la funzione merge_sort().
In ogni caso secondo me il problema consiste nel fatto che tu non abbia capito come funzioni e cosa faccia la funzione merge().
Per esempio come diventerà il vettore
v = 3 5 2 0 1 7 9 2 6 8 3 2
dopo aver richiamato la funzione merge(v, 3, 6, 9)?
int main()
{
int v[] = {2, 1};
stampa_array(v, 2);
merge_sort(v, 0, 1);
stampa_array(v, 2);
}e prova a seguire passo passo quello che avviene una volta richiamata la funzione merge_sort().
In ogni caso secondo me il problema consiste nel fatto che tu non abbia capito come funzioni e cosa faccia la funzione merge().
Per esempio come diventerà il vettore
v = 3 5 2 0 1 7 9 2 6 8 3 2
dopo aver richiamato la funzione merge(v, 3, 6, 9)?
Se chiamo la funzione merge sul vettore scritto da te il valore di s = 3 d non puo essere 9 ma 2 e c dovrebbe essere o 92 visto che è metà del vettore, o sbaglio? Nel main ch hai scritto tu il vettore 2 1 viene diviso in due vettori con le due funzioni ricorsive di per se ordinati, ma poi entra in gioco la merge e in effetti non capisco sa faccia esattamente. Potresti speigarmelo proprio su questo esempio semplice?
Se chiamo la funzione merge sul vettore scritto da te il valore di s = 3 d non puo essere 9 ma 2 e c dovrebbe essere o 92 visto che è metà del vettore
La funzione merge() si aspetta semplicemente due partizioni ordinate, dove la prima partizione inizia dall'indice s e termina all'indice c, mentre la seconda partizione inizia dall'indice c+1 e termina all'indice d.
Considerando il vettore
v = 3 5 2 0 1 7 9 2 6 8 3 2
con la chiamata a funzione merge(v, 3, 6, 9), le due partizioni da unire sono le seguenti:
3 5 2 0 1 7 9 2 6 8 3 2
la funzione in pratica riempie un array (di dimensione pari alla somma degli elementi delle 2 partizioni) prendendo di volta in volta il minimo tra l'elemento corrente (che parte dal primo) delle due partizioni. Tale vettore viene poi sostituito alle 2 partizioni. Quindi all'uscita dalla funzione sarà
v = 3 5 2 0 1 2 6 7 8 9 3 2
Ah perfetto, adesso ho capito, quando mi hai dato i valori da considerare, pensavo che ti riferissi ai numeri e non agli indici dell'array. Ti ringrazio tantissimo per la pazienza che hai avuto nello spiegare e sopratutto la chiarezza. Buona serata!
Non ho capito bene quale sia stato il misunderstanding, in ogni caso di niente! 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo