Problema con algoritmo merge sort

di il
5 risposte

Problema con algoritmo merge sort

Studiando gli algoritmi di ordinamento sono arrivato al merge sort, che ho trovato difficile non tanto nel capirlo ma nell'implementarlo. Comunque ci ho provato lo stesso optando per una soluzione ricorsiva e ho diviso il lavoro in: una funzione mergeSort che divide via via fino ad arrivare al caso base che all'inizio divide l'array di partenza in due parti, poi continua con una delle due parti e poi con un'altra funzione ricorsiva riprende l'altra parte dell'array e la divide all'ultimo, infine viene eseguita la funzione merge per fondere il tutto; poi nel main l'ho verificato, ma il programma all'avvio ha un crash, ed ho scoperto che era nell'istruzione che divideva l'array. Poi volevo vedere in rete se ci fossero delle soluzioni più efficienti della mia, ed l'ho trovata, solo che non sono riuscito a capirla. Potreste aiutarmi a capirla e spiegarmi perchè mi dà il crash?(Vi metto la "soluzione" al crash in un commento del codice).

Funzione mergeSort

void mergeSort(int arr[], int s, int d)
{
	if (s < d)
	{
		int c =  (d - s) / 2;   //Se questa istruzione la scrivessi così: int c = s+(d-s)/2  non mi darebbe il crash. Come mai?
			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)  //Potreste aiuatarmi a capire il funzionamento di questo codice, in particolare dal primo ciclo for al delete?
{
		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;
}
Poi non allego il main percè lì non c'è nessun problema. Grazie in anticipo per l'aiuto!

5 Risposte

  • Re: Problema con algoritmo merge sort

    Deve essere

    int c = (d + s) / 2;
  • Re: Problema con algoritmo merge sort

    Ah si, grazie oregon, potrei chiederti un'altra cosa? Quando viene eseguito ricorsivamente il merge sort e si arriva al caso base, come fà ad ordinare gli elementi che ono diventati singoli per poi metterli insieme agli altri ordinati. Il meccanismo di fusione che ho implementato io è diverso da quello che ho postato prima, volevo capire come funzionasse, ma non capito esattamente cosa facessero quei cicli for.
  • Re: Problema con algoritmo merge sort

    Quel che non ho capito è: una volta che tutto l'array è diviso in parti indivisibili, come fa la funzione merge a rimetterli insieme in ordine? Come fa ad ordinarli? Io non ho visto nessuno meccanismo che facesse ciò dentro la munzione merge.
  • Re: Problema con algoritmo merge sort

    Nella mergeSort prima della chiamata alla merge inserisci una

    cout << "merge " << s << " " << d << endl;

    e vedrai che i pezzetti minimi sono fatti da due elementi che vengono messi in ordine dalla if..else nella merge.
    La if (s<d) assicura che il minimo pezzo sia di due elementi, quelli da un elemento non devono essere trattati, ovviamente.
  • Re: Problema con algoritmo merge sort

    Mi sei stato di grande aiuto, grazie mille per il consiglio, buona serata!
Devi accedere o registrarti per scrivere nel forum
5 risposte