Tri fusion en java

Résolu/Fermé
lwdu76 Messages postés 68 Date d'inscription samedi 16 janvier 2021 Statut Membre Dernière intervention 8 novembre 2022 - Modifié le 1 févr. 2022 à 13:39
lwdu76 Messages postés 68 Date d'inscription samedi 16 janvier 2021 Statut Membre Dernière intervention 8 novembre 2022 - 23 févr. 2022 à 11:30
Salut,
j'ai un problème avec mon tri fusion, il ne tri pas correctement les valeurs alors que l'algorithme me semble bien implémenter.

class TableauElement
public void triFusion (Element [] tableau, int indiceDebut, int indiceFin) { // Création d'une méthode triFusion sans paramètres, qui utilise le tri fusion avec des paramètres tableau, indiceDebut et indiceFin 

        if (indiceDebut < indiceFin && indiceDebut <= 0) { // Si l'indiceDebut est inférieur à l'indiceFin et que l'indiceDebut est invérieur à 0 du tableau d'élément

            int indiceMilieu = (indiceDebut + indiceFin / 2); // Indice du milieu est une fusion de l'indice du début et de fin

            triFusion (tableau, indiceDebut, indiceMilieu); // Indice du début et du milieu ne bouge pas dans le tri fusion 

            triFusion (tableau, indiceMilieu + 1, indiceFin); // Indice du milieu augmente et l'indice de fin bouge pas dans le tri fusion 

            fusion (tableau, indiceDebut, indiceMilieu, indiceFin); // Fusion de l'indice du début, milieu et de fin

            operationElementaireTriFusion = operationElementaireTriFusion + 4; // Nombre d'opérations élémentaire du tri fusion
        }
    }

    public void fusion (Element [] tableau, int indiceDebut, int indiceMilieu, int indiceFin) { // Création d'une méthode fusion, qui utilise la fusion avec des paramètres tableau, indiceDebut, indiceMilieu et indiceFin 

        int indice1 = indiceMilieu - indiceDebut + 1; // Indice1 est l'indice du milieu moins celui du debut
        int indice2 = indiceFin - indiceMilieu; // Indice2 est l'indice de la fin moins celui du milieu
 
        Element Gauche [] = new Element [indice1]; // Création d'un nouvel indice1 à gauche
        Element Droite [] = new Element [indice2]; // Création d'un nouvel indice2 à droite

        operationElementaireTriFusion = operationElementaireTriFusion + 4; // Nombre d'opérations élémentaire du tri fusion
 
        for (int i = 0; i < indice1; i++) { // Compte l'indice1

            Gauche [i] = tableau [indiceDebut + i]; // L'élément gauche est l'indiceDebut augmente
        
            for (int j = 0; j < indice2; j++) { // Compte l'indice2

                Droite [j] = tableau [indiceMilieu + 1 + j]; // L'élément droit est l'indiceMilieu augmente

                operationElementaireTriFusion++; // Nombre d'opération élémentaire du tri fusion augmente
            }
        }
        
        int i = 0; // Initialise i
        int j = 0; // Initialise j

        int k = indiceDebut; // K est l'indice du début

        while (i < indice1 && j < indice2) { // Tant que i est inférieur à l'indice1 et que j est inférieur à l'indice2
            
            if (Gauche [i].getCle () <= Droite [j].getCle ()) { // Si la clé de l'élément gauche est inférieur à celle de droite 

                tableau [k] = Gauche [i]; // Tableau k est l'élément gauche
                
                i++; // I augmente
            
            } else { // Sinon on retourne
                
                tableau [k] = Droite [j]; // Tableau k est l'élément droit

                j++; // J augmente

                operationElementaireTriFusion = operationElementaireTriFusion + 3; // Nombre d'opérations élémentaire du tri fusion
            }

            k++; // K augmente
        }
 
        while (i < indice1) { // Tant que i est inférieur à l'indice1

            tableau [k] = Gauche [i]; // Tableau k est l'élément gauche

            i++; // I augmente
            
            k++; // K augmente

            operationElementaireTriFusion = operationElementaireTriFusion + 2; // Nombre d'opérations élémentaire du tri fusion
        }
 
        while (j < indice2) { // Tant que j est inférieur à l'indice2

            tableau [k] = Droite [j]; // Tableau k est l'élément droit

            j++; // J augmente
            
            k++; // K augmente

            operationElementaireTriFusion = operationElementaireTriFusion + 2; // Nombre d'opérations élémentaire du tri fusion
        }
    }

    public void afficherTriFusion (){ // Création d'une méthode afficherTriFusion sans paramètres, qui affiche le tri fusion 
        
        if (this.taille > 0) { // Si la taille du tableau est supérieur à 0

            System.out.println ("Tableau Fusion avant triFusion    : \n" + this); // Affiche les éléments du tableau avant le tri fusion

            double debutTempsTriFusion = System.nanoTime (); // Début du temps pour le tri fusion donné en nanosecondes

            this.triFusion (this.elements, 0, this.getTaille () - 1); // Tri fusion 

            double finTempsTriFusion = System.nanoTime (); // Fin du temps pour le tri fusion donné en nanosecondes

            System.out.println ("Tableau Fusion apres triFusion : \n" + this); // Affiche les éléments du tableau après le tri fusion

            afficherDuree ("Tri Fusion", debutTempsTriFusion, finTempsTriFusion); // Affiche la durée du tri fusion

            System.out.println ("Nombre d'operations elementaires tri fusion : " + operationElementaireTriFusion); // Affiche le nombre d'opérations élémentaires du tri fusion

        } else { // Sinon on retourne, que le tableau par tri fusion est inférieur à 0 

            System.out.println ("Tableau Fusion de taille <= 0"); // Affiche que le tableau par tri fusion est inférieur à 0 
        }
    }

