Classes Préparatoires d’entrée dans

les Grandes Ecoles (CPGE)

Algorithmique et Programmation en
Python

Dr Sibiri TIEMOUNOU

Année académique 2020-2021

1
Plan du cours

1. Généralités sur l’algorithmique et la programmation

2. Rappel sur les notions de bases

3. Structures de données

4. Procédures et fonctions

5. Algorithme de tri et de recherche

2
05/03/2021
Sommaire

 Objectifs de ce cours

 Comprendre les notions de bases en algorithmique et programmation

 Savoir écrire et écrire un algorithme et le traduire en langage Python

 Maîtriser l’utilisation du langage Python pour réaliser la mise en œuvre d’algorithmes et le

développement d’applications de petite taille.

 Evaluation
 Rapport de TP
 Mini projet (en Python)

3
0. Généralités sur l’Algorithmique et la programmation

4
05/03/2021
0.1 Algorithmique

 Définition
 L’algorithmique est un terme d’origine arabe, comme algèbre, amiral ou zénith.

 C’est un mot dérivé du nom du mathématicien « al Khwarizmi » qui a vécu au 9ème

siècle, était membre d’un académie des sciences à Bagdad

 Un algorithme est une suite d’actions à effectuer pour:

 Réaliser un traitement donné

 Résoudre un problème donné

 Un programme est une série d’instructions pouvant s’exécuter en séquence, ou en

parallèle (parallélisme matériels) qui réalise (implémente) un algorithme

5
0.1 Algorithmique

 Exemples d’algorithmes
 Recettes de cuisine

 Résoudre un système d’équations à plusieurs inconnues

6
0.1 Algorithmique

 Formalisation d’un algorithme

Informations
en entrée

Algorithme informatique
=
procédure de calcul

Rigueur scientifique IMPORTANT !

Sinon, information de sortie erronée
Informations
en sortie

7
0.1 Algorithmique

 Les problèmes fondamentaux en algorithmique

 Complexité
 En combien de temps un algorithme va -t-il atteindre le résultat escompté?

 De quel espace a-t-il besoin?

 Calculabilité
 Existe-t-il des tâches pour lesquelles il n'existe aucun algorithme ?

 Etant donnée une tâche, peut-on dire s'il existe un algorithme qui la résolve ?

 Correction
 Peut-on être sûr qu'un algorithme réponde au problème pour lequel il a été conçu ?

8
0.2 Langage de programmation

 Qu’est-ce qu’un langage de programmation?

 Pour communiquer avec quelqu’un, vous devez parler le même langage
 Avec un ordinateur, difficile de communiquer car ne comprenant que des 0 et 1

 Pour communiquer avec un ordinateur, il faut un interpréteur (ou logiciel)

 Charger de transformer un message en 0 et 1

9
05/03/2021
0.2 Langage de programmation

 Qu’est-ce qu’un langage de programmation?

 Un ordinateur obéit aux ordres que nous lui donnons

 Ces ordres s’appellent des instructions

 Un langage est donc une suite d’instructions

 Exemple :
 Affiche « A » à l’écran
 Affiche une zone où l’utilisateur pourra saisir son nom
 Si l’utilisateur clique sur le bouton « fermer », alors le programme se ferme

 Un langage de programmation permet d’écrire toutes ces instructions (aussi appelé

code source) dans un langage de comprise par le traducteur
 Charger de transformer un message en 0 et 1

10
0.3 Type de langages de programmation

 Quels sont les types de langage ?

 Il existe 2 types de langages

 Langages compilés
 Le code écrit par le développeur est d’abord compilé (conversion du code source
en langage machine) avant d’être exécuter

11
0.3 Type de langages de programmation

 Quels sont les types de langage ?

 Il existe 2 types de langages

 Langages interprétés
 Ces langages n’ont pas besoin de compilation. Le code source est lu et traduite
pour être exécuté

12
0.3 Type de langages de programmation

 Liste de quelques langages couramment utilisés

Langages Type
Python Interprété
C++ Compilé
C Compilé
Java Compilé
HTML/CSS Interprété
PHP Interprété
Javascript Interprété
SQL Interprété

13
0.4 Algorithmie et programmation

 Quel lien entre Algorithmique et langage de programmation ?

 L’algorithmique sert à résoudre les problèmes de monde des vivants grâçe à la logique et surtout de mettre en place
un système d’automisation

 L’algorithme est universel pour quasiment tous les langages de programmation

 Un algorithme peut être codé en C, C++, qu’en Python et d’autres langage

 Le langage de programmation sert entre autre à traduire l’algorithme dans le strict respect dudit langage
14
0.5 Présentation du langage Python

 C’est quoi le langage Python ?

 C’est un langage de programmation inventé par Guido Van Rossum
 La 1ère version est apparu en 1991

 C’est un langage de programmation interprété

 Pas nécessaire de compiler avant de l’exécuter

15
0.5 Présentation du langage Python

 C’est quoi le langage Python ?

 Un des langages les plus utilisés au monde

 Elu Meilleur langage en 2020 (source : IEEE : top 10 des meilleurs langages de
programmation de l’année 2020)

16
0.5 Présentation du langage Python

 Quelles sont les caractéristiques du langage Python?

 Langage facile à apprendre, à comprendre et à écrire
 Il n’ y a pas de pointeurs explicites en Python (contrairement aux langages C/C++)

 Langage Orienté Objet

 Supporte l’héritage multiple et la surcharge des opérateurs

 Langage portable
 fonctionne sous de nombreux systèmes d'exploitation
 Linux, MacOS, Windows

 Doté d’une communauté active

 Utile pour résoudre des problèmes de bugs

17
0.5 Présentation du langage Python

 Qui utilise Python ?

18
0.5 Présentation du langage Python

 Que peut-on faire avec Python?

 Programmation des progiciels (ensemble de plusieurs logiciels pouvant fonctionner
ensemble)

 Très utilisé en robotique (technologie Raspbberry)

 Internet des objets (IoT) et Intelligence artificielle (IA)

19
0.5 Présentation du langage Python

 Distribution de Python et bibliographie

 Site officiel : http://www.python.org
 Manuel de références
 Documentation des bibliothèques de fonctions
 Version actuelle : 3.8.2

 Editeurs IDE Python

 PyCharm
 L’un des meilleurs IDE (très complet et gratuit)

 Sublime Text (ou notepad++)

 Editeurs (très complet et gratuit)
 Spyder
 Véritable environnement développement et très intuitif
 Intégré dans le framework « Anaconda »
 Jupyter notebook
 Environnement dédié à la science des données 20
