Problema con algoritmo merge sort

Messaggioda ZfreS » 15/07/2018, 15:43

Ho trovato un'implmentazione del merge sort, ma eseguendo il codice il programma va in crash:

Funzione mergesort:
Codice:
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:
Codice:
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:
Codice:
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
Codice:
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!
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 676 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema con algoritmo merge sort

Messaggioda Super Squirrel » 15/07/2018, 22:33

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":
Codice:
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.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 248 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema con algoritmo merge sort

Messaggioda ZfreS » 16/07/2018, 08:48

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 è:
Codice:
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?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 677 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema con algoritmo merge sort

Messaggioda Super Squirrel » 16/07/2018, 09:27

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?
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 250 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema con algoritmo merge sort

Messaggioda ZfreS » 16/07/2018, 09:36

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
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 678 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema con algoritmo merge sort

Messaggioda Super Squirrel » 16/07/2018, 10:57

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?

Immagine
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?
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 251 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema con algoritmo merge sort

Messaggioda ZfreS » 16/07/2018, 11:09

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?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 679 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema con algoritmo merge sort

Messaggioda Super Squirrel » 16/07/2018, 11:46

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()?
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 252 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema con algoritmo merge sort

Messaggioda ZfreS » 16/07/2018, 12:22

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.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 680 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema con algoritmo merge sort

Messaggioda Super Squirrel » 16/07/2018, 13:00

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():
Immagine
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 253 di 1486
Iscritto il: 16/05/2013, 22:05

Prossimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite