Les algorithmes de tri et de recherche
MPSI-PCSI
Introduction Les algorithmes de recherche Les algorithmes de tri
Plan
1 Introduction
2 Les algorithmes de recherche
3 Les algorithmes de tri
1/22
Introduction Les algorithmes de recherche Les algorithmes de tri
Introduction
Rechercher un élément dans une collection de données est l’un des
nombreux problèmes fondamentaux de l’informatique.
Recherche d’un mot dans une page web.
Recherche d’une phrase dans un livre.
Recherche d’un individu dans une base de données.
De nombreuses structures de données et algorithmes ont été conçus
pour permettre une recherche efficace.
2/22
Introduction Les algorithmes de recherche Les algorithmes de tri
Introduction
Pour pouvoir faire la recherche dans un temps minimal, on procède à
trier la structure de données selon un ordre précis.
Les objets à trier doivent faire, donc, partie d’un ensemble muni
d’une relation d’ordre.
Parmi les ordres les plus utilisés, on trouve l’ordre numérique et
l’ordre lexicographique(Pour les chaînes de caractères).
Dans ce cours, on s’intéresse à quelques algorithmes de tri et de
recherche d’un élément dans une liste.
3/22
Introduction Les algorithmes de recherche Les algorithmes de tri
Définition
Définition 1
Un algorithme est une suite finie et non ambiguë d’instructions et
d’opérations permettant de résoudre une classe de problèmes.
4/22
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche séquentielle
Problème : Est-ce qu’un objet x appartient à une liste L ?
Le principe de la recherche séquentielle consiste à parcourir tous les
éléments de la liste tout en les comparant avec x, jusqu’à ce que
l’élément recherché soit trouvé, ou que tous les éléments ont été
traités avec un résultat négatif.
5/22
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche séquentielle
Problème : Est-ce qu’un objet x appartient à une liste L ?
Le principe de la recherche séquentielle consiste à parcourir tous les
éléments de la liste tout en les comparant avec x, jusqu’à ce que
l’élément recherché soit trouvé, ou que tous les éléments ont été
traités avec un résultat négatif.
Exemple : valeur cherchée = 10
5/22
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche séquentielle
Exercice :
1 Ecrire une fonction appartient(element, liste) qui vérifie si un
élément appartient à une liste en utilisant l’algorithme de la
recherche séquentielle.
2 Créer une liste L0 ayant 10 nombres entiers aléatoires.
3 Tester la fonction avec un entier x de votre choix et la liste L0.
4 Adapter votre fonction pour renvoyer l’indice de x s’il existe, et
None sinon.
6/22
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche séquentielle
Implémentation de la recherche séquentielle en Python :
1 def r e c h e c h e r _ s e q u e n t i e l l e (L , val ) :
2 n = len ( L )
3 for i in range ( n ) :
4 if L [ i ]== val :
5 return True
6 return False
7/22
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche dichotomique
La recherche dichotomique : Est un algorithme de recherche d’une
valeur v dans une liste triée L.
8/22
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche dichotomique
La recherche dichotomique : Est un algorithme de recherche d’une
valeur v dans une liste triée L.
Le principe de cet algorithme est le suivant :
On compare la valeur recherché avec l’élément au « milieu » de la
liste. On a alors 3 cas de figure :
8/22
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche dichotomique
La recherche dichotomique : Est un algorithme de recherche d’une
valeur v dans une liste triée L.
Le principe de cet algorithme est le suivant :
On compare la valeur recherché avec l’élément au « milieu » de la
liste. On a alors 3 cas de figure :
Si la valeur recherchée et supérieure à la valeur au milieu, alors
elle se trouve dans la moitié droite de la liste : son indice et
supérieur à « milieu ».
Si la valeur recherchée et inférieure à la valeur au milieu, la
valeur recherché se trouve dans la première partie de la liste : càd
à gauche de « milieu ».
On réitère la même opération avec la « moitié » du tableau qui est
censée contenir la valeur recherchée, jusqu’à ce qu’elle soit trouvée,
ou que la liste ne comporte plus qu’un seul élément.
Si la valeur recherchée et égale à la valeur située au « milieu » ,
8/22
voilà v est trouvée !
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche dichotomique
Exemple :
liste : [2, 8, 10, 16, 25]
valeur cherchée = 8
9/22
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche dichotomique
Exemple :
liste : [2, 8, 10, 16, 25]
valeur cherchée = 8
1 On commence par le milieu, et on compare :
9/22
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche dichotomique
Exemple :
liste : [2, 8, 10, 16, 25]
valeur cherchée = 8
1 On commence par le milieu, et on compare :
2 8 est inférieure à 10, donc on réitère le même processus dans la
première partie de notre liste.
9/22
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche dichotomique
Exemple :
liste : [2, 8, 10, 16, 25]
valeur cherchée = 8
1 On commence par le milieu, et on compare :
2 8 est inférieure à 10, donc on réitère le même processus dans la
première partie de notre liste.
3 L’élément recherché est trouvé.
9/22
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche dichotomique
Exercice : Implémenter l’algorithme de la recherche dichotomique
en python.
10/22
Introduction Les algorithmes de recherche Les algorithmes de tri
La recherche dichotomique
Exercice : Implémenter l’algorithme de la recherche dichotomique
en python.
1 def r e c h e r c h e _ d i c h o t o m i q u e (L , val ) :
2 debut , fin =0 , len ( L ) -1
3 milieu =( debut + fin ) //2
4 while debut < fin and L [ milieu ] != val :
5 if L [ milieu ] > val :
6 fin = milieu -1
7 else :
8 debut = milieu +1
9 milieu =( debut + fin ) //2
10 return L [ milieu ] == val
10/22
Introduction Les algorithmes de recherche Les algorithmes de tri
Tri par comptage
Le tri par comptage est une méthode de tri extrêmement efficace mais
ne s’applique que dans le cas où on sait déjà que notre liste sera
composée d’entiers entre deux bornes connues.
Par exemple si j’ai une liste d’un milliard de notes sur 20 à ranger par
ordre croissant, le tri par comptage sera le meilleur.
11/22
Introduction Les algorithmes de recherche Les algorithmes de tri
Tri par comptage
Le principe est simple : D’abord on détermine les bornes inférieure et
supérieur de la liste. Par exemple, supposons que tous les nombres
de la liste L initiale soient entre 0 et 100.
1 On crée une liste d’occurences L_Occ ayant 101 zéros (i.e La
borne supérieur + 1) qui nous servira pour compter les
occurences de chaque élément de la liste.
2 Pour chaque élément e de notre liste. On rajoute 1 à l’élément
d’indice e dans la liste des occurences L_Occ.
3 Maintenant qu’on sait combien apparait chaque élément dans la
liste, on l’utilise pour créer notre liste triée L_finale ; on balaye la
liste d’occurences L_Occ et on ajoute l’indice e à L_finale un
nombre L_Occ[e] de fois.
12/22
Introduction Les algorithmes de recherche Les algorithmes de tri
Tri par comptage
Exemple :
Liste initiale : L = [ 3, 0, 2, 2, 3, 2]
Liste_Occurences : [1, 0, 3, 2]
Liste triée : [0, 2, 2, 2, 3, 3]
13/22
Introduction Les algorithmes de recherche Les algorithmes de tri
Tri par comptage
Exercice : Implémenter l’algorithme de tri par comptage.
Indications :
1 Déterminer le maximum de La liste initiale.
2 Créer une liste L_Occurences de taille maximum+1.
Elle doit être initialisée par des zéros.
3 Remplir L_Occurences.
4 Utiliser L_Occurences pour remplir la liste triée.
14/22
Introduction Les algorithmes de recherche Les algorithmes de tri
Tri par comptage
Exercice : Implémenter l’algorithme de tri par comptage.
15/22
Introduction Les algorithmes de recherche Les algorithmes de tri
Le tri à bulle
Le principe du tri à bulles est de comparer chaque deux valeurs
adjacentes dans la liste et d’inverser leurs positions si elles (les deux)
sont mal triées.
Exemple :
16/22
Introduction Les algorithmes de recherche Les algorithmes de tri
Le tri à bulle
Algorithme : L’idée est de faire remonter vers la fin de la liste les
éléments les plus grands en les déplaçant de la manière suivante :
1 On considère le premier élément de notre liste et on le compare
avec le second. S’il est plus grand on les permute.
2 On considère maintenant le second élément et on le compare au
troisième. S’il est plus grand on les permute.
3 On continue ainsi jusqu’à la fin de la liste. A cette étape,
l’élément le plus grand se trouve forcément à la fin de liste.
4 On répéte les trois premières étapes mais cette fois-ci on s’arrête
à l’avant-dernière position (puisque le plus grand élément se
trouve déjà à la fin).
5 On continue ainsi en reculant à chaque fois la position finale des
comparaisons.
17/22
Introduction Les algorithmes de recherche Les algorithmes de tri
tri à bulle
Exercice : Implémenter l’algorithme du tri à bulle en python.
18/22
Introduction Les algorithmes de recherche Les algorithmes de tri
tri à bulle
Exercice : Implémenter l’algorithme du tri à bulle en python.
18/22
Introduction Les algorithmes de recherche Les algorithmes de tri
tri par sélection
Le principe de ce tri est :
1 chercher le plus grand (ou le plus petit) élément, le placer à la fin
(ou au début) de la liste.
2 chercher le second plus grand (ou le second plus petit) élément,
le placer à l’avant-dernière (ou à la seconde) position
3 On réitère jusqu’à traiter la totalité de la liste.
19/22
Introduction Les algorithmes de recherche Les algorithmes de tri
tri par sélection
Le principe de ce tri est :
1 chercher le plus grand (ou le plus petit) élément, le placer à la fin
(ou au début) de la liste.
2 chercher le second plus grand (ou le second plus petit) élément,
le placer à l’avant-dernière (ou à la seconde) position
3 On réitère jusqu’à traiter la totalité de la liste.
Exemple :
19/22
Introduction Les algorithmes de recherche Les algorithmes de tri
tri par sélection
Exercice : Implémenter l’algorithme du tri pa sélection en python.
Indication : Définir une fonction recherche_indice_max(L,i) qui
permet de trouver l’indice du maximum d’une partie de la liste ( de 0
jusqu’à un indice i).
20/22
Introduction Les algorithmes de recherche Les algorithmes de tri
tri par sélection
Exercice : Implémenter l’algorithme du tri pa sélection en python.
Indication : Définir une fonction recherche_indice_max(L,i) qui
permet de trouver l’indice du maximum d’une partie de la liste ( de 0
jusqu’à un indice i).
1 def r e c h e r c h e _ i n d i c e _ m a x (L , i ) :
2 ind_max =0
3 for j in range ( i ) :
4 if L [ j ] > L [ ind_max ]:
5 ind_max = j
6 return ind_max
7
8 def tri_selection ( L ) :
9 n = len ( L )
10 for i in range (n -1 ,0 , -1) :
11 ind_max = r e c h e r c h e _ i n d i c e _ m a x (L , i )
12 if ind_max != i :
13 L [ i ] , L [ ind_max ]= L [ ind_max ] , L [ i ]
20/22
Introduction Les algorithmes de recherche Les algorithmes de tri
tri par insertion
C’est le tri souvent utilisé pour le jeu de cartes : Dans chaque étape on
insére le i-ème élément à sa place parmi ceux qui le précèdent. Pour
ce faire, il faut chercher son emplacement en le comparant à ceux qui
le précèdent, puis les décaler afin de pouvoir effectuer l’insertion.
21/22
Introduction Les algorithmes de recherche Les algorithmes de tri
tri par insertion
C’est le tri souvent utilisé pour le jeu de cartes : Dans chaque étape on
insére le i-ème élément à sa place parmi ceux qui le précèdent. Pour
ce faire, il faut chercher son emplacement en le comparant à ceux qui
le précèdent, puis les décaler afin de pouvoir effectuer l’insertion.
Exemple :
21/22
Introduction Les algorithmes de recherche Les algorithmes de tri
tri par insertion
Exercice : Implémenter l’algorithme du tri par insertion en python.
22/22
Introduction Les algorithmes de recherche Les algorithmes de tri
tri par insertion
Exercice : Implémenter l’algorithme du tri par insertion en python.
1 def tri_insertion ( L ) :
2 n = len ( L )
3 for i in range (1 , n ) :
4 pos = i
5 while L [ pos -1] > L [ i ] and pos >0:
6 pos = pos -1
7 elt = L [ i ]
8 for j in range (i , pos , -1) :
9 L [ j ]= L [j -1]
10 L [ pos ]= elt
22/22