0.5 Présentation du langage Python

 Comment installer Python?

 En téléchargeant la dernière version sur le site officielle « https://www.python.org/downloads/ »

 Avec cette version, on a principalement accès à l’invite de commande « Python’

 Pour télécharger l’IDE « Spyder », il faudra télécharger le framework « Anaconda » en

utilisant le lien suivant : « https://www.anaconda.com/distribution/#download-section »
en veillant à bien sélectionner la version correspondante à votre système d’exploitation

21
0.5 Présentation du langage Python

 Exemple de code Python

 Commentaires multi lignes

""" commentaire
…
"""

 Commentaires sur une ligne

# commentaire

22
0.5 Présentation du langage Python

 Exemple de code Python

 Appel à des libraires prédéfinies

(bibliothèque standard) ou celles
implémentées par l’utilisateur

 Mot clé : import

 from A import B
 A partir de la librairie A
importer la sous libraire (ou
fonctions) B

23
0.5 Présentation du langage Python

 Exemple de code Python

 Utilisation de variable
 Pas besoin de spécifier son type

 Déclaration et initialisation de
tableau

 Appel de fonctions
24
0.5 Présentation du langage Python

 Distribution de Python et bibliographie

 Bibliographies
 Programmation Python, par Tarek Ziadé, Editions Eyrolles, Paris, 2006, 538 p.,
ISBN 978-2-212-11677-9

 Au coeur de Python, volumes 1 et 2, par Wesley J. Chun, traduction de Python core

programming, 2d edition (Prentice Hall) par Marie-Cécile Baland, Anne Bohy et Luc
Carité, Editions CampusPress, Paris, 2007, respectivement 645 et 385 p., ISBN 978-2-
7440-2148-0 et 978-2-7440-2195-4.

 Python : How to program, par Deitel, Liperi & Wiedermann, Prentice Hall, Upper
Saddle River – NJ 07458, 2002, 1300 p., ISBN 0-13-092361-3,

25
0.6 A propos de la programmation

 Programmer, c’est dur ?

Il faut que je sois un

super-méga
matheux
Ouais, ouais,

 Réponses:
 Non, non et non
 un super-niveau en maths n'est pas nécessaire
 La connaissance en maths dépend du type de logiciels (cryptage, jeux 3D, …)

 Tout ce dont vous aurez besoin en Maths

 Savoir effectuer les calculs de base (addition, multiplication, …)
 Notion de logique (Algorithmique)
26
0.6 A propos de la programmation

 Programmer, c’est dur ?

 Les qualités suivantes sont nécessaires pour être un bon programmeur

Patience Sens de la logique Sérénité

• Le programme ne marche • Pas besoin d’être fort en • Non, on ne tape pas son
jamais du premier cours Maths mais besoin de ordinateur avec un marteau
réfléchir

• Il faut savoir persévérer • Ce n’est pas ça qui résoudra

• Trouver l’algorithmie le programme
répondant à un problème
donné • Un peu de sérénité

27
1. Rappel sur les notions de base

28
05/03/2021
1.1 Retour sur l’algorithmique

 Formalisation d’un algorithme

 L’une des représentations la plus utilisée pour formuler un algorithme, le pseudocode ou
pseudo-langage :Langage de Description Algorithmique(LDA)

 Le pseudo-code n’est pas un langage de programmation mais un moyen d’être très proche
de la programmation, sans être noyé sous la syntaxe d’un langage de programmation.

 Etapes de réalisation d’un algorithme

 Préparation du traitement : Données nécessaires à la résolution du problème

 Traitement : Résolution pas à pas et décomposition du problème en sous-problème si

nécessaire

 Editions des résultats : Impression à l’écran, sauvegarde dans un fichier, etc

29
1.1 Retour sur l’algorithmique

 Langage algorithmique

Algorithme NomAlgorithme Algorithme Bonjour

{Ceci est un commentaire} {Il a juste dit bonjour …

Debut mais en anglais}
… Actions Debut
Fin Afficher(« Hello world »)
Fin

 Il faut avoir une écriture rigoureuse

 Il faut avoir une écriture soignée : respecter l’indentation
 Il est nécessaire de commenter les algorithmes
 Il existe plusieurs solutions algorithmiques à un problème posé
 Il faut rechercher l’efficacité de ce que l’on écrit

 L’un des éléments fondamentaux en Algorithmique est la manipulation des des données à l’aide
des variables 30
1.2 Les variables

 Définition
 Lors de l’exécution d’un algorithme, on va avoir besoin de stocker des données, voire des
résultats. Pour cela, on utilise des variables. On attribue un nom à chaque variable.

 Une variable est donc une zone mémoire qui associe un nom à une valeur qui peut
éventuellement varier au cours du temps

 Il peut s’agir de nombres entiers, de chaine de caractères, …

31
1.2 Les variables

 Déclaration
 Dans le format LDA, Il faut faire précéder la description de l'algorithme par une partie dite
déclarative où l'on regroupe les caractéristiques des variables manipulées

 La partie déclarative est placée (généralement) en tête de l'algorithme et regroupe une ou

plusieurs indications de la forme:

 type variables.

 Instruction d’affectation

 Une fois nommée, il est souvent nécessaire de modifier la valeur de la donnée

référencée par une variable. C’est le rôle de l’instruction d’affectation.

 L’affectation est l’opération qui consiste à attribuer une valeur à une variable.

 La syntaxe est la suivante :

Variable ← expression
32
1.2 Les variables

 Type de variable
 Lorsqu’on déclare une variable, il faut préciser ce que l’on voudra mettre dedans c’est le
type

 Types numériques : entier, réel

 Type alphanumérique : caractère, chaine de caractères

 Type booléen (valeurs logiques VRAI, FAUX)

33
1.2. Les variables

 Instruction de saisie et d’affichage

 Au format LDA, l’instruction de lecture (ou d’affichage) du contenu d’une variable s’écrit:

Lire variable

 Concernant l’instruction d’écriture

affiche variable

 Exemple
 Exprimer un nombre de secondes sous forme d'heures, minutes, secondes. La seule
donnée est le nombre total de secondes que nous appellerons nsec ; les résultats
consistent en 3 nombres : h, m, s

34
1.2. Les variables

 Exemple

35
1.2. Les variables

 Les variables en Langage Python

 La déclaration d’une variable en Python ne requiert pas de type. Ainsi toute variable déclarer doit être
initialisée
nombreVariable = valeur

 Remarques
 Contrairement au langage C, une instruction, en Python, ne se termine pas par un point virgule « ; »

 Même si la déclaration d’une variable ne requiert pas son type, une variable est en réalité typée en
Python :
type Type en Python Exemple
Les entiers int x=2
Les réels float, double a = 5.0
Les chaines de caractères string (str) my flowers are beautiful
Les booléens bool (True, False) is_rich = True
 Pour connaitre le type d’une variable :
type (ma_variable) 36
1.2 Les variables

 Les variables en Langage Python

 Les noms des variables doivent respecter quelques règles:
 Ils ne commenceront pas par un chiffre.

 Le langage C est sensible à la casse (majuscule/minuscule)

Exemple : somme # Somme

 Ils peuvent avoir des lettres, en minuscule ou majuscule et des chiffres

 les caractères spéciaux tels que $, #, @, etc. sont interdits, à l’exception du caractère
« _ » (souligné).

 Ils ne doivent pas être un mot-clé réservé par Python

37
1.2 Les variables

 Les variables en Langage Python

 Pour afficher le contenu d’une variable, on utilise la fonction « print(…) » et une
commande spécifique

 Exemple :
print("my flowers are beautiful ")
nbEtudiant = 15
print("le nombre d’étudiant dans la classe est: ", nbEtudiant)

 Pour récupérer les informations saisies par l’utilisateur sur le clavier, on utilise la fonction
« input(…) ». Pour ce faire, une fois l’information saisie, on va le récupérer et le stocker
dans une variable
# Programme testant si une année, saisie par l'utilisateur, est bissextile ou non
annee = input("Saisissez une année : ") # On attend que l'utilisateur saisisse l'année qu'il désire tester
annee = int(annee) # Risque d'erreur si l'utilisateur n'a pas saisi un nombre

if annee % 400 == 0 or (annee % 4 == 0 and annee % 100 != 0):

print("L'année saisie est bissextile.")
else:
print("L'année saisie n'est pas bissextile.") 38
1.3 Les opérations de bases

 Les opérateurs mathématiques

 Il s’agit des opérations usuelles

 L’addition : +

 La soustraction : -

 La multiplication : *

 La division : /

 Le modulo : mod ( « % » en Python)

 Les opérateurs relationnels (ou booléens)

 < (inférieur) , > (supérieur) , <= (inférieur ou égal) , >= (supérieur ou égal) , =(égal, ==
en Python) , <>(différent de, != en Python)

39
1.3 Les opérations de bases

 Les opérateurs logiques

Types LDA En Python

Négation Non Not
Et logique et and
Ou logique ou or

 Affectation avec opérations

 Addition: +=, ex : a += b  a = a + b
 Soustraction: -=, ex : a -= b  a = a – b
 Multiplication: *=, ex : a *= b  a = a * b
 Division: /=, ex : a /= b  a = a / b
 Modulo: %=, ex : a %= b  a =a % b

40
1.3 Les opérations de bases

 Exemple
 Traduction en Python de l’algorithme convertissant un nombre de secondes sous forme
d’heure, minutes et seconde

41
1.4 Structures de contrôle et boucles
 Structure de contrôles
 Les structures conditionnelles ou alternatives permettent d'écrire dans le programme des
règles comme « Si ceci arrive, alors fais cela » ;

 Elles désignent toute situation n’offrant que deux (ou plusieurs) issues possibles s’excluant
mutuellement

 Syntaxe

Si condition logique alors

# bloc d’instruction 1
sinon
# Blocs d’instruction 2
FinSi

Où « condition logique » peut être soit « VRAI » soit « FAUX ». Il s’agit généralement d’une
comparaison d’une variable à une valeur ou une autre variable

« Finsi » indique la fin de la condition 42

1.4 Structures de contrôle et boucles
 Structure de contrôles
 Le résultat de l’exécution dépendra de la condition logique :

 Si la condition est VRAI alors la première séquence d'instruction sera exécutée et la

seconde sera ignorée;

 Si la condition es FAUX, seule la seconde séquence d'instructions sera effectuée.

 Exemple :

 On considère un jeu dans lequel 2 joueurs A et B doivent présenter un certain

nombre de doigts (0 à 5). Si la somme des nombres de doigts montrés est paire, le
joueur A a gagné sinon c'est le joueur B qui a gagné.

 Le problème est de faire prendre la décision par l'ordinateur.

43
1.4 Structures de contrôle et boucles
 Structure de contrôles
 Exemple : En LDA, on obtient

44
1.4 Structures de contrôle et boucles
 Structure de contrôles
 Remarques :
 Le bloc « sinon » est facultatif dans certains cas

 Une instruction « si … finsi » peut contenir plusieurs autres conditions. On parle

d’imbrication

45
1.4 Structures de contrôle et boucles
 Structure de contrôles en Python
 Syntaxe

Si condition logique alors

if condition :
# bloc d’instruction 1
# bloc d’instruction 1
sinon
else :
# Blocs d’instruction 2
#bloc d’instruction 2
FinSi

 Remarques :

 En python, Il y a « : » à la fin de la condition

 Il n’ y a d’accolades (à la différence du C)

 Veuillez à bien aligner les instructions sous les conditions

 Source du problème d’indentation
 Le bloc « sinon » (ou « else » en Python) est facultatif

46
1.4 Structures de contrôle et boucles
 Structure de contrôles en Python
 Remarques :
 Il est également possible d’avoir des conditions imbriquées. En Python, on peut
utiliser le « elif » pour signifier le « sinon si »
if condition :
# bloc d’instruction 1
elif condition :

#bloc d’instruction 2
else :
#bloc d’instruction 3

 Exemple : Traduction de l’exemple précédent en Python

47
1.4 Structures de contrôle et boucles

 Les boucles
 Exemple introductif :

 Problème: On souhaiterait remplir un fossé. Pour cela on dispose d’un tas de sable et
d’une pelle. Le volume du tas de sable est supposé supérieur au volume du trou à
combler.

 Analyse: Jeter une pelletée de sable dans le fossé tant que le fosse n’est pas plein.

 Cette analyse met en évidence deux éléments :

 1.une action à exécuter (jeter une pelletée de sable),

 2.une condition d’exécution (le fossé n’est pas plein).

 Une boucle est une exécution répétée d’une ou plusieurs des actions et ayant un
mécanisme pour l’arrêter.
48
1.4 Structures de contrôle et boucles

 Les boucles
 On distingue types de boucles :

 La boucle « pour »

 La boucle « tant que »

 La boucle « Faire … tant que »

 Nous verrons uniquement les 2 premières car la dernière n’existe pas en Python

49
1.4 Structures de contrôle et boucles

 Les boucles « pour »

 Cette boucle est utilisée lorsqu'on connait à l’avance le nombre d’itération (nombre de fois
qu’une action sera répétée)

 Syntaxe : (LDA)

 « iterateur » : est une variable de contrôle, initialisée à debut et s’incrémentant à chaque

itération

 L’itération s’arrête lorsque : « Iterateur > fin »

