Mergesort en Java
Je suis nouveau sur Java et ont essayé de mettre en œuvre mergesort en Java. Cependant, même après avoir exécuté le programme plusieurs fois, au lieu de l'souhaité triés sortie, j'obtiens le même utilisateur donné en entrée comme en sortie. Je serais reconnaissant si quelqu'un pouvait m'aider à comprendre ce comportement inattendu.
import java.io.*;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) throws IOException{
BufferedReader R = new BufferedReader(new InputStreamReader(System.in));
int arraySize = Integer.parseInt(R.readLine());
int[] inputArray = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
inputArray[i] = Integer.parseInt(R.readLine());
}
mergeSort(inputArray);
for (int j = 0; j < inputArray.length; j++) {
System.out.println(inputArray[j]);
}
}
static void mergeSort(int[] A) {
if (A.length > 1) {
int q = A.length/2;
int[] leftArray = Arrays.copyOfRange(A, 0, q);
int[] rightArray = Arrays.copyOfRange(A,q+1,A.length);
mergeSort(leftArray);
mergeSort(rightArray);
A = merge(leftArray,rightArray);
}
}
static int[] merge(int[] l, int[] r) {
int totElem = l.length + r.length;
int[] a = new int[totElem];
int i,li,ri;
i = li = ri = 0;
while ( i < totElem) {
if ((li < l.length) && (ri<r.length)) {
if (l[li] < r[ri]) {
a[i] = l[li];
i++;
li++;
}
else {
a[i] = r[ri];
i++;
ri++;
}
}
else {
if (li >= l.length) {
while (ri < r.length) {
a[i] = r[ri];
i++;
ri++;
}
}
if (ri >= r.length) {
while (li < l.length) {
a[i] = l[li];
li++;
i++;
}
}
}
}
return a;
}
}
source d'informationauteur tinker
Vous devez vous connecter pour publier un commentaire.
Ici est une version corrigée de votre code:
Lorsque vous relier
A
dansmergeSort()
:cela n'a aucun effet dans
inputArray
dansmain()
.Vous avez besoin de retourner le tableau trié de
mergeSort()
de la même manière que vous le retourner à partir demerge()
.et dans
main()
:Le problème, c'est que java est le passage par valeur et par référence... Lors de l'affectation d'Un tableau dans la méthode de fusion vous modifiez une copie de la référence à l'Un et pas la référence à elle-même. Par conséquent, vous devez passer Une dans votre méthode de fusion et de faire un changement structurel à A.
Le problème se situe ici:
Maintenant de fusion de la matrice de fait ceci:
Quand vous avez commencé, était une référence à inputArray. Mais alors vous avez choisi d'être ce que venait de fusionner. Malheureusement, cela ne touche pas à ce inputArray est dans la méthode main. Qui dit en gros "Oh regarde tout le travail que vous avez fait... le jeter!"
Vous pouvez changer cela avec quelque chose comme
Ensuite dans votre méthode principale, vous pouvez le faire
En supposant que votre
merge
fonction est correcte:Depuis que nous avons besoin de retourner le tableau, nous retourner
A
non modifié, si elle n'a qu'un seul élément, sinon nous fusionner les résultats de trier les parties gauche et droite de la matrice.Les codes ci-dessus sont un peu confus
Ne jamais utiliser des variables avec des noms: "k", "j", "m",... ce qui rend le code beaucoup de confusion
Suit le code d'une manière plus facile...
Pourrait tout aussi bien ajouter mon point de vue sur ceci:
Prend deux int tableaux et les fusionne.
Où "résultat" est un tableau de taille.longueur + b.longueur