Algorithmes de recherche et tri par comptage
Sakina ZININI
CPGE Salmane Al Farissi - Salé / MPSI - 1TSI
2023 - 2024
1 Introduction
2 Algorithmes de recherche
Recherche séquentielle
Recherche dichotomique
3 Problème de tri et Algorithme de tri par comptage
Concepts de base
Algorithme de tri par comptage
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 2 / 25
Introduction
• Dans ce chapitre, nous allons étudier deux problèmes fondamen-
taux en algorithmique : La recherche et le tri.
• Ces algorithmes sont à la base de la plupart des bons algorithmes
qui manipulent des données organisées.
• La recherche dans un multi-ensemble (des éléments ayant la même
valeur) muni d’un ordre total, consiste à comparer ces éléments
avec l’élément recherché afin de déterminer son existence.
• En ce qui concerne le tri, C’est la procédure d’ordonner un multi-
ensemble d’éléments en fonction de clés sur lesquelles est définie
une relation d’ordre.
• Par la suite, on utilise une structure tabulaire pour représenter les
multi-ensembles.
• Implémentation par les listes en Python.
L’algorithmique est la branche de l’informatique qui traite des algo-
rithmes.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 3 / 25
Introduction
Exemple :
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 4 / 25
Algorithmes de recherche
Définition
Le problème de recherche consiste à vérifier l’existence d’un élément
dans un multi-ensemble particulier. Il fournit en sortie une information
liée à l’existence de l’élément recherché dans le multi-ensemble :
Algorithme :
Entrée : Un tableau a[1..n] ayant n ≥ 1 éléments d’un certain
type T et une valeur (ou clé) e de type T.
Sortie : i tel que a[i] = e ou NonTrouvé (ex : −1).
• La méthode séquentielle parcourt l’un après l’autre les éléments
de la multi-ensemble en les comparant à l’´élément recherché.
• La méthode dichotomique, utilisable uniquement lorsque les élé-
ments sont rangés en ordre (croissant ou décroissant), s’appuie
sur cette propriété d’ordre pour éliminer à chaque comparaison,
la moitié des éléments de l’ensemble restant à traiter.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 5 / 25
Algorithmes de recherche Recherche séquentielle
Recherche séquentielle
Définition
La recherche séquentielle (sequential search) parcourt, case après case,
les n éléments d’un tableau a et s’arrête au premier élément rencontré
qui est égal à l’élément e. Dans ce cas l’information renvoyée est la
position contenant l’élément recherché.
Exemple :
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 6 / 25
Algorithmes de recherche Recherche séquentielle
Algorithme : Version itérative.
La version itérative repose sur un parcours (de la gauche vers la
droite) des cases du tableau :
1 Au départ on se positionne sur la première case du tableau
2 A chaque itération (passage de boucle) on examine le contenu
d’une case :
S’il est égal à l’élément cherché : on termine en renvoyant la
position.
Sinon on passe à la case suivante.
3 Si on traverse tout le tableau : l’élément cherché n’était pas pré-
sent.
Exercice 1
Implémenter la version itérative de la recherche séquentielle.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 7 / 25
Algorithmes de recherche Recherche séquentielle
Solution :
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 8 / 25
Algorithmes de recherche Recherche séquentielle
Algorithme : Version récursive.
La récursion se fait sur la taille (= nombre d’éléments) du sous-
tableau :
1 Si la taille est 0 : l’élément cherché n’y est pas.
2 Sinon on compare l’élément cherché avec le premier élément :
S’il y a égalité : on renvoie cette position.
Sinon on recommence sur le sous-tableau privé de son premier
élément.
Exercice 2
Implémenter la version récursive de la recherche séquentielle.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 9 / 25
Algorithmes de recherche Recherche séquentielle
Solution :
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 10 / 25
Algorithmes de recherche Recherche dichotomique
Recherche dichotomique
• La recherche séquentielle dans un tableau trié augmente le nombre
de comparaisons à effectuer pour trouver un élément donné. C’est
une méthode naïve qui n’exploite pas l’information de tri. En re-
vanche la recherche par dichotomie utilise cette information sur
l’ordre des éléments de manière beaucoup plus efficace.
Définition
La recherche par dichotomie (binary search) compare l’élément cherché
e avec l’élément en position m situé au milieu du sous-tableau : Si
e == a[m] alors l’élément e est trouvé, sinon si e > a[m] alors e se
trouve dans la moitié droite du sous tableau sinon (c-à-d e < a[m])
l’élément e se trouve dans la moitié gauche du sous tableau.
Le tableau a[1..n] est supposé TRIÉ par valeurs strictement croissantes.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 11 / 25
Algorithmes de recherche Recherche dichotomique
Exemple : Chercher la valeur 7.
Si le tableau contient plusieurs fois l’élément cherché, la fonction
renverra l’indice du premier élément trouvé.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 12 / 25
Algorithmes de recherche Recherche dichotomique
Algorithme : Version itérative.
soit e un élément qui se trouve entre la position d et f du tableau a,
avec d ≤ f .
1 Calculer l’élément pivot m = ⌊ d+f
2
⌋.
2 Si e == a[m] alors on renvoie la position m.
3 Sinon, si e > a[m] alors d reçoit m + 1.
4 Sinon, c’est à dire e < a[m] alors f = m − 1.
5 on continue ainsi la recherche, et après chaque comparaison, la
taille du sous tableau restant à traiter diminue de moitié. La re-
cherche se termine si d > f , Dans ce cas e n’est pas présent dans
le sous tableau.
Exercice 3
Implémenter la version itérative de la recherche dichotomique.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 13 / 25
Algorithmes de recherche Recherche dichotomique
Solution :
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 14 / 25
Algorithmes de recherche Recherche dichotomique
Algorithme : Version récursive.
1 Si d > f ou la taille de a vaut 0, l’algorithme termine en renvoyant
-1 (NonTrouvé).
2 Sinon, procéder de la manière suivante :
Calculer l’élément pivot m = ⌊ d+f
2 ⌋.
Si e == a[m] alors retourner la position m.
Sinon si e > a[m] alors chercher dans la partie supérieure du sous
tableau.
Sinon, chercher dans la partie inférieure du sous tableau.
3 A chaque appel récursif, la taille du sous tableau restant à traiter
diminue de moitié. Si la recherche aboutit sur un tableau de taille
nulle ou d > f , e n’est pas présent et la recherche s’arrête.
Exercice 4
Implémenter la version récursive de la recherche dichotomique.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 15 / 25
Algorithmes de recherche Recherche dichotomique
Solution :
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 16 / 25
Problème de tri et Algorithme de tri par comptage
• Les premières suites d’instruc-
tions permettant d’effectuer
un tri ont été étudiées pendant
la seconde guerre mondiale.
• L’américaine Betty Holberton
était une de six program-
meuses de l’ENIAC. Elle a dé-
veloppe le premier algorithme
de tri.
• Elle consacra ensuite sa car-
rière au développement des
langages Fortran et Cobol.
ENIAC : le premier ordinateur électronique, destiné pour résoudre, en
principe, tous les problèmes de calcul numérique.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 17 / 25
Problème de tri et Algorithme de tri par comptage Concepts de base
Définition
Trier consiste à ordonner les éléments d’un multi-ensemble (représentée
par un structure tabulaire) en fonction de clés sur lesquelles est définie
une relation d’ordre.
Algorithme de tri :
Entrée : Un tableau de n nombres [a1 , a2 , ..., an ].
Sortie : Permutation [a1′ , a2′ , ..., an′ ] des éléments du tableau donné
en entrée, de façon que a1′ ≤ a2′ ≤ ... ≤ an′ .
Exemple :
• Entrée : 5, 7, −1, 3, 1, 2.
• Tri : classement par ordre croissant (par exemple).
• Sortie : −1, 1, 2, 3, 5, 7.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 18 / 25
Problème de tri et Algorithme de tri par comptage Concepts de base
Un tri ne supprime pas les doublons.
Quel que soit l’algorithme de tri, un tableau vide ou réduite à un
unique élément est (déjà) triée.
Stabilité d’un algorithme de tri
• Un algorithme de tri est stable s’il ne modifie jamais l’ordre relatif
de deux éléments de clés égales.
• Exemple : Trier([3, 1, 2, 1]) → [ 1, 1, 2, 3].
Tri en place
• Un tri se fait en place s’il ne nécessite pas de placer plus d’un
nombre constant d’éléments hors du tableau d’entrée.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 19 / 25
Problème de tri et Algorithme de tri par comptage Concepts de base
Opérations élémentaires de tri
• La comparaison de deux éléments.
• La permutation (échange des valeurs) de deux éléments.
Algorithmes de tri
• Dans "The Art Of Computer Pro-
gramming", Donald Knuth a analysé
environ 25 algorithmes de tri diffé-
rents.
• Chaque algorithme a des avantages et
des inconvénients.
• Ce qui marche bien pour un problème
ne marche pas bien pour un autre.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 20 / 25
Problème de tri et Algorithme de tri par comptage Concepts de base
Il n’y a donc pas un meilleur tri, il y en a plusieurs. Mais il y en a qui
sont très mauvais (inefficaces).
Visualisation graphique des tris
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 21 / 25
Problème de tri et Algorithme de tri par comptage Algorithme de tri par comptage
Définition
L’algorithme de tri par comptage (counting sort) permet de trier un
multi-ensemble qui satisfait à ces deux critères :
• Ses éléments prennent un nombre fini de valeurs.
• La différence entre la valeur maximale et la valeur minimale est
proche du nombre n de ses éléments.
Considérons le cas d’un tableau a de longueur n dont les valeurs sont
prises dans l’ intervalle entier [|0, k − 1|].
• En itérons sur le tableau a, il est possible de compter le nombre
d’occurrences de chacune des k valeurs possibles.
• Le résultat est stocké dans un autre tableau de longueur propor-
tionnel à k.
• Chaque valeur de l’intervalle [|0, k − 1|] est ensuite rangée dans
le tableau a autant de fois que nécessaire.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 22 / 25
Problème de tri et Algorithme de tri par comptage Algorithme de tri par comptage
Exemple :
• Le tableau a avant tri :
• Le tableau t de comptage :
• Le tableau a après le tri :
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 23 / 25
Problème de tri et Algorithme de tri par comptage Algorithme de tri par comptage
Algorithme :
Soit a un tableau des entiers naturels.
1 On crée un tableau t de max (a) + 1 valeurs.
2 On met toutes ses valeurs à 0.
3 On traverse a et on compte le nombre de fois ou a[i] est pris en
incrémentant t[a[i]].
4 Ensuite on balaie le tableau t et on copie autant de fois une valeur
qu’elle apparait dans t.
Exercice 5
Implémenter l’algorithme de tri par comptage.
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 24 / 25
Problème de tri et Algorithme de tri par comptage Algorithme de tri par comptage
Solution :
Sakina ZININI (CPGE Salmane Al Farissi - Salé
Algorithmes
/ MPSI - de
1TSI)
recherche et tri par comptage 2023 - 2024 25 / 25
