Problema con algoritmo merge sort
Inviato: 15/07/2018, 15:43
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:
- 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!