En informatique, le tri par tas est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale, c'est-à-dire que l'on démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure. Sa complexité est proportionnelle à où est la longueur du tableau à trier. Le tri par tas se fait en place, c’est-à-dire qu’il ne nécessite pas l'allocation d'une zone mémoire supplémentaire (plus précisément il ne nécessite qu'une allocation d'une zone mémoire de taille ). Par contre, il n'est pas stable.

Property Value
dbo:abstract
  • En informatique, le tri par tas est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale, c'est-à-dire que l'on démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure. Sa complexité est proportionnelle à où est la longueur du tableau à trier. Le tri par tas se fait en place, c’est-à-dire qu’il ne nécessite pas l'allocation d'une zone mémoire supplémentaire (plus précisément il ne nécessite qu'une allocation d'une zone mémoire de taille ). Par contre, il n'est pas stable. Son inconvénient majeur est sa lenteur comparé au tri rapide (qui est en moyenne deux fois plus rapide[réf. nécessaire]) : sur un tableau de taille importante, il sera amené à traiter un nombre élevé d'emplacements mémoire dont l’éloignement peut dépasser la capacité du cache, ce qui ralentit l'accès à la mémoire et l’exécution de l’algorithme. (fr)
  • En informatique, le tri par tas est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale, c'est-à-dire que l'on démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure. Sa complexité est proportionnelle à où est la longueur du tableau à trier. Le tri par tas se fait en place, c’est-à-dire qu’il ne nécessite pas l'allocation d'une zone mémoire supplémentaire (plus précisément il ne nécessite qu'une allocation d'une zone mémoire de taille ). Par contre, il n'est pas stable. Son inconvénient majeur est sa lenteur comparé au tri rapide (qui est en moyenne deux fois plus rapide[réf. nécessaire]) : sur un tableau de taille importante, il sera amené à traiter un nombre élevé d'emplacements mémoire dont l’éloignement peut dépasser la capacité du cache, ce qui ralentit l'accès à la mémoire et l’exécution de l’algorithme. (fr)
dbo:discoverer
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 12162 (xsd:integer)
dbo:wikiPageInterLanguageLink
dbo:wikiPageLength
  • 7397 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 186643147 (xsd:integer)
dbo:wikiPageWikiLink
prop-fr:wikiPageUsesTemplate
prop-fr:wikibooks
  • Implémentation d'algorithmes classiques/Algorithmes de tri/Tri par tas (fr)
  • Implémentation d'algorithmes classiques/Algorithmes de tri/Tri par tas (fr)
prop-fr:wikibooksTitre
  • Implémentations du tri par tas (fr)
  • Implémentations du tri par tas (fr)
dct:subject
rdfs:comment
  • En informatique, le tri par tas est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale, c'est-à-dire que l'on démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure. Sa complexité est proportionnelle à où est la longueur du tableau à trier. Le tri par tas se fait en place, c’est-à-dire qu’il ne nécessite pas l'allocation d'une zone mémoire supplémentaire (plus précisément il ne nécessite qu'une allocation d'une zone mémoire de taille ). Par contre, il n'est pas stable. (fr)
  • En informatique, le tri par tas est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale, c'est-à-dire que l'on démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure. Sa complexité est proportionnelle à où est la longueur du tableau à trier. Le tri par tas se fait en place, c’est-à-dire qu’il ne nécessite pas l'allocation d'une zone mémoire supplémentaire (plus précisément il ne nécessite qu'une allocation d'une zone mémoire de taille ). Par contre, il n'est pas stable. (fr)
rdfs:label
  • Heapsort (ca)
  • Heapsort (de)
  • Heapsort (nl)
  • Heapsort (sv)
  • Sắp xếp vun đống (vi)
  • Tri par tas (fr)
  • ヒープソート (ja)
  • 堆排序 (zh)
  • Heapsort (ca)
  • Heapsort (de)
  • Heapsort (nl)
  • Heapsort (sv)
  • Sắp xếp vun đống (vi)
  • Tri par tas (fr)
  • ヒープソート (ja)
  • 堆排序 (zh)
rdfs:seeAlso
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:basedOn of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is oa:hasTarget of
is foaf:primaryTopic of