[PDF] [PDF] TD 4 - Quelques algorithmes de tri - LaBRI

[PDF] Corrigé de la séance Python 2 (algorithmes de tri) 1 Tri bulle

"""trie la liste l par l'algorithme du tri bulle 3 La fonction modifie la liste l et ne renvoie rien""" 4

[PDF] Algorithmes de tris

Dans la pratique, ces algorithmes seront illustrés en Python par le tri d'une liste à valeurs étudier deux algorithmes de tri élémentaires : le tri par sélection et le tri par insertion, bulle, bubble sort en anglais), que vous rédigerez en Python

[PDF] 2 Quelques algorithmes de tri

2 Quelques algorithmes de tri Page 3 trier de grands tableaux, même avec Python La fusion se prête très bien également à une programmation récursive,  

[PDF] TD 4 - Quelques algorithmes de tri - LaBRI

et par la pratique les temps d'exécution de vos différents algorithmes de tris Exercice 1: Le Le tri à bulles est un algorithme de tri qui consiste à faire remonter progressivement les reconvertir t en une liste d'entiers Python Tester cet 

[PDF] Algorithmes de tri - CNRS

Ecrire en Python la procédure de tri par insertion, par ordre croissant, d'un tableau de Le tri à bulles est un algorithme de tri qui s'appuie sur des permutations 

[PDF] TP 1 : Algorithmes de tri - ENS Rennes

Python est un langage de programmation très populaire, notamment grâce à sa syntaxe épurée et la richesse de ses librairies (calcul scientifique, développement 

[PDF] Tri fusion

Pour fusionner les deux paquets en un seul paquet trié : on prend la Fusion de deux listes – Programme Python Tri fusion d'une liste – Programme Python

[PDF] 1 Algorithmes de tri

Celà ne pose pas de problème en Python car les paramètres sont passés par L'algorithme du tri à bulles consiste à trier un tableau en ne s'autorisant qu'à 

[PDF] Informatique en CPGE (2018-2019) Algorithmes de tri 1 Introduction

nécessaire d'étudier la complexité temporelle des différents algorithmes de tri Le tri par insertion d'un tableau à n éléments [t0, ,tn-1] se fait comme suit : à utilisant des listes supplémentaires et les possibilités de Python sans utiliser

[PDF] 1 Introduction au tri à bulles

teur, il devra contenir les fichiers modules Python que vous écrirez Parmi les algorithmes de tri existe celui appelé « tri à bulles » (ou bubble-sort), 

[PDF] algorithme tri par selection python

[PDF] algorithmic bias in recruitment

[PDF] algorithmique et programmation c

[PDF] algorithmique et programmation en java cours et exercices corrigés pdf

[PDF] algorithmique et programmation en pascal

[PDF] algorithmique et programmation en pascal (résumé)

[PDF] algorithmique et programmation en pascal exercices corriges

[PDF] algorithmique et programmation python

[PDF] algorithmique programmation et complexité lyon 1

[PDF] algorithms with c o'reilly pdf

[PDF] alibaba business model pdf

[PDF] alibaba competitive advantage

[PDF] alibaba presentation

[PDF] alienware aw3418dw displayport not working

[PDF] aliera healthcare payer id

TD 4 - Quelques algorithmes de tri

Dans ce TP, les listes d"éléments à trier sont des listes d"entiers. Vous devez implémenter et tester tout les programmes de ce TP en utilisant Python. Vous

devez évaluer la complexité de chacun de vos algorithmes. Vous devez comparer par la théorie

et par la pratique les temps d"exécution de vos différents algorithmes de tris.

Exercice 1: Le tableau est-il trié?

Écrire une fonctionest_trie(t), qui prend en paramètre un tableautet qui renvoietrue si le tableau est trié etfalsesinon.

Exercice 2: Recherche dichotomique

Implémenter une fonction, de complexité optimale, qui prend en paramètre un tableau trié

t et un élément e et qui renvoie -1 si l"élément e n"existe pas dans le tableau ou qui renvoie la

position de sa première occurrence si il existe. Tester l"algorithme avec le tableaut=[1,3,3,5,6,7,7]et la valeur3.

Exercice 3: Tri par sélection.

Sur un tableau de n éléments (numérotés de 0 à n-1), le principe du tri par sélection est

le suivant :

rec hercherle p lusp etitélémen tdu tableau, et l"éc hangera vecl"é lémentd"indice 0 ;

rec hercherle plus p etitélémen tde la p ortiondu tabl eaucomprise en treles indices 1 et n-1, et l"échanger avec l"élément d"indice 1; rec hercherle plus p etitélémen tde la p ortiondu tabl eaucomprise en treles indices 2 et n-1, et l"échanger avec l"élément d"indice 2; con tinuerde ce ttefaçon jusqu"à ce que l etableau soit en tièrementtrié. Écrire une procéduretri_selection(t)qui tri le tableauten utilisant le tri par sélection. Tester votre procédure sur plusieurs exemples. Combien d"échanges fait-il au maximum? Ce résultat vous semble-t-il optimal? Exercice 4: Tri par insertion (ou tri du joueur de cartes)

Le tri par insertion permet de trier une liste L d"éléments. Il consiste à ajouter un à un les

éléments de L dans une liste R initialement vide, de sorte que la liste R soit toujours triée.

Implémenter la fonctiontri_insertion(t)qui prend en paramètre un tableautet qui renvoie un nouveau tableau trié contenant les éléments det.

Tester l"algorithme sur la liste[2,7,1,2,8,7,5].

Implémenter une procéduretri_insertion_en_continu()qui demande à l"utilisateur des

entiers, qui affiche au fur et à mesure la liste triée des entiers tapés par l"utilisateur et qui

s"arrête quand l"utilisateur tape -1.

Exercice 5: Tri à bulles

1 Le tri à bulles est un algorithme de tri qui consiste à faire remonter progressivement les plus grands éléments d"un tableau (comme des bulles d"air remontent à la surface d"un verre de champagne).

Le tri à bulles est une succession d"étapes. Une étape du tri à bulles consiste à parcourir

tous les éléments du tableau et à échanger dans le tableau l"élément courant avec l"élément

suivant si l"élément courant est strictement plus petit que l"élément suivant. Par un exemple,

voici ce que donne le tri à bulles sur la liste[5,1,3,7,2]:

Première étape :

Deuxième étape :

Troisième étape :

[1;3;2;5;7]![1;3;2;5;7]![1;2;3;5;7]

Quatrième étape :

[1;2;3;5;7]![1;2;3;5;7] Écrire une procéduretri_a_bulles(t)qui implémente le tri à bulles. Tester votre tableau sur plusieurs exemples. Modifier votre procédure en une procéduretrace_bulles(t)qui affiche avec la commande printles différentes étapes du tri à bulles, comme effectué sur l"exemple ci-dessus.

Exercice 6: Tri rapide.

Le principe du tri rapide consiste à choisir un élémentpdu tableau, appelé pivot, puis à

trier le tableau en mettant les éléments plus petits quepà gauche depet les éléments plus

grands quepà droites dep. Ensuite, on recommence le processus sur le tableau de gauche

d"une part (c"est à dire les éléments situés à gauche du pivot) et sur le tableau de droite d"autre

part. L"algorithme s"arête quand le tableau est complètement trié. Écrire une procéduretri_rapide(t)qui implémente le tri à rapide. Tester votre tableau sur plusieurs exemples.

Exercice 7: Tri fusion.

Le tri fusion consiste à couper le tableau en 2 de tailles identiques (à un élément près), à

trier le tableau de gauche en utilisant l"algorithme de tri fusion, à trier le tableau de droite avec le même algorithme, puis à fusionner les deux tableaux. Écrire une procéduretri_fusion(t)qui implémente le tri fusion. Tester votre tableau sur plusieurs exemples.

Exercice 8: Tri par dénombrement

Ici, on suppose que tous les nombres sont compris entre 0 et M, où M est fixé. Cette contrainte supplémentaire va nous permettre d"optimiser cet algorithme de tri, pour peu que

M soit assez petit.

Afin de trier un tableau t, le principe est le suivant : 2 -on cr éeun tableau tiroirsconstitué de M+1 zéros; on mo difiele tableau tiroirsde manière à ce quetiroirs[k]soit égal au nombre d"éléments de valeur k dans le tableau t (le faire en une seule lecture du tableau t). à l"aide du tableau tiroirs, on trie le tableau t en renvoyant un tableau contenant dans l"ordre :tiroirs[0]0,tiroirs[1]1,tiroirs[2]2, etc ... Écrire une fonctiontri_par_denombrement(t,N)qui implémente le tri par dénombrement.

Exercice 9: Tri radix

Ici, on suppose que tous les nombres du tableau sont compris entre 0 et10m1. Écrire une fonctionconvertir_liste(n,m)qui transforme un entier n en un tableau à m

éléments listant son écriture en base 10 (renvoyer une erreur si ce n"est pas possible). Exemple :

convertir_liste(823,4)doit renvoyer[0,8,3,2]. Écrire une fonctionconvertir_entier(l)qui transforme une liste l de chiffres compris

entre 0 et 9 en un entier dont l"écriture en base 10 est donnée par l. Exemple :convertir_entier([0,8,3,2])

doit renvoyer832. Le principe du tri radix sur un tableau t est le suivant :

remplacer les en tiersdu tableau t par leur écriture en base 10 donnée par convertir_liste(n,m);

trier, en utilisan tun tri stable, les nom brespar rapp ortaux c hiffresdes unités ; trier, en utilisan tun tri stable, les nom brespar rapp ortaux c hiffresdes dizaines ; con tinuerà tri er,toujours en utili santdes tris stables, décimale par décimale ; recon vertirt e nune liste d"en tiersPython. Tester cet algorithme sur la papier avec la liste[764,199,20,438,199](m=3). Expliquer pourquoi cet algorithme de tri marche. Écrire une fonctiontri_radix(t,m)qui implémente le tri radix.

Exercice 10: Tri du singe

Un singe trie les cartes de la façon suivante : il prend les cartes, les jette en l"air, les ramasse

puis regarde si elles sont triées. Si oui, il s"arrête, sinon il relance les cartes. Implémenter et tester ce tri sur le tableaut=[3,1,9,4,4]. 3quotesdbs_dbs21.pdfusesText_27