scal sort to duplikowanie wpisów tablicy - java, tablice, algorytm, sortowanie

Próbowałem zaimplementować w Javie sortowanie scalającealgorytm według Cormen's Wprowadzenie do algorytmów. Problem z moim kodem (poniżej) polega na tym, że główna tablica powiela niektóre z jego wpisów podczas kroku scalania.

Czy ktoś jest w stanie uchwycić to, co robię źle?

Dziękuję Ci!

  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;
}

Odpowiedzi:

1 dla odpowiedzi № 1

Część problemu tutaj jest przykładem zksiążka najwyraźniej używa zakresu indeksu od 1 do długości. Będzie łatwiej, jeśli zmienisz zakres indeksu od 0 do długości-1, co zakładam w pozostałej części mojej odpowiedzi.

Użyj przyrostu postu podczas kopiowania do lewej [] i prawej [] zgodnie z odpowiedzią Laune (od zakresu indeksu 0 do długości-1).

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

Głównym problemem jest to, że funkcja scalania nie sprawdza, czy osiągnęła koniec lewego lub prawego przebiegu podczas scalania. Można to naprawić, zmieniając wewnętrzny, jeśli:

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

Wywołania rekurencyjne w celu scalenia sortowania powinny być:

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

Nie pokazano, ale początkowe wywołanie mergeSort powinno być:

                mergeSort(a, 0, a.length);

Nie ma potrzeby przydzielania dodatkowego elementu po lewej i prawej stronie (ponieważ zakres indeksu wynosi od 0 do długości-1).

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

---

1 dla odpowiedzi nr 2

Myślę, że jest to błąd (podobnie jak jego rodzeństwo w następnej pętli):

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

Chcesz skopiować zaczynając od pp = p, więc nie zwiększaj przed uzyskaniem dostępu do elementu tablicy:

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

---