Mergesort

di il
14 risposte

Mergesort

Salve, dovrei realizzare un programma che somma l'elemento iniziale delle chiamate del mergesort, precisamente così, abbiamo l'array [0 2 4 3 3]
L'array viene poi diviso in due sotto-array di dimensione 3 e 2, rispettivamente. Le chiamate successive saranno quindi realizzate sui sotto-array [0 2 4] e [3 3]. L'ultima chiamata realizzata su di un array con almeno 2 elementi e quella realizzata sull'array [0 2]. La somma che si vuole calcolare è quindi 0 + 0 + 3 + 0 = 3.
Avevo provato così ma non va, da 6
(conto è una variabile globale)
void mergesort(int a[], int left, int right)
{
	if (left< right)
	{

		int center=(left+right)/2;
		if(center+1>1)
			conto+=a[left]+a[center+1]-a[center+1];
		mergesort(a,left,center);
		mergesort(a,center+1,right);
		merge(a,left,center,right);
	}
}

14 Risposte

  • Re: Mergesort

    Ma da dove vengono 0 0 3 0 ? Non si capisce
  • Re: Mergesort

    0 è il primo numero dell'array [0 2 4 3 3], poi ci sono le altre chiamate, l'array si divide in 2 e si hanno i sotto array [0 2 4] e [3 3] e si prendono di nuovo i primi numeri dell'array, quindi 0 nell'array [0 2 4] e 3 nell'array [3 3], l'array [0 2 4] si suddivide ancora in [0 2] e prendiamo di nuovo il primo numero, quindi in totale dobbiamo sommare 0+0+3+0=3
    adesso penso che sono stato abbastanza chiaro
  • Re: Mergesort

    Quindi tutti i primi valori degli intervalli da 2 numeri.

    Devi quindi individuare gli intervalli da 2 numeri (con una if opportuna) prendere il valore a sinistra e sommarlo al totalizzatore.
  • Re: Mergesort

    Si, tutti i primi valori degli intervalli che contengono almeno 2 numeri.
    Il primo valore non sarebbe left?
    Mi verrebbe di fare così, ma l'ho provato e ottengo una somma errata
    void mergesort(int a[], int left, int right)
    {
       if (left< right)
       {
    
          int center=(left+right)/2;
          if(right>=1)
             conto+=left;
          mergesort(a,left,center);
          mergesort(a,center+1,right);
          merge(a,left,center,right);
       }
    }
  • Re: Mergesort

    Perché la if con >=1 ? Perché sommi la left ?

    Quelli sono gli indici ... rifletti ... aiutati con delle printf dei valori per capire
  • Re: Mergesort

    La if con >=1 perchè l'array deve avere almeno 2 valori
    Vero,ho sbagliato, sto sommando gli indici, allora dovrei sommare a[left] e anche a[center+1] perchè sarebbe il primo valore dell'array quando si dividono..e la condizione come dovrei metterla?
  • Re: Mergesort

    Ma confronti degli indici ! Che possono valere 40 o 343 non 1 ! Devi stare alla differenza tra indici ... se uno è 50 e l'altro è 51 ... allora...

    E usa le printf per esaminare i valori e renderti conto ... fallo ...
  • Re: Mergesort

    Non capisco perchè confronto gli indici..se faccio a[left] dovrebbe essere il valore..devo fare a[0]?
    Ho visto le cout con a[left] mi da i numeri dell'array
  • Re: Mergesort

    È la differenza tra gli indici che ti serve per determinare l'ampiezza dell'intervallo, non sei d'accordo?
  • Re: Mergesort

    Non ho capito...capirei meglio se vedo come impostare la condizione
  • Re: Mergesort

    Secondo me non ti sforzi e ti affidi al codice pronto.

    Cosa non capisci di 'differenza tra indici' che ti impedisca di provare a scrivere qualcosa?
  • Re: Mergesort

    Quindi devo fare questo?
    if(right-left>=1)
    sto provando così, con questo array {0, 2, 4, 3 ,3}
    void mergesort(int a[], int left, int right)
    {
    	if (left< right)
    	{
    		int center=(left+right)/2;
    		if(right-left>=1)
    			cout<<a[left]<<" "<<a[center+1]<<endl;
    		mergesort(a,left,center);
    		mergesort(a,center+1,right);
    		merge(a,left,center,right);
    	}
    }
    E le cout mi danno questo:
    0 3
    0 4
    0 2
    3 3673856
    3 3
  • Re: Mergesort

    Se scrivi >= prendi qualsiasi intervallo non solo quelli di due elementi
  • Re: Mergesort

    Io voglio prendere quelli di elementi maggiori o uguali 2, non è corretto?
Devi accedere o registrarti per scrivere nel forum
14 risposte