50
1.4 Structures de contrôle et boucles

 Les boucles « pour »

 Exemple :

 Écrire l’algorithme qui affiche la table de multiplication de n.

51
1.4 Structures de contrôle et boucles

 Les boucles « tant que »

 On utilise cette boucle quand on ne connait pas à l’avance le nombre d’itération

 Syntaxe :

 Au moment du premier passage dans la boucle la condition est évaluée; si elle est vérifiée,
la séquence d’instructions est exécutée

 A la fin de l’exécution de cette séquence d’instructions, la condition est de nouveau évaluée

et on répète l’exécution de la séquence d’instructions tant que la condition est vérifiée.

 Dès que la condition devient fausse, l’exécution du programme se poursuit à partir de la

1ère instruction qui suit immédiatement le mot-clé « fintantque »
52
1.4 Structures de contrôle et boucles

 Les boucles « tant que »

 Exemple :

 Écrire l’algorithme qui affiche la table de multiplication de 6.

53
1.4 Structures de contrôle et boucles

 Les boucles « Pour » en Python

 Syntaxe :

for iterateur in sequence:

# Instructions 1
# instruction 2 Attention à l’indentation !!!!
# ….
# instruction N

 La variable « iterateur » n’a pas besoin d’être initialiser. Elle prendra successivement chacune
des valeurs figurant la « séquence » parcourue

 La variable « sequence » est un tableau (ou liste de valeur)

 Pour créer une séquence d’entier entre deux valeurs a et b, on utilise la fonction « range »

 range (a, b, pas) : pas correspond à l’incrémention. Si non spécifier alors « pas = 1 »
54
1.4 Structures de contrôle et boucles

 Les boucles « Pour » en Python

 Exemple : Traduction de l’exemple précedent

55
1.4 Structures de contrôle et boucles

 Les boucles « tant que » en Python

 Syntaxe :

while condition :
# Instructions 1
# instruction 2
# ….
# instruction N

 Exemple :

56
2. Structure de données

05/03/2021
57
2.1 Introduction

 Jusqu’ici, nous avons travaillé les variables

 Rappel : une variable ne permet de stocker qu’une seule et unique valeur

 Que se passe t-il si on devait stocker plusieurs valeurs du même type? Et de types différents ?

 Dans ce chapitre, nous verrons particulièrement deux types de variables permettant de stocker
plusieurs valeurs :

 Les listes (ou tableaux)

 Les chaines de caractères

 Les dictionnaires

 Notion d’objet
 Un objet est une variable, pouvant elle-même contenir d’autres variables et fonctions
 C’est une notion fondamentale en Python
 En réalité, toutes les variables utilisées jusqu’ici sont des objets (idem pour les fonctions)
 Garder à l’esprit qu’en python, tout est objet
58
2.2 Tableaux

 Définition
 Un tableau (encore appelé table ou variable indicée) est un ensemble de données, qui sont
toutes de même type, désigné par un identificateur unique (le nom du tableau), et qui se
distinguent les une des autres par leur numéro d’indice

 L’accès à un élément du tableau se fait grâce son indice

 Attention : l’écriture de Température[-2] ou Température[12] n’ont pas de sens car elles

59
font référence à des éléments inexistants
2.2 Tableaux

 Déclaration de tableau
 Trois éléments définissent un tableau:

 Son nom : identificateur respectant les règles classiques des identificateurs d’un
programme

 Le nombre de ses éléments

 Le type de données qu’il contient

 Notation LDA

 Un tableau à plusieurs dimensions est un tableau pour lequel l’accès à un élément se fait en
utilisant plusieurs indices 60
2.2 Tableaux

 Exemple
 On souhaiterait calculer la température moyenne de la semaine, les températures étant
stockés dans un tableau « temperature »

 L’accès à un élément du tableau se fait grâce son indice

61
2.2 Tableaux

 Tableaux à plusieurs dimensions

 Les tableaux qu’on a étudiés jusqu’à présent sont dits unidimensionnels (car on utilise un
seul indice de parcours)

 Proche des vecteurs utilisés en mathématiques.

 Mais on peut aussi avoir besoin de manipuler des matrices, i.e. des structures possédant
plus de deux dimensions.

62
2.3 Tableaux en Python

 Création d’un tableau (liste)

 Liste vide
>>> nom_liste = [ ]
>>> nom_liste = list()

 Tableau initialisé
>>> nom_liste = [1, 5, 10, 15, 20, 25]

 Insertion d’éléments dans la liste

 Méthode « append » : ajout en fin de liste

>>> ma_liste = [1, 2, 3]

>>> ma_liste.append(56) # On ajoute 56 à la fin de la liste

 Méthode « Insert » : Insertion d’un élément à une position donnée

>>> ma_liste = ['a', 'b', 'd', 'e']
>>> ma_liste.insert(2, 'c') # On insère 'c' à l'indice 2
>>> print(ma_liste)
['a', 'b', 'c', 'd', 'e'] 63
2.3 Tableaux en Python

 Parcours d’un tableau

 Utilisation des boucles
>>> ma_liste = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
>>> i = 0 # Notre indice pour la boucle while
>>> while i < len(ma_liste):
... print(ma_liste[i])
... i += 1 # On incrémente i, ne pas oublier !
...
>>> # Cette méthode est cependant préférable
... for elt in ma_liste: # elt va prendre les valeurs successives des éléments de ma_liste
... print(elt)
...

 Méthode « enumerate »

 Elle prend en paramètre une liste et renvoie une liste d’objets contenant deux valeurs
par élément : l'indice et l'élément de la liste parcouru

 Exemple :

>>> ma_liste = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
>>> for elt in enumerate(ma_liste):
... print(elt)
64
2.3 Tableaux en Python

 Suppression d’éléments
 Méthode « del » : Permet de supprimer définitivement une variable donnée
>>> ma_liste = [-5, -2, 1, 4, 7, 10]
>>> del ma_liste[0] # On supprime le premier élément de la liste
>>> ma_liste
[-2, 1, 4, 7, 10]
>>> del ma_liste[2] # On supprime le troisième élément de la liste
>>> ma_liste
[-2, 1, 7, 10]
>>>

 Remarque : la méthode « del » n’est une méthode de l’objet « Liste » mais une
fonctionnalité de python

 Méthode « remove() »

 Méthode appartenant à l’objet « Liste » : elle prend en paramètre non pas l’indice de
l’élément à supprimer mais plutôt l’élément lui-même
>>> ma_liste = [31, 32, 33, 34, 35]
>>> ma_liste.remove(32)

 Attention : La méthode « remove » ne retire que la première occurrence de la valeur trouvée

65
dans la liste !
2.3 Tableaux en Python

 Tableaux à plusieurs dimensions

 En python, un tableau à plusieurs dimensions une liste contenant des listes

 Exemple : On souhaiterait créer une matrice (3*3) dimension

