Fusion De Tri Java
Je suis en train de faire une fusion méthode de tri, mais il continue à donner le mauvais sortes. Où dois-je modifier pour le rendre réellement trier le tableau? Quelle partie du code doit être différente? Je vous remercie pour votre temps.
public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) {
int elements = (rHigh - lHigh +1) ;
int[] temp = new int[elements];
int num = left;
while ((left <= lHigh) && (right <= rHigh)){
if (a[left] <= array[right]) {
temp[num] = array[left];
left++;
}
else {
temp[num] = array[right];
right++;
}
num++;
}
while (left <= right){
temp[num] = array[left]; //I'm getting an exception here, and is it because of the num???
left += 1;
num += 1;
}
while (right <= rHigh) {
temp[num] = array[right];
right += 1;
num += 1;
}
for (int i=0; i < elements; i++){
array[rHigh] = temp[rHigh];
rHigh -= 1;
}
EDIT: maintenant, le mergeSort n'a pas vraiment de trier les nombres, quelqu'un peut-il me dire où il est spécifiquement? surtout quand j'ai l'impression que le "Test de la fusion de tri".
Umm.. êtes-vous essayer de faire fonctionner correctement ou tout simplement compiler?!
dans merge(), le premier appel à la fusion doit être du début à la centre, pas du début à la fin.
dans merge(), l'appel à mergeSort devrait être
Désolé, mon erreur, mais quand je l'appelle merge() la mergeSort donne le mauvais sortes, c'est à cause de la façon dont j'ai copié le tableau?
Voir mon édités réponse. Vous êtes certainement sur la bonne voie, vous mergeSort() de la fonction, doit cependant être complètement ré-écrit.
dans merge(), le premier appel à la fusion doit être du début à la centre, pas du début à la fin.
dans merge(), l'appel à mergeSort devrait être
mergeSort(newArray, start,center, center+1,end);
Désolé, mon erreur, mais quand je l'appelle merge() la mergeSort donne le mauvais sortes, c'est à cause de la façon dont j'ai copié le tableau?
Voir mon édités réponse. Vous êtes certainement sur la bonne voie, vous mergeSort() de la fonction, doit cependant être complètement ré-écrit.
OriginalL'auteur Sam | 2009-11-14
Vous devez vous connecter pour publier un commentaire.
Tout d'abord, je suppose que c'est académique, plutôt que de la pratique, puisque vous n'êtes pas à l'aide d'un construit en fonction de tri. Cela étant dit, voici un peu d'aide pour vous faire bouger dans la bonne direction:
Généralement, on peut penser à une fusion de sorte que deux méthodes différentes: une fusion() fonction qui fusionne deux listes triées dans une liste triée, et mergeSort() qui de manière récursive les sauts de la liste en un seul élément des listes. Depuis un seul élément de la liste est triée déjà, vous pour ensuite fusionner les listes ensemble dans une grande liste triée.
Voici une partie de la main gauche pseudo-code:
Peut-être que ça vous aidera à éclaircir où vous voulez aller.
Sinon, il y a toujours MergeSort sur wikipédia.
Supplémentaires:
Pour vous aider, voici quelques commentaires en ligne dans votre code.
Je suis délibérément vague, de sorte que vous pensez de l'algorithme. Essayez d'insérer vos propres commentaires dans le code. Si vous pouvez écrire ce qui est conceptuellement qui se passe, alors vous ne pouvez pas besoin de Débordement de Pile 🙂
Mes pensées sont ici que vous n'êtes pas mise en œuvre correctement. C'est parce que on dirait que vous êtes seulement de toucher les éléments du tableau qu'une seule fois (ou presque qu'une seule fois). Cela signifie que vous avez un mauvais scénario de O(N) Tri prend généralement au moins
O(N * log N)
et de ce que je sais, les versions simplifiées de fusion de tri sont en faitO(N^2)
.Plus:
Dans la plus simpliste de la mise en œuvre de la fusion de tri, je m'attends à voir une sorte de la récursivité dans le mergeSort() la méthode. C'est parce que la fusion de tri est généralement définie de manière récursive. Il y a des façons de le faire de manière itérative à l'aide de boucles for et while, mais je ne le recommande pas comme un outil d'apprentissage jusqu'à ce que vous obtenez de manière récursive.
Honnêtement, je suggère de prendre mon pseudo-code ou le pseudo-code que vous pouvez trouver dans un article de wikipédia à mettre en œuvre et recommencer avec votre code. Si vous faites cela et il ne fonctionne pas encore correctement, le poster ici et nous allons vous aider à travailler sur the kinks.
Cheers!
Et enfin:
voir mes dernières modifications.
Je ne peux vraiment pas vous aider sans voir comment vous appelez la méthode. Pouvez-vous poster quelques cas de test que vous utilisez?
non, mon commentaire avait pour but de dire à mettre en œuvre toutes les pseudo-code que vous avez besoin iL, iR, et num.
ah ha! Je vois ce que vous vouliez faire dans votre code maintenant. la première boucle while, fondamentalement, par rapport à tous les éléments jusqu'à ce que vous exécutez hors de paires, puis vous remplissez le reste du temp avec les éléments restants. il serait vraiment vous aider (et finalement) si vous avez écrit des commentaires comme préconditions et postconditions. commentaires vous aider à comprendre ce que vous faites.
OriginalL'auteur Jeremy Powell
OriginalL'auteur Varun Verma
Voici un autre!
OriginalL'auteur Sam Dozor
OriginalL'auteur Arun Dutta
>
De Fusion De Tri À L'Aide De Sentinelle
Ce codes fonctionne parfaitement bien.
OriginalL'auteur Akashdeep Singh
Voici une autre alternative:
}
OriginalL'auteur user3402754
package com;
OriginalL'auteur Tushar Mahajan