le tri de fusion duplique les entrées de tableau - Java, tableaux, algorithme, tri

J'essayais d'implémenter en Java le type de fusionalgorithme selon "Introduction aux algorithmes de Cormen". Le problème avec mon code (ci-dessous) est que le tableau principal duplique certaines de ses entrées lors de la fusion.

Est-ce que quelqu'un peut attraper ce que je fais mal?

Je vous remercie!

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

Réponses:

1 pour la réponse № 1

Une partie de la question ici est l'exemple de laLe livre utilise apparemment une plage d'index allant de 1 à longueur. Ce sera plus simple si vous changez la plage d'index de 0 à longueur-1, ce que je suppose dans le reste de ma réponse.

Utilisez post incrément lors de la copie à gauche [] et à droite [] comme indiqué par laun (de 0 à 1).

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

Le problème principal est que la fonction de fusion ne vérifie pas si elle a atteint la fin de l'exécution à gauche ou à droite lors d'une fusion. Cela peut être corrigé en modifiant le si intérieur à:

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

Les appels récursifs pour fusionner le tri doivent être:

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

Non affiché, mais l'appel initial à mergeSort devrait être:

                mergeSort(a, 0, a.length);

Il n’est pas nécessaire d’allouer l’élément supplémentaire à gauche et à droite (la plage d’index allant de 0 à longueur-1).

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

---

1 pour la réponse № 2

Je pense que c'est une erreur (ainsi que son frère dans la boucle suivante):

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

Vous voulez copier en commençant par pp = p, ne pas incrémenter avant d’accéder à l’élément de tableau:

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

---