class Element

public class Element { // Création d'une class Element

    private int cle; // Clé de l'élément 

    private String valeur; // Valeur de l'élément 

    public Element (){ // Création d'un constructeur de l'Element sans paramètres cle et valeur, qui sont la clé et la valeur de l'élément

        this.cle = 0;

        this.valeur = null;
    }

    public Element (int cle, String valeur) { // Création d'un constructeur de l'Element avec des paramètres cle et valeur, qui sont la clé et la valeur de l'élément
        
        this.cle = cle;

        this.valeur = valeur;
    }

    public Element (Element element) { // Création d'un constructeur par recopie de l'Element avec un paramètre element, qui est l'élément à recopier 
        
        this.cle = element.cle;
        
        this.valeur = element.valeur;
    }

    public int getCle (){ // Création d'un accesseur Cle, qui retourne la clé de l'élément 

        return this.cle;
    }

    public void setCle (Element element) { // Création d'une méthode Cle, qui modifie la clé de l'élément avec le paramètre element 

        this.cle = element.cle;
    }
    
    public String getValeur (){ // Création d'un accesseur Valeur, qui retourne la valeur de l'élément 

        return this.valeur;
    }


    public void setValeur (Element element) { // Création d'une méthode Valeur, qui modifie la valeur de l'élément avec le paramètre element
    
        this.valeur = element.valeur;
    }

    public String toString (){ // Création d'un String (méthode) toString, qui affiche le contenu de la cellule sous forme de chaine de caractère

        String string; // Affiche la chaine de caractère 

        string = this.cle + " " + this.valeur; // Clé et valeur de l'élément
        
        return string; // Retourne la clé et la valeur de l'élément
    }
}
class Test

import java.util.Scanner; // Import l'outil Scanner

public class Test { // Création d'une class Test  
    public static void main (String [] arguments) { // Création d'une méthode statique main, qui renvoit une chaine de caractère en arguments

        TableauElement tableauFusionEntree       = new TableauElement (); // Création d'un nouveau tableauFusionEntree, qui entre les éléments du tableau fusion

        int tailleAleatoire = TableauElement.demanderTaille (); // Taille aléatoire du tableau fusion 

        TableauElement tableauFusion        = new TableauElement (tailleAleatoire); // Création d'un nouveau tableauFusion, qui donne une taille aléatoire du tableau fuion

        int grandeur = TableauElement.demanderBorne (); // Demande la grandeur de la clé d'élément 

        tableauFusion.remplir (grandeur); // Rempli le tri fuson par la grandeur de la clé d'élément 

        System.out.println ("\n" + "*************** Tableaux remplis au clavier ***************" + "\n"); // Affiche les tableaux remplis au clavier, pour les petites valeurs (100) 

        tableauFusionEntree.afficherTriFusion (); // Affiche le tri fusion

        System.out.println ("\n" + "*************** Tableaux remplis aleatoirement ***************" + "\n"); // Affiche les tableaux remplis aléatoirement, pour les grandes valeurs (15000) 
        
        tableauFusion.afficherTriFusion (); // Affiche le tri fusion
    }
}
A voir également:

3 réponses

KX Messages postés 16747 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 9 juillet 2024 3 017
1 févr. 2022 à 20:59
Bonjour,

Je n'ai pas allumé le PC pour tester ton programme, mais en lisant rapidement le code il y a une erreur qui me saute aux yeux dès le début.
int indiceMilieu = (indiceDebut + indiceFin / 2);

Normalement le milieu devrait être calculé comme ceci :
int indiceMilieu = (indiceDebut + indiceFin) / 2;
lwdu76 Messages postés 68 Date d'inscription samedi 16 janvier 2021 Statut Membre Dernière intervention 8 novembre 2022
1 févr. 2022 à 21:24
Ah oui merci c´est une erreur d'étourderie
0
lwdu76 Messages postés 68 Date d'inscription samedi 16 janvier 2021 Statut Membre Dernière intervention 8 novembre 2022
1 févr. 2022 à 21:34

Il me donne ceci
0