A voir également:
- Heap sort / tri par tas
- Trier une liste python sans sort - Forum - Python
- Tri à bulles en python 3.0 à partir d'un algorithme ✓ - Forum - Python
- [Python] Ordonner / filter / trier ??? ✓ - Forum - Python
- Trier un tableau sans utiliser la fonction sort - Conseils pratiques - Perl
- Trier un tableau d'entier avec ARRAYS.SORT(); ✓ - Forum - Programmation
4 réponses
KX
- Messages postés
- 16248
- Date d'inscription
- samedi 31 mai 2008
- Statut
- Modérateur
- Dernière intervention
- 20 février 2021
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.
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.
Whismeril
- Messages postés
- 15593
- Date d'inscription
- mardi 11 mars 2003
- Statut
- Contributeur
- Dernière intervention
- 22 février 2021
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
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
charline159
- Messages postés
- 123
- Date d'inscription
- lundi 14 août 2017
- Statut
- Membre
- Dernière intervention
- 21 février 2021
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 ?
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)); } }
Whismeril
- Messages postés
- 15593
- Date d'inscription
- mardi 11 mars 2003
- Statut
- Contributeur
- Dernière intervention
- 22 février 2021
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.
KX
- Messages postés
- 16248
- Date d'inscription
- samedi 31 mai 2008
- Statut
- Modérateur
- Dernière intervention
- 20 février 2021
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
À lire attentivement : Plagier, c’est frauder et risquer des sanctions
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
charline159
- Messages postés
- 123
- Date d'inscription
- lundi 14 août 2017
- Statut
- Membre
- Dernière intervention
- 21 février 2021
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
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 ?
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 ?
KX
- Messages postés
- 16248
- Date d'inscription
- samedi 31 mai 2008
- Statut
- Modérateur
- Dernière intervention
- 20 février 2021
- 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.
Tu dois donc appeler la méthode sort uniquement, c'est elle qui appelera heapify comme il faut.
charline159
- Messages postés
- 123
- Date d'inscription
- lundi 14 août 2017
- Statut
- Membre
- Dernière intervention
- 21 février 2021
- 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!
merci à toi!
J'ai échangé par MIN_VALUE mais ça me fait juste le problème inverse, avec des [-2147483648, 1, -2147483648, -2147483648, -2147483648, -2147483648, -2147483648].