Discussion:Tri par tas

Autres discussions [liste]

Admissibilité
Neutralité
Droit d'auteur
Article de qualité
Bon article
Lumière sur
À faire
Archives
Commons

Cet article est indexé par les projets Informatique et Mathématiques.

Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.

**Évaluation** de l’article « **Tri par tas** »
Avancement	Importance	pour le projet
Bon début	Faible		Informatique (discussion • critères • liste • stats • hist. • comité • stats vues)
Bon début	À évaluer		Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues)

Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.

Au départ, question de Alvaro "vous aimez la présentation xxx > xxx > xxx ?" portant sur la ligne:

Informatique > Algorithmique > Algorithmes de Tri > Tri par tas

à ce moment là en haut de l'article. Didup

en bas, pourquoi pas...

en haut, pas vraiment

Ce qui est important, c'est l'article, pas son placement dans une classification plus ou moins arbitraire...wikipédia n'est pas vraiment une structure en étoile...hum...qu'est ce que vous en pensez ?

J'aime bien, en haut ou en bas, ça m'est égal, mais il faudrait un séparateur, surtout en bas. L'intérêt n'est pas pour moi la structure en étoile (en arbre?) : on peut avoir plusieurs chemins/classfications sur certains articles, il me semble l'avoir déjà vu en histoire et je trouve ça bien aussi. L'intérêt c'est de donner des liens : il est naturel de vouloir remonter vers Algorithmes de tri (note : je trouve que tu as bien fait de renommer le lien, à mon avis, il faudrait renommer la page Tri aussi, elle ne parle que de d'algos). Et sur les dites pages, ça donne les liens inverses (pages liées). Inconvénient éventuel: pour les débuts de chemin, (ici Informatique), on va vraiment avoir beaucoup beaucoup de choses sur "pages liées". Si on pense que c'est mal, on peut se limiter à ne donner que la fin des chemins, seulement un ou deux niveaux supérieurs. Bien sur d'accord pour dire que le plus important, c'est l'article Didup

Oui, en haut, en bas... peu importe ; l'intérêt c'est les lien qui permettent de se balader et "qui sautent aux yeux", plus vite que de cliquer sur "pages liées".
Quant à la classification... c'est la colonne vertébrale d'une encyclopédie; on doit pouvoir accéder à tous les articles depuis les items proposés sur la page d'accueil (enfin, il me semble); alors, pourquoi ne pas mettre le "chemin inverse" dans l'article ? Et ça peut ouvrir des horizons à celui qui est arrivé sur un article donné par la fonction de recherche.
Personnellement je vois wikipedia comme une incitation à la balade dans le savoir.
Alvaro 15 avr 2003 à 20:46 (CEST)

Mais, je ne voulais absolumment pas dire que j'étais contre les liens ! C'est bien ce qu'on trouve dans Voir aussi non ?

Ce qui me pose souci c'est pourquoi cette classification la...bon, évidemment, je parle a des matheux, des fanas de la classification, et je serais bien incapable de vous donner un exemple avec Tris par tas :-)...alors je vais vous en donner un autre...pourquoi maïs descendrait t-il forcemment de agriculture ? Il peut aussi descendre organismes génétiquement modifiés qui lui même descend de biologie ainsi que de agronomie et transgénèse...pourquoi une "remontée" serait elle privilégiée par rapport à une autre ? Excusez moi, mais cela n'a pas de sens...on peut descendre, mais on ne peut pas remonter. Il y a potentiellement des miliers de chemins possibles.

Ce qui n'empêche pas de mettre les liens donnés par Alvaro dans l'article bien sur. Mais, la notion de chemin...je ne comprend pas du tout. Mais, si cela peut vous faire plaisir dans les articles de mathématiques...allez y...mais...quand il y aura un autre chemin menant a Tri par tas, allez vous ajouter tous les chemins remontant a Rome ??? LOL, amicalement Utilisateur:Anthere

J'aime bien, à condition de l'en mettre que quand ça a un sens, ie quand un article à une place claire dans la hiérarchie ébauchée en page principale. S'il a deux ou trois positions, mieux vaut soit les mettre toutes, soit n'en mettre aucune. Par contre, il ne faut pas, àmha, que ça devienne une obligation ou quelque chose de systématique.

Pour la position, je préfère en haut en principe, mais il est vrai que ça charge un peu la page... L'idéal serait d'avoir des balises (quelque chose du genre <position> </position> pour ça, et de pouvoir configurer la façon dont ça s'affiche, un peu comme pour les liens interwiki. --- MM

Par contre, ce que j ai déjà vu evoquer sur la main liste, serait le fait de suivre le chemin que "nous" avons suivi...de façon a retourner directement a un article consulté précédemment dans la cession, sans avoir a faire 10 retours successifs...ce sera sympa aussi...

Je poursuis: ce n'est pas criant sur le tri par tas, mais bcp plus sur le Tri par insertion où il n'y a nulle mention d'informatique, d'algo ou de quoi que ce soit; ok, il y a les autres tris en bas de page, mais...
Il ne faut rien d'obligatoire. C'est peut-être redondant... je n'en sais rien, j'ai eu cette idée... parce qu'on voit souvent des choses de ce genre sur la toile. En fonction des réactions...
La notion de chemin... je pense (sûr de moi à 47%) qu'à partir de la page d'accueil on doit arriver à tous les articles euh... sans détour?
Ce principe doit être applicable facilement dans certains cas, comme ici ou dans le cas de la classification "traditionnelle" du viavnt; va falloir que je réfléchisse plus avant à mon argumentaire ;D
Alvaro 15 avr 2003 à 21:23 (CEST)

explication[modifier le code]

À propos de ce diff. Il me semble que la correction apportée par 195.83.11.66 est justifiée :

         n                                1
       /   \          exemple :          / \    (je me suis pas foulé pour l'exemple :o)
      2n   2n+1                         2   3

On peut en discuter un peu plus si ça pose problème ; en attendant, je rétablis la version précédente qui me semble correcte. Wiz ¨ 17 décembre 2005 à 01:13 (CET)[répondre]

y a un truc qui cloche dans le pseudo code[modifier le code]

on a un tableau de longueur longueur on commence la procedure avec i=longueur/2 on tamise(longueur=longueur,noeud=i)

et on peut arriver à une ligne (dans la procedure tamise):

i=2i

==> i=longueur

et dans la boucle suivante (de la procedure tamise), on teste arbre(2i+1)

==> indice arbre=2*longueur+1 >longueur tableau

Me trompje?

Je suis d'accord avec vous et je me suis permis de rectifier ce pseudo-code (Backtracking)

Définition de tas[modifier le code]

Pour la définition de tas, ne serait-il pas mieux de faire simplement un lien vers l'article eponyme -- qui semble de plus assez complet ?

Faire un lien, oui (je viens de le faire). Mais remplacer l'explication par un lien, je suis assez fortement contre : on peut très bien comprendre le tri par tas sans tout savoir sur les tas, pourquoi donc imposer au lecteur de se référer à un autre article ? Une information peut très bien apparaître plusieurs fois dans Wikipédia, fort heureusement. MM (pas Utilisateur:MM) 6 août 2006 à 18:04 (CEST)[répondre]

Je viens d'enlever la phrase "Notons qu'avec cette représentation, les sous-tas (enracinés n'importe où, et finissant n'importe où) sont des sous-tableaux contigus. Toutes les procédures de l'algorithme travaillant sur cette représentation des tas s'appliquent donc naturellement aux sous-tas ce qui permet la récursivité" dans la section principe.

Les fils de l'élement n sont 2n et 2n+1, ce qui contredit la contiguïté. En exemple, le sous-tas du fils gauche de la racine commence par les élements d'indice 2,4,5,8,9,10,11,... Il y a "contiguïté par morceau", mais pas contiguïté.

Si l'implementation en Pascal est comme celle de C#, alors elle fonctionne à l'envers et contient des choses qui n'ont rien à voir avec le tri. Je n'ai pas de quoi la tester et la modifier, donc si une âme charitable passe par ici, cela vaut le coup de la vérifier. 193.57.56.10 (d) 16 décembre 2009 à 17:04 (CET)[répondre]

Tri rapide sur les derniers éléments[modifier le code]

J'ai supprimé la remarque sur l'utilisation du tri rapide pour trier les derniers éléments, pour la raison suivante : le tri rapide étant normalement plus rapide que le tri par tas, il me semble qu'il n'y a pas plus de raison de l'utiliser pour les 25 derniers éléments que de l'utiliser pour tout le tableau (et même si les éléments sont à peu près à l'envers, ça ne rend pas le tri rapide particulièrement efficace, puisque le meilleur cas du tri rapide est en n log n). Nordald (d) 16 mai 2010 à 18:54 (CEST)[répondre]

Pseudo-code faux (?)[modifier le code]

Bonjour,

Nous sommes étudiants et travaillons actuellement sur un projet utilisant les tas binaires. Après s'être creusée la tête un moment nous pensons que le pseudo-code de la fonction "tri_par_tas" est faux :

fonction tri_par_tas(arbre,longueur):
  pour i:=longueur/2 a 1
    tamiser(arbre,i,longueur)
  fin pour
  pour i:=longueur a 2
    échanger arbre[i] et arbre[1]
    tamiser(arbre,1,i-1) //Cette ligne
  fin pour
fin fonction

Seul le sous-arbre composé de la racine et de ces deux fils est tamisé, ce qui résulte en un tas qui ne sera pas "trié suivant l'ordre croissant". Nous préférons cependant une confirmation avant d'éditer la page du Wiki.

À vos crayons !