>>> t = [ [4,2,5], [7,7,8], [5,6,3]]

66
2.3 Tableaux en Python

 Les tuples
 Ils sont vus comme des liste, sauf qu'on utilise comme délimiteur des parenthèses au lieu
des crochets

 Ce sont des listes immuables, i.e. qu’on ne peut modifier

 Ils sont très utiles lorsqu’une fonction doit renvoyer plusieurs variables

 Certains modules de python contiennent des fonctions renvoyant des tuples

 La méthode « enumerate » renvoie en réalité des tuples

 Exemple

tuple_vide = ()
tuple_non_vide = (1,)
tuple_non_vide = (1, 3, 5)

67
2.4 Les chaines de caractères (Python)

 En python, les chaines de caractères sont gérés par un objet (ou classe) appelé « str »
 Prenons un exemple:
 Ecrire une fonction prenant en paramètre un chaine de caractère et renvoyant cette
chaîne en minuscule
 On s’attendrait à un code de la sorte :

>>> chaine = « N’TOH ! Humm…, J’adore les DONUTS!"

>>> mettre_en_minuscule(chaine)
‘n’toh!, humm …, j’adore les donuts'

 Toutefois jusqu’ici, nous ne savons pas comment gérer ce type de problème

 C’est tout là, l’importance des objets : l’objet « str » contient des méthodes prédéfinies
permettant de manipuler les chaines de caractères.

 Pour notre exercice, l’objet « str » contient la méthode « lower() » permettant de

convertir les chaines de caractères en minuscule
68
2.4 Les chaines de caractères (Python)

 Création d’une chaine de caractères

 2 méthodes possibles :
 Par initialisation directe :

ma_chaine = "N’TOH ! Humm…, J’adore les DONUTS!"

 Appel de la méthode « str() »

ma_chaine = str("N’TOH ! Humm…, J’adore les DONUTS!« )

69
2.4 Les chaines de caractères (Python)

 Mise en forme d’une chaine de caractères

 L’objet « str » dispose des méthodes suivantes:
 lower(): convertit la chaine en minuscule
 upper() : transforme une chaine en majuscule
 capitalize() : convertit le premier caractère de la chaine en majuscule
 strip() : retire des espaces en début et fin de la chaine de caractère
 center() : centre la chaine
 Exemple:

>>> minuscules = "une chaine en minuscules"

>>> minuscules.upper() # Mettre en majuscules
'UNE CHAINE EN MINUSCULES'
>>> minuscule.capitalize() # La première lettre en majuscule
'Une chaine en minuscules'
>>> espaces = " une chaine avec des espaces "
>>> espaces.strip() # On retire les espaces au début et à la fin de
la chaîne
'une chaine avec des espaces'
>>> titre = "introduction"
>>> titre.upper().center(20)
' INT
70
2.4 Les chaines de caractères (Python)

 Formatage et affichage d’une chaine de caractères

 Affichage simple : utilisation de la fonction « print »
chaine = "Bonjour tout le monde !"
print(chaine)

print( "le message à afficher sur l’écran est : ", chaine)

 Méthode « format(…) »
>>> prenom = "Paul"
>>> nom = "Dupont"
>>> age = 21
>>> print( "Je m'appelle {0} {1} et j'ai {2} ans.".format(prenom, nom, age) )
Je m'appelle Paul Dupont et j'ai 21 ans.

 Le message contient des accolades entourant des nombres 0, 1, 2 ;

 La méthode « format » prend en paramètres les variables à afficher, dans un ordre bien précis ;

 quand Python exécute cette méthode, il remplace dans notre chaîne {0} par la première variable
passée à la méthode format (soit le prénom), {1} par la deuxième variable… et ainsi de suite.

71
2.4 Les chaines de caractères (Python)

 Formatage et affichage d’une chaine de caractères

 Concaténation des chaines
 Elle consiste à regrouper les chaines de caractères en une seule une chaine
 On utilise pour cela le caractère « + »

 Exemple

>>> prenom = "Paul"

>>> message = "Bonjour"
>>> chaine_complete = message + prenom # On utilise le symbole '+‘ pour concaténer deux
chaînes

... print(chaine_complete) # Résultat :

BonjourPaul

>>> # Pas encore parfait, il manque un espace

... # Qu'à cela ne tienne !
... chaine_complete = message + " " + prenom
>>> print(chaine_complete) # Résultat :
Bonjour Paul
>>>

72
2.4 Les chaines de caractères (Python)

 Formatage et affichage d’une chaine de caractères

 Concaténation des chaines
 Attention : la concaténation n’accepte que les chaines de caractère

 Exemple
>>> age = 21
>>> message = "J'ai " + age + " ans."

Traceback (most recent call last):

File "<stdin>", line 1, in <module>
TypeError: Can't convert 'int' object to str implicitly
>>>

 On réalise une concaténation de chaine et de nombre

 On constate qu’il ya une erreur de conversion

 Solution : tout convertir en chaine de caractère avec la méthode « str »

>>> age = 21
>>> message = "J'ai " + str(age) + " ans."
>>> print(message)
J'ai 21 ans.
>>> 73
2.4 Les chaines de caractères (Python)

 Parcours et sélection de chaines

 Sélection de chaînes
 En python, il est possible de sélectionner ou d’extraire une partie de la chaine à partir
des indices

ma_chaine[indice_debut : indice_fin]

 Exemple
>>> presentation = "salut"
>>> presentation[0:2] # On sélectionne les deux premières lettres
'sa'
>>> presentation[2:len(presentation)] # On sélectionne la chaîne sauf les deux premières lettres
'lut‘

>>> presentation[:2] # Du début jusqu'à la troisième lettre non comprise

'sa'
>>> presentation[2:] # De la troisième lettre (comprise) à la fin
'lut'
>>>

74
2.4 Les chaines de caractères (Python)

 Parcours et sélection de chaines

 Remarque
 Il est souvent utile de pouvoir désigner l’emplacement d’un caractère par rapport à la
fin de la chaîne. Pour ce faire, il suffit d’utiliser des indices négatifs :
 « -1 » désignera le dernier caractère,
 « -2 » l’avant-dernier, etc.

 L’opérateur * permet de répéter une chaine de caractères

 Exemple

>>> nom = « Cédric"

>>> print(nom[-1], nom[-2], nom[-4], nom[-6])
cidC
>>> m = 'zut ! ' * 4 # répétition
zut ! zut ! zut ! zut !

75
2.5 Les dictionnaires

 Rappel sur les listes

 Une liste est une structure de données pouvant contenir plusieurs type de données
différentes

 Chaque élément d’une liste est rangé dans un ordre bien précis
 Pour accéder à un élément, on passe toujours par son indice (entier naturel)

 Il existe une autre structure de données plus élaborée n’utilisant pas la notion d’indice mais
plutôt de clé

 Il s’agit des dictionnaires

 Les dictionnaires est l’une des structures de données les plus utilisées en Python

76
2.5 Les dictionnaires

 Définition
 Un dictionnaire est un objet pouvant en contenir d'autres, à l'instar des listes

 Chaque élément du dictionnaire est associé à une clé

 Ces clés peuvent être des chaines de caractères (c’est le cas la plupart du temps) ou des objets
 Dans les listes, la clé est l’indice de l’élément

 Les données d’un dictionnaire ne sont pas ordonnées contrairement aux listes

 Par exemple, un dictionnaire peut contenir un carnet d'adresses et on accède à chaque

contact en précisant son nom.

77
2.5 Les dictionnaires

 Création d’un dictionnaire

 2 méthodes de création d’un dictionnaire
 En utilisant la méthode « dict() » ou simplement les accolades « {} »

>>> mon_dictionnaire = dict()

>>> type(mon_dictionnaire)
<class 'dict'>
>>> mon_dictionnaire
{}
>>> # Du coup, vous devriez trouver la deuxième manière de créer un dictionnaire vide
... mon_dictionnaire = {}
>>> mon_dictionnaire
{}
>>>

78
2.5 Les dictionnaires

 Ajout d’un élément dans un dictionnaire

>>> mon_dictionnaire = {}
>>> mon_dictionnaire["pseudo"] = "Prolixe"
>>> mon_dictionnaire["mot de passe"] = "*"
>>> mon_dictionnaire
{'mot de passe': '*', 'pseudo': 'Prolixe'}
>>>

 Procédure
 On spécifie la clé entre crochets

 Si la clé n'existe pas dans le dictionnaire, elle y est ajoutée avec la valeur spécifiée
après le signe =

 Sinon, l'ancienne valeur à l'emplacement indiqué est remplacée par la nouvelle :

79
2.5 Les dictionnaires

 Ajout d’un élément dans un dictionnaire

 Exemple
>>> mon_dictionnaire = {}
>>> mon_dictionnaire[0] = "a"
>>> mon_dictionnaire[1] = "e"
>>> mon_dictionnaire[2] = "i"
>>> mon_dictionnaire[3] = "o"
>>> mon_dictionnaire[4] = "u"
>>> mon_dictionnaire[5] = "y"
>>> mon_dictionnaire
{0: 'a', 1: 'e', 2: 'i', 3: 'o', 4: 'u', 5: 'y'}
>>

 Remarques
 Un dictionnaire ne peut naturellement pas contenir deux clés identiques
 La seconde valeur écrase la première

 Il est possible d'avoir deux valeurs identiques dans le dictionnaire

 Les clés peuvent être de tout type (cependant le type doit être unique)

80
2.5 Les dictionnaires

 Ajout d’un élément dans un dictionnaire

 Exemple
 On souhaite représenter un plateau d'échecs. Généralement, une case de l’échequier
est représentée par une lettre (de A à H) suivie d'un chiffre (de 1 à 8). La lettre définit
la colonne et le chiffre définit la ligne. La valeur contenu dans la case correspond au
nom de la pièce

 Créer un dictionnaire permettant de gérer l’échiquier

81
2.5 Les dictionnaires

 Ajout d’un élément dans un dictionnaire

 Exemple
 Solution

echiquier = {}
echiquier['a', 1] = "tour blanche" # En bas à gauche de l'échiquier
echiquier['b', 1] = "cavalier blanc" # À droite de la tour
echiquier['c', 1] = "fou blanc" # À droite du cavalier
echiquier['d', 1] = "reine blanche" # À droite du fou
# ... Première ligne des blancs
echiquier['a', 2] = "pion blanc" # Devant la tour
echiquier['b', 2] = "pion blanc" # Devant le cavalier, à droite du
pion
# ... Seconde ligne des blancs

82
2.5 Les dictionnaires

 Suppression des clés d’un dictionnaire

 Deux possiblités:
 Mot clé « del »

placard = {"chemise":3, "pantalon":6, "tee shirt":7}

del placard["chemise« ]

 Méthode de dictionnaire « pop »

>>> placard = {"chemise":3, "pantalon":6, "tee shirt":7}

>>> placard.pop("chemise")
3
>>>

 Cette méthode supprime non seulement la clé mais aussi la valeur associée. Elle
retourne cette valeur.

83
2.5 Les dictionnaires

 Parcours d’un dictionnaire

 le parcours d'un dictionnaire ne s'effectue pas tout à fait comme celui d'une liste car il n’est
pas une structure ordonnée

 On utilise généralement des méthodes de l’objet « dict »

 2 méthodes de parcours:
 Parcours des clés

 Parcours des valeurs

 Parcours des deux simultanément

84
2.5 Les dictionnaires

 Parcours d’un dictionnaire

 Parcours des clés

>>> fruits = {"pommes":21, "melons":3, "poires":31}

>>> for cle in fruits:
... print(cle)
...
melons
poires
pommes
>>>

 En parcourant « simplement » un dictionnaire, on parcourt en réalité la liste des clés

contenues dans le dictionnaire

 Remarque :
 L’ordre d’apparition des clés ne suit pas l’ordre de l’initialisation

 Normal car un dictionnaire n’est pas une structure ordonnée

85
2.5 Les dictionnaires

 Parcours d’un dictionnaire

 Parcours des clés
 La méthode « keys() » de l’objet « dict » permet d’obtenir les mêmes résultats

>>> fruits = {"pommes":21, "melons":3, "poires":31}

>>> for cle in fruits.keys():
... print(cle)
...
melons
poires
pommes
>>>

86
2.5 Les dictionnaires

 Parcours d’un dictionnaire

 Parcours des valeurs
 La méthode « values() » renvoie la liste des valeurs du dictionnaire

 Exemple

>>> fruits = {"pommes":21, "melons":3, "poires":31}

>>> for valeur in fruits.values():
... print(valeur)
...
3
31
21
>>>

87
2.5 Les dictionnaires

 Parcours d’un dictionnaire

 Parcours simultané des clés et valeurs
 On utilise la méthode « items() »
 Elle renvoie une liste, contenant les couples (clé : valeur), sous la forme d'un tuple

 Exemple

>>> fruits = {"pommes":21, "melons":3, "poires":31}

>>> for cle, valeur in fruits.items():
... print("La clé {} contient la valeur {}.".format(cle,
valeur))
...
La clé melons contient la valeur 3.
La clé poires contient la valeur 31.
La clé pommes contient la valeur 21.
>>>

88
3. Procédures et fonctions

05/03/2021
89
3.1 Généralités

 Définition et utilité
 Les procédures et fonctions permettent de décomposer un programme complexe en
plusieurs parties plus simple et relativement indépendantes (aussi appelées sous-
programmes)

 Les avantages:

 Elles peuvent implémentées et testées séparément

 Si le même traitement est nécessaire en plusieurs point du programme, on se contente

d’appeler la fonction (ou procédure) correspondante plusieurs fois au lieu de
dupliquer le code source ;

 Une même fonction (ou procédure) peut être utilisée dans plusieurs programmes
différents, grâce au concept de bibliothèque

 Les aspects les plus importantes des fonctions et procédures sont leur création et leur
appel dans des programmes 90
3.1 Généralités

 Fonctionnement d’un programme

 Un programme (ou algorithme) peut être composé d’un ou plusieurs sous-programmes
(exécutant des taches bien définies)

 Un sous-programme est obligatoirement caractérisé par un nom (un identifiant) unique

91
3.1 Généralités

 Environnement d’un sous-programme

 Un sous-programme est caractérisé par 3 types de variables :

 Les variables globales : elles sont définies dans le programme appelant et ont donc
une portée globale

 Les variables locales : Elles sont définies à l’intérieur du sous-programme et ne sont

pas accessible en dehors du sous-programme. Leur portée est locale

 Les variables formels : Il s’agit des variables d’entrées servant d’échanges entre les
programmes appelant et appelé

92
3.2 Les procédures

 Définition
 Une procédure est un sous-programme représentant une ou plusieurs actions, et ne
retournant aucune valeur, sauf en paramètre.

 Déclaration

93
3.2 Les procédures

 Exemple :
 Ecrire une procédure « Age » prenant en paramètre l’année de naissance d’un utilisateur
puis affiche son âge

Procédure Age (Donnees annee_naissance : entier)

Variables :
entier age
Début :
age  2020 – annee_naissance
afficher (‘vous avez ’, age, ‘ ans’)
FinProcedure

94
3.3 Les fonctions

 Définition
 Une fonction est un sous-programme à l’image d’une procédure mais qui retourne des
valeurs

 Déclaration

95
3.3 Les fonctions

 Exemple :
 Ecrire une fonction prenant en 2 entiers puis retournant le plus des 2

Fonction Maximum (Donnees a, b : entier) : entier

Variables :
entier maxi
Début :
si a > b alors
maxi = a
sinon
maxi = b
finsi
retour maxi
FinFonction

96
3.4 Appel de fonction (ou procédure)

 Méthodologie
 Pour utiliser une fonction (ou procédure), on fait un appel en lui passant des expressions
correspondant aux paramètres dont elle a besoin

 La syntaxe est la suivante :

nomFonction( param1, param2, …, paramk) ;

 Exemple : Appel des procédure et fonction défini précédemment

Age( 1901)

X  Maximum(45, 1)

 Remarque : lors de l’appel d’une fonction (ou procédure), un paramètre formel (ou
argument) d’une fonction (ou procédure) peut être une variable ou une valeur mais doit 97
3.4 Appel de fonction (ou procédure)

 Remarque
 Une fonction (ou procédure) avant d’être appelée doit être préalablement définie (et
implémentée)

 Etant donnée qu’une fonction retourne une valeur, il est possible d’affecter cette valeur à
une variable ou peut être utilisée dans une autre fonction ou expression
Fonction Puissance(données x : réel, n : entier) : réel
Variables :
 Exemple réel : resultat
Debut:
resultat  1
pour i allant de 0 à n-1 faire:
resultat  resultat*x
finPour
retour resultat
FinFonction
Algorithme ProgrammePrincipal
réel : x, y
entier : m
Debut:
lire (x)
lire(m)
y  Puissance(x, m) + 2*Puissance(x, m-1)
afficher(y)
afficher(Puissance(x,m))
Fin 98
3.5 Fonctions et procédures en Python

 Syntaxe de déclaration
def nom_del_la_fonction(param1, param2,
paramN):
# Instructions 1
# instruction 2
# ….
# instruction N

 « def » : abréviation du mot « define » en anglais, prélude à toute construction de fonction

 « nom_de_la_fonction » : le nom de la fonction

 Attention : N'utilisez pas un nom de variable déjà instanciée pour nommer une fonction

 « param1, param2, … » : la liste des paramètres de la fonction

 Les deux points « : » clôturent la fonction

 Attention à ne pas l’oublier
 Appel de fonction
 Pour appeler une fonction, on utilise le nom de la fonction en précisant les
99
paramètres, s’il ya en
3.5 Fonctions et procédures en Python

 Exemple
 Reprenons les exemples précédent

def puissance (x, n):

resultat = 1
for i in range(n-1):
resultat = resultat*x
return resultat

x = float(input("saisir x"))
m = float(input("saisir m"))

y = puissance(x, m) + 2*Puissance(x, m-1)

print("y = ", y)
print(puissance(x,m))

100
3.6 Fonctions recursives

 Définition
 On appelle fonction récursive toute fonction qui s’appelle elle-même

 Elle permet de coder des fonctions (mathématiques) définie à partir de relation de

récurrence

 Exemple : calcul du factoriel d’un nombre entier

o 1ère définition

• n! = 1 * 2 * 3 * 4 * … * n

• Traduction par une boucle :

o 2ème définition:

101
3.6 Fonctions récursives

 Définition
 Exemple : calcul du factoriel d’un nombre entier

102
3.6 Fonctions récursives

 Définition
 Dérouler cet algorithme pour factoriel(5)

103
3.7 Les modules

 Qu’est-ce qu’un module ?

 Un module est un fichier « script python » (d’extension « .py ») contenant un ensemble de
fonctions et variables et ayant des rapport entre elles

 Un module python fait généralement appel à des éléments qui sont présents dans d'autres
modules python

 Un programme python peut donc se composer d'un ou de plusieurs modules

 Il existe un grand nombre de modules disponibles sous Python notamment math, cmath,
random, turtle, matplotlib, numpy, pandas, etc…

 Généralement, soit ces modules font déjà partie du langage python (ex. random, numpy)
soit on peut les trouver sur internet (ex. pandas librairie très utile science de données)
3.8 Les modules

 Comment importer un module ?

 Pour importer un module, il suffit d’utiliser le mot clé « import » suivi du nom du module

 Exemple : pour importer le module « math » dans un programme, il suffit de faire :

import math

 Pour appeler une fonction contenue dans un module, il faut taper le nom du module suivi
de « . »

>>> math.sqrt(16)
4>
>>

105
3.8 Les modules

 Comment importer un module ?

 Pour connaître les fonctions disponibles dans le module « math », il suffit d’utiliser la
fonction « help »

>>> help("math")
Help on built-in module math:
NAME
math
FILE
(built-in)
DESCRIPTION
This module is always available. It provides access to the
mathematical functions defined by the C standard.
FUNCTIONS
acos(...)
acos(x)
Return the arc cosine (measured in radians) of x.
acosh(...)
acosh(x)
Return the hyperbolic arc cosine (measured in radians) of x.
asin(...)
-- Suite --

106
3.8 Les modules

 Comment importer un module ?

 Il est possible de remplacer le nom d’un module par un autre nom lors de l’importation

 Exemple

import math as mathematiques

mathematiques.sqrt(25)

 « mathématiques » est désormais l’homonyme du module « math »

 Très utile pour « retrouver ses repaires » dans la liste interminable des modules
proposés par python

107
3.8 Les modules

 Comment importer un module ?

 Lors de l’appel d’un module donné, toutes les fonctions et variables définies dans ce
modules sont importés

 Conséquences : ralentissement de la performance du code

 Il est donc possible d’importer une partie des fonctionnalités contenues dans un module.
Pour cela, il suffit d’utiliser la méthode suivante :

from … import …

 Exemple
>>> from math import fabs
>>> fabs(-5)
5>
>> fabs(2)
2>
>>

 Pour importer toutes les fonctionnalités d’un module

>>> from math import *
108
3.9 Exercices

 Exercice 1 :
 Ecrire l’algorithme de la fonction « Moyenne » prenant en paramètre un tableau « T » de N
éléments puis effectue la moyenne des nombres pairs
 Exercice 2 (Algorithme et traduction en Langage Python):
 On souhaiterait calculer la somme d’ordre n de Sn défini comme suit :

(−1)𝑖+1
𝑆𝑛 = σ𝑛𝑖=0 𝑋𝑖 (1) avec X ≠0
𝑖!

a. Ecrire l’algorithme de la fonction « puissance » prenant en paramètre un nombre réel X et

un entier « m » puis calcule et retourne 𝑋 𝑚

b. Ecrire l’algorithme de la fonction « factoriel » prenant en paramètre un entier « k » puis

calculant et retournant le factoriel de k en utilisant la récursivité

c. Ecrire un algorithme demandant à l’utilisateur de saisir l’entier n et un nombre réel x puis de

calculer et d’afficher l’équation décrite par (1)
109
3.9 Exercices

 Exercice 3 :
 On souhaiterait calculer les indicateurs statistiques des notes des étudiants en 2ème des
CPGE. Il s’agit de calculer les indicateurs suivants:
 La moyenne générale

 L’écart-type

 La moyenne géométrique

 Les meilleures notes (note > 15) et les pires notes (note < 5)

 Ecrire les fonctions (Moyenne, EcartType et MoyenneGeometrique) prenant en paramètre

un tableau de taille N puis realisant leur taches respectives

 Ecrire les procédures MeilleuresNotes et PireNotes prenant en paramètre un tableau de

taille N puis affichant respectivement les meilleures et pires notes

 Dans la fonction principale, demander à l’utilisateur saisir le nombre total de notes puis de
remplir les notes et d’afficher les statistiques des notes
110
4. Algorithmes de tri

05/03/2021
111
4.1 Introduction

 Définition:
 Un tableau T est dit « trié en ordre croissant » si tous les éléments consécutifs du tableau
vérifient :

 Il est admis qu’un :

 tableau vide est trié

 tableau ne contenant qu’un seul élément est trié

 D’où la définition:

 Un tableau vide (n=0) est ordonné (trié)

 Un tableau contenant un seul élément (n=1) est ordonné

 Un tableau T[1,…n], (n > 1) est ordonné si

112
4.2 Tri d’un tableau

 Principe:
 Soit un vecteur (tableau à une dimension) T[1..n] à valeurs dans un ensemble E de valeurs
muni d’une relation d’ordre notée <

 Trier le vecteur T consiste à construire un vecteur T‘[1..n] tel que :

 T‘ soit trié,

 T‘ et T contiennent les mêmes éléments.

 Le plus souvent T et T‘ sont le même vecteur ; T‘ est construit en permutant entre eux les
éléments de T

 Les méthodes de tri les plus populaires sont:

 Le tri par remplacement

 Le tri par insertion

 Le tri par sélection

 Le tri à bulles 113

4.2 Tri d’un tableau

 Tri par remplacement:

 Cette méthode simple et intuitive est malheureusement très peu performante.

 Elle consiste à construire un tableau Ttrié[1..n] à partir de T[1..n] tel que :

 Principe :

 Identifier le maximum du tableau T

 Rechercher le minimum du tableau T

 Recopier ce minimum dans Ttrié à la position i

 Remplacer le minimum du tableau T par le maximum

 Recommencer pour i+1

114
4.2 Tri d’un tableau

 Tri par remplacement:

115
4.2 Tri d’un tableau

 Tri par remplacement

 Inconvénients:

 Pour chaque élément rangé dans le tableau Ttrié, il faut parcourir tout le tableau T et
non une partie du tableau T

 Nécessite un 2ème tableau, or si le nombre d’éléments à trier est important, cet

algorithme requiert donc un espace mémoire double.

116
4.2 Tri d’un tableau

 Tri par insertion

 Cette méthode de tri insère (au ième passage) le ième élément T[i] à la bonne place parmi
T[1],T[2]...T[i-1].

 Après l'étape i, tous les éléments entre la première et la ième position sont triés.

 Il existe plusieurs méthode de tri par insertion selon le principe qui est utilisé pour
rechercher le rang de l’élément à insérer parmi les éléments du début de la liste déjà triés

117
4.2 Tri d’un tableau

 Tri par insertion

118
4.2 Tri d’un tableau

 Tri par sélection

 Le principe du tri par sélection d'un vecteur est d'aller chercher le plus petit élément du
vecteur pour le mettre en premier, puis de repartir du second, d'aller chercher le plus petit
élément pour le mettre en second etc.

 Au ième passage, on sélectionne l’élément ayant la plus petite valeur parmi les positions i..n
et on l'échange avec T[i].

119
4.2 Tri d’un tableau

 Tri par sélection

120
4.2 Tri d’un tableau

 Tri à bulles
 Le principe du tri à bulles (bubble sort) est de :

 comparer deux à deux les éléments e1 et e2 consécutifs d'un tableau ;

 et d'effecteur une permutation si e1 > e2 . On

 continue de trier jusqu'à ce qu'il n'y ait plus de permutation.

121
4.2 Tri d’un tableau

 Tri à bulles

122
 Fin

2019/2020 L1/ESI 123