Scribd
Importer
120 vues1 page

Série 4 Algorithmes de Tris Classiques en Python

Le document présente trois algorithmes de tri classiques en Python : le tri par sélection, le tri par insertion et le tri à bulle. Chaque algorithme est expliqué avec son principe de fonctionnement et des instructions pour écrire une fonction correspondante en Python. Les exercices demandent de créer des fonctions qui prennent une liste de nombres en entrée et retournent la liste triée selon l'algorithme respectif.

Transféré par

boumalekzineb35
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
120 vues1 page

Série 4 Algorithmes de Tris Classiques en Python

Le document présente trois algorithmes de tri classiques en Python : le tri par sélection, le tri par insertion et le tri à bulle. Chaque algorithme est expliqué avec son principe de fonctionnement et des instructions pour écrire une fonction correspondante en Python. Les exercices demandent de créer des fonctions qui prennent une liste de nombres en entrée et retournent la liste triée selon l'algorithme respectif.

Transféré par

boumalekzineb35
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Prof.

: My Hafid Aabidi
Série_4_Algorithmes_De_Tris_Classiques_en_Python

Exercice 1. Le Tri par sélection.


Sur un tableau de n éléments (numérotés de 1 à n), le principe du tri par sélection est le suivant :
• rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ;
• rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 2 ;
• continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.
Une autre variante de ce tri consiste à procéder de façon symétrique, en plaçant d'abord le plus
grand élément à la fin, puis le second plus grand élément en avant-dernière position, etc.
Ecrire une fonction TriSelection() en python qui prend en paramètre une liste de nombres et
retourne la liste triée par l’algorithme de tri par sélection.

Exercice 2. Le Tri par insertion.


Le tri par insertion est un algorithme de tri classique, que la plupart des personnes utilisent
naturellement pour trier des cartes à jouer : prendre les cartes mélangées une à une sur la table, et
former une main en insérant chaque carte à sa place.
Dans l'algorithme, on parcourt le tableau à trier du début à la fin. Au moment où on considère le i-
ème élément, les éléments qui le précèdent sont déjà triés. Pour faire l'analogie avec l'exemple
du jeu de cartes, lorsqu'on est à la i-ème étape du parcours, le i-ème élément est la carte saisie,
les éléments précédents sont la main triée et les éléments suivants correspondent aux cartes
encore mélangées sur la table.
L'objectif d'une étape est d'insérer le i-ème élément à sa place parmi ceux qui précèdent. Il faut
pour cela trouver où l'élément doit être inséré en le comparant aux autres, puis décaler les
éléments afin de pouvoir effectuer l'insertion. En pratique, ces deux actions sont fréquemment
effectuées en une passe, qui consiste à faire « remonter » l'élément au fur et à mesure jusqu'à
rencontrer un élément plus petit.

Ecrire une fonction TriInsertion() en python qui prend en paramètre une liste de nombres et
retourne la liste triée par l’algorithme de tri par insertion.

Exercice 3. Le Tri à bulle.


Le tri à bulle est un algorithme de tri qui prend en paramètre une liste de nombres et l’ordonne
dans le sens croissant. Il s’opère de la façon suivante :
– Parcourir les éléments du tableau de gauche à droite.
– Dès que l’on rencontre deux éléments consécutifs qui ne sont pas dans le bon ordre, on échange
leur position. C’est à dire : SI tableau[i] > tableau[i+1] ALORS : échanger tableau[i] et tableau[i+1]
– Recommencer tant que l’on a changé quelque chose.

Ecrire une fonction TriBulle() en python qui prend en paramètre une liste de nombres et
retourne la liste triée par l’algorithme de tri à bulle.

Vous aimerez peut-être aussi