Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithmes de tri corrige des exercices

Chapitre informatique commune Corrigé des exercices Tris par comparaison ? Exercice ? def minimum t j if j len t ?? return j i minimum t j if t j t i return j else return i def selectsort t j if j len t ?? i minimum t j if i j t i t j t j t i selectsort t j def insere t j if j and t j t j ?? t j ?? t j t j t j ?? insere t j ?? def insertionsort t j if j len t insere t j insertionsort t j ? Exercice ? Observons la situation après avoir déjà trouvé les j plus petits éléments et déterminé l ? endroit o? se trouve l ? élément j j j non trié La partie non triée correspond à une permutation de S j n Si on les suppose toutes équiprobables la probabilité pour que j soit situé à son endroit dé ?nitif et ne nécessite donc pas de permutation est égale à n ?? j ?? Le nombre de permutation moyen est donc égal à n ?? j n ?? j n ?? ?? n ?? n n ?? ln n ?? ? o n ??j k j k ? Exercice ? Lorsqu ? on parcourt le tableau de la gauche vers la droite en permutant deux éléments consécutifs à chaque fois que l ? élément le plus petit se trouve à droite du plus grand on est assuré en ?n de parcours d ? avoir placé le plus grand élément du tableau à sa place dé ?nitive en ayant e ?ectué n ?? comparaisons et au plus n ?? permutations Il reste à réitérer le procédé sur le tableau privé de sa dernière case pour obtenir l ? algorithme de tri bulle ainsi nommé car les éléments les plus grands du tableau se dirigent vers leur place dé ?nitive à l ? image des bulles d ? air qui remontent à la surface d ? un liquide On rédige une fonction de remontée ? des bulles jusqu ? au niveau k def remonte t k for j in range k ?? if t j t j t j t j t j t j puis la fonction de tri proprement dit Jean-Pierre Becirspahic C informatique commune def bubble sort t for k in range len t ?? remonte t k Notons cn le nombre de comparaisons e ?ectuées et pn le nombre de permutations de deux éléments Nous avons cn n ?? cn ?? et pn ?? pn pn ?? n ?? donc cn n n ?? et pn n n ?? Il s ? agit donc d ? un algorithme de coût quadratique le pire des cas ayant lieu lorsque le tableau est trié à l ? envers n n ?? car alors cn pn Remarque Il est possible d ? améliorer légèrement cet algorithme en observant que si lors d ? une étape de