Heap sort / tri par tas [Résolu]

Signaler
Messages postés
123
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
21 février 2021
-
Messages postés
123
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
21 février 2021
-
Bonjour,
j'ai essayé d'implémenter le tri par tas. Cependant, j'obtiens des résultats astronomiques lorsque je l'applique à un tableau.
Par exemple, avec le tableau [11, 7, 9, 14, 14, 4, 14], je vais obtenir [14, 2147483647, 2147483647, 2147483647, 14, 9, 4].

Avez-vous une idée d'où cela peut venir?

Cordialement

package com.company;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class TriTas {

    static int[] tab;
    static int count;


    /** génère une priority queue
     * d'entiers aléatoires
     * de longueur n
     */
    static int[] priorityQueue(int n){
        tab = new int[n];

        int i = 0;
        while (i<n){
            int element = new Random().nextInt(15);
            tab[i] = element;
            i++;
        }
        count = 0;

        return tab;
    }



    // tas
    void tasHaut(int x){
        if(x<=0){ // cas de base
            return;}
        int par = (x-1)/2;

        int tmp;
        if(tab[x-1] < tab[par]){
            tmp = tab[par];
            tab[par] = tab[x-1];
            tab[x-1] = tmp;
            tasHaut(par+1);
        }
    }


    void insert(int valeur){
        if(count == tab.length){
            System.out.println("impossible");
            return; // quitte sans rien retourner
        }
        tab[count++] = valeur;
        tasHaut(count);
    }


    void tasBas(int index){
        if (index >=tab.length){ // cas de base
            return;
        }

        int min = index;
        int gauche = 2*index;
        int droit = gauche+1;
        int tmp;

        if (gauche<tab.length && tab[index] > tab[gauche]){
            min = gauche;
        }

        if (droit < tab.length && tab[min] > tab[droit]){
            min = droit;
        }

        if (min!=index){
            tmp = tab[min];
            tab[min] = tab[index];
            tab[index] = tmp;
            tasBas(min);
        }
    }


    int min(){ //trouve le minimum
        int min = tab[0];
        tab[0] = Integer.MAX_VALUE;
        tasBas(0);
        return min;
    }


    static void TriTas(int[] tab){
        TriTas priorityQueue = new TriTas();
        int i;
        for (i=0; i<tab.length;i++){
            priorityQueue.insert(tab[i]);
        }
        for (i=0; i<tab.length;i++){
            tab[i] = priorityQueue.min();
        }
    }




    /** test
     * tri par tas
     */
    public static void main(String[] args) {

        int[] tableau = priorityQueue(7);
        System.out.println("la priority queue générée est: " + Arrays.toString(tableau));
        TriTas(tableau);
        System.out.println("\ntri par tas: " + Arrays.toString(tableau));

    }
}

4 réponses

Messages postés
16248
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
20 février 2021
2 796
Bonjour,

Je n'ai pas regardé le code dans le détail, mais la valeur 2147483647 ne sort pas de nul part, c'est Integer.MAX_VALUE que tu as mis ligne 88.
Messages postés
123
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
21 février 2021
1
Salut, et merci pour ta réponse.

J'ai échangé par MIN_VALUE mais ça me fait juste le problème inverse, avec des [-2147483648, 1, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648].
Messages postés
15593
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
22 février 2021
662
Bonjour
Selon le commentaire, la méthode min est sensée chercher la valeur minimale.
C’est pas du tout ce qu’elle fait.

Elle mets le valeurs de tab[0] dans une variable min, affecte int.MinValue à tab[0], puis retourne min. => des données à trier et pas de recherche
Messages postés
15593
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
22 février 2021
662
As tu eu un cours ou as fait des recherches sur le tri par tas?
Car selon les miennes, il n'y a pas besoin de chercher la valeur minimale du tableau.
Messages postés
123
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
21 février 2021
1
Oui j'ai eu un cours mais j'ai pas tout saisi du coup j'ai essayé de regarder sur internet et je pensais que c'était correct.
Mais la méthode min() est appelée dans la fonction TriTas(), c'est pas correct ?

Sinon il y a également cette façon de faire, mais je vois pas pourquoi elle renvoie pas le bon résultat ?

package com.company;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class TriTas {

    static int[] tab;
    static int count;


    /** génère une priority queue
     * d'entiers aléatoires
     * de longueur n
     */
    static int[] priorityQueue(int n){
        tab = new int[n];

        int i = 0;
        while (i<n){
            int element = new Random().nextInt(15);
            tab[i] = element;
            i++;
        }
        count = 0;

        return tab;
    }


    static public void sort(int arr[]) {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Heap sort
        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify root element
            heapify(arr, i, 0);
        }
    }

    static void heapify(int arr[], int n, int i) {

        // Find largest among root, left child and right child
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        // Swap and continue heapifying if root is not largest
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }




    /** test
     * tri par tas
     */
    public static void main(String[] args) {

        int[] tableau = priorityQueue(7);
        System.out.println("la priority queue générée est: " + Arrays.toString(tableau));

        int max = Arrays.stream(tableau).max().getAsInt();
        System.out.println("le max est: " + max);

        heapify(tableau, tableau.length, Arrays.stream(tableau).max().getAsInt());
        System.out.println("\ntri par tas: " + Arrays.toString(tableau));

    }
}

Messages postés
15593
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
22 février 2021
662
du coup j'ai essayé de regarder sur internet

Ha oui? C'est étonnant quand même, parce quand je tape "tri par tas" dans mon moteur de recherche favori, la première occurence pointe vers un site "pas trop" connu : Wikipedia.

Même si l'explication peut mériter de la relire 2 ou 3 fois, il y a un pseudo code en bas.
Il ressemble beaucoup plus à ton code du message 5 qu'au premier.
Messages postés
15593
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
22 février 2021
662 >
Messages postés
15593
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
22 février 2021

Mais pas tout à fait quand même
Messages postés
16248
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
20 février 2021
2 796
Bonjour,

Tout d'abord je parlerais rapidement de ton premier code, il faut absolument arrêter de mélanger le code static et le code objet.

Quelques morceaux choisis : ligne 7 tu créés une classe TriTas, lignes 94 et 95 tu as une méthode static TriTas qui créé un objet TriTas qui manipule des méthodes d'objets qui se basent tous sur les attributs tab et count des lignes 9 et 10... qui sont static.
Très honnêtement c'est impossible de déterminer le nombre d'effet de bords que peux engendrer ce genre de code, tellement ça s'emmêle.

Passons au deuxième code, qui est un copier-coller d'internet, on le retrouve notamment dans cet article très complet qui détaille pas à pas le fonctionnement du tri par tas (que tu devrais lire...)
https://www.programiz.com/dsa/heap-sort
Le programme fonctionne très bien, à condition d'appeler la méthode
sort(tableau);
et pas juste heapify.

À lire attentivement : Plagier, c’est frauder et risquer des sanctions
Messages postés
15593
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
22 février 2021
662
Salut, ha oui, j'avais même pas fait attention à tout ça.....
Messages postés
123
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
21 février 2021
1
Oui, c'est précisément sur cette page que je l'ai pris.
J'ai lu les explications également. Comme j'ai pas très bien compris, je veux trouver une version et la tester de mon côté, puis essayer de retenir ce que j'ai pu tester, et donc si possible ré-implémenter ce que j'aurais pu en tirer.

Là par exemple, avec un simple copier/coller, je suis même pas capable de faire marcher ce code, alors j'aimerais résoudre le problème avant de passer à l'étape suivante.

je viens de faire un
sort(tableau);
heapify(tableau, tableau.length, 0);

mais je passe de [1, 10, 6, 8, 6, 12, 6] à [6, 8, 6, 6, 1, 10, 12] ? Je n'ai pas appelé les méthodes sort et heapify correctement ?
Messages postés
16248
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
20 février 2021
2 796 >
Messages postés
123
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
21 février 2021

heapify ne sert qu'à faire fonctionner la méthode sort, c'est d'ailleurs pour ça que sort est public mais pas heapify.

Tu dois donc appeler la méthode sort uniquement, c'est elle qui appelera heapify comme il faut.
Messages postés
123
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
21 février 2021
1 >
Messages postés
16248
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
20 février 2021

oui effectivement... il faudrait vraiment que je fasse quelque chose pour mon niveau de programmation...
merci à toi!