unire l'ordinamento è duplicare le voci dell'array - java, array, algoritmo, ordinamento

Stavo cercando di implementare in Java il tipo di unionealgoritmo secondo la Introduzione agli algoritmi di Cormen. Il problema con il mio codice (sotto) è che l'array principale sta duplicando alcune delle sue voci durante la fase di unione.

Qualcuno è in grado di cogliere ciò che sto facendo di sbagliato?

Grazie!

  static void merge(int a[], int p, int q, int r)
{
int n1 = q - p;
int n2 = (r - q);
int [] left = new int[n1 + 1];
int [] right = new int[n2 + 1];
int pp = p;
int qq = q;
for(int i = 0; i < n1; i++)
{
left[i] = a[++pp];
}
for(int i = 0; i < n2; i++)
{
right[i] = a[++qq];
}
left[left.length-1] = Integer.MAX_VALUE;
right[right.length-1] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
for(int k = p; k < r; k++)
{
if(left[i] <= right[j])
{
a[k] = left[i];
i++;
}
else
{
a[k] = right[j];
j++;
}
}
}

static int [] mergeSort(int a[], int p, int r)
{
if(p < r)
{
int q = (p + r)/2;
mergeSort(a, 1, q);
mergeSort(a, q + 1, r);
merge(a, p, q, r);
}
return a;
}

risposte:

1 per risposta № 1

Parte del problema qui è l'esempio delapparentemente il libro usa un indice compreso tra 1 e lunghezza. Sarà più semplice se cambi l'intervallo dell'indice da 0 a lunghezza-1, che presumo nel resto della mia risposta.

Usa l'incremento post durante la copia su left [] e right [] come risposta da laune (dal range di indice 0 a lunghezza-1).

                left[i] = a[pp++];
...
right[i] = a[qq++];

Il problema principale è che la funzione di unione non sta controllando per vedere se ha raggiunto la fine della corsa sinistra o destra durante un'unione. Questo può essere risolto cambiando l'interno se a:

                if (i < n1 && (j >= n2 || left[i] <= right[j]))

Le chiamate ricorsive per unire l'ordinamento dovrebbero essere:

                mergeSort(a, p, q);
mergeSort(a, q, r);

Non visualizzato, ma la chiamata iniziale a mergeSort dovrebbe essere:

                mergeSort(a, 0, a.length);

Non è necessario allocare l'elemento aggiuntivo a sinistra e a destra (poiché l'intervallo dell'indice è compreso tra 0 e lunghezza-1).

            int [] left = new int[n1];
int [] right = new int[n2];

---

1 per risposta № 2

Penso che questo sia un errore (così come il suo fratello nel ciclo successivo):

left[i] = a[++pp];

Si desidera copiare a partire da pp = p, quindi non aumentare prima di accedere all'elemento array:

left[i] = a[pp++];

---