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!