Cours 5 Algorithmique et Programmation
Algorithmes de Tri et de recherche
Prof Kaninda Musumbu
1 Université de Bordeaux & ESIS - Salama (RDC)
K Musumbu Algorithmique et Programmation
Algorithmes de tri et de recherche
Problème du tri
Trier des objets en fonction d’un ordre sur une clef. Cela revient
à trier un tableau d’entiers.
Critères :
Complexité en temps.
Complexité en espace (tri sur place).
tri stable (deux objets du tableau ayant des clefs identiques
sont ordonnées dans le tableau résultat comme dans le
tableau de départ).
K Musumbu Algorithmique et Programmation
Algorithmes de tri et de recherche
Problème du tri
Trier des objets en fonction d’un ordre sur une clef. Cela revient
à trier un tableau d’entiers.
Critères :
Complexité en temps.
Complexité en espace (tri sur place).
tri stable (deux objets du tableau ayant des clefs identiques
sont ordonnées dans le tableau résultat comme dans le
tableau de départ).
K Musumbu Algorithmique et Programmation
Algorithmes de tri et de recherche
Problème du tri
Trier des objets en fonction d’un ordre sur une clef. Cela revient
à trier un tableau d’entiers.
Critères :
Complexité en temps.
Complexité en espace (tri sur place).
tri stable (deux objets du tableau ayant des clefs identiques
sont ordonnées dans le tableau résultat comme dans le
tableau de départ).
K Musumbu Algorithmique et Programmation
Algorithmes de tri et de recherche
Problème du tri
Trier des objets en fonction d’un ordre sur une clef. Cela revient
à trier un tableau d’entiers.
Critères :
Complexité en temps.
Complexité en espace (tri sur place).
tri stable (deux objets du tableau ayant des clefs identiques
sont ordonnées dans le tableau résultat comme dans le
tableau de départ).
K Musumbu Algorithmique et Programmation
Algorithmes de tri et de recherche
Problème du tri
Trier des objets en fonction d’un ordre sur une clef. Cela revient
à trier un tableau d’entiers.
Critères :
Complexité en temps.
Complexité en espace (tri sur place).
tri stable (deux objets du tableau ayant des clefs identiques
sont ordonnées dans le tableau résultat comme dans le
tableau de départ).
K Musumbu Algorithmique et Programmation
Echange de deux valeurs du tablea
Algorithme .1 : Echange(T,i,j)
Données : Un tableau T et deux indices valides i et j
Résultat : Le tableau T avec T[i] et T[j] echangés
Θ(1)
aux ← T[i];
T[i] ← T[j];
T[j] ← aux;
K Musumbu Algorithmique et Programmation
Décalages dans un tableau
Algorithme .2 : DecalageDroite(T,g,d)
Données : Un tableau T et deux indices valides g et d>g
Résultat : Le tableau T avec pour k dans ]g,d], T’[k]=T[k-1] et
T’[g]=T[d]
Θ(d − g)
aux ← T[d];
pour k=d g+1 faire
T[k] ← T[k-1];
T[g] ← aux;
K Musumbu Algorithmique et Programmation
Décalages dans un tableau
Algorithme .3 : DecalageGauche(T,g,d)
Données : Un tableau T et deux indices valides g et d>g
Résultat : Le tableau T pour k dans [g,d[, T’[k]=T[k+1] et
T’[d]=T[g]
Θ(d − g)
aux ← T[g];
pour k=g à d-1 faire
T[k] ← T[k+1];
T[d] ← aux;
K Musumbu Algorithmique et Programmation
Algorithmes de tri
tri par sélection
idée et exemple Trouver le plus petit pour l’échanger avec le
premier, recommencer avec le second plus petit, et ainsi de
suite.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < i sont triées et
placées.
Les variables du tableau avec un indice ≥ i sont ≥ T [i − 1].
K Musumbu Algorithmique et Programmation
Algorithmes de tri
tri par sélection
idée et exemple Trouver le plus petit pour l’échanger avec le
premier, recommencer avec le second plus petit, et ainsi de
suite.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < i sont triées et
placées.
Les variables du tableau avec un indice ≥ i sont ≥ T [i − 1].
K Musumbu Algorithmique et Programmation
Algorithmes de tri
tri par sélection
idée et exemple Trouver le plus petit pour l’échanger avec le
premier, recommencer avec le second plus petit, et ainsi de
suite.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < i sont triées et
placées.
Les variables du tableau avec un indice ≥ i sont ≥ T [i − 1].
K Musumbu Algorithmique et Programmation
Algorithmes de tri
tri par sélection
idée et exemple Trouver le plus petit pour l’échanger avec le
premier, recommencer avec le second plus petit, et ainsi de
suite.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < i sont triées et
placées.
Les variables du tableau avec un indice ≥ i sont ≥ T [i − 1].
K Musumbu Algorithmique et Programmation
Algorithmes
Algorithme .4 : TriSelection(T)
Données : Un tableau T d’entiers
Résultat : Le tableau T trie par ordre croissant des valeurs
pour i=0 à longueur(T)-1 faire /* Θ(n2 ) */
iMin ← i;
pour j=i+1 à longueur(T)-1 faire /* Θ(n − i) */
si T[j] <T [iMin] alors /* Θ(1) */
iMin ← j;
si i 6= iMin alors /* Θ(1) */
Echange(T,i,iMin); /* Θ(1) */
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps : Θ(n2 )
Complexité en espace : Θ(1)
Tri stable : Non comme tous les tris qui échangent des
variables dont les indices sont non consécutifs.
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps : Θ(n2 )
Complexité en espace : Θ(1)
Tri stable : Non comme tous les tris qui échangent des
variables dont les indices sont non consécutifs.
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps : Θ(n2 )
Complexité en espace : Θ(1)
Tri stable : Non comme tous les tris qui échangent des
variables dont les indices sont non consécutifs.
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps : Θ(n2 )
Complexité en espace : Θ(1)
Tri stable : Non comme tous les tris qui échangent des
variables dont les indices sont non consécutifs.
K Musumbu Algorithmique et Programmation
Tri selection : python
def triSelection(T) :
n = len(T)
for i in range(n) :
iMin = i
for j in range(i+1,n) :
if T[j]<T[iMin] :
iMin = j
if iMin != i :
echange(T,i,iMin)
K Musumbu Algorithmique et Programmation
Tri à bulles
Idée et exemple
On permute tout couple de cases successives mal ordonnées.
Un premier parcours emmène la plus grande valeur jusqu’à la
dernière case du tableau, comme les grosses bulles qui
remontent à la surface de l’eau plus vite que les petites. Un
second parcours fait remonter la deuxième plus grande valeur,
et il suffit d’arrêter la remontée à l’avant-dernière case du
tableau ; et ainsi de suite.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice > i sont triées et
placées.
Les variables du tableau avec un indice ≤ i sont ≤ T [i − 1].
K Musumbu Algorithmique et Programmation
Tri à bulles
Idée et exemple
On permute tout couple de cases successives mal ordonnées.
Un premier parcours emmène la plus grande valeur jusqu’à la
dernière case du tableau, comme les grosses bulles qui
remontent à la surface de l’eau plus vite que les petites. Un
second parcours fait remonter la deuxième plus grande valeur,
et il suffit d’arrêter la remontée à l’avant-dernière case du
tableau ; et ainsi de suite.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice > i sont triées et
placées.
Les variables du tableau avec un indice ≤ i sont ≤ T [i − 1].
K Musumbu Algorithmique et Programmation
Tri à bulles
Idée et exemple
On permute tout couple de cases successives mal ordonnées.
Un premier parcours emmène la plus grande valeur jusqu’à la
dernière case du tableau, comme les grosses bulles qui
remontent à la surface de l’eau plus vite que les petites. Un
second parcours fait remonter la deuxième plus grande valeur,
et il suffit d’arrêter la remontée à l’avant-dernière case du
tableau ; et ainsi de suite.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice > i sont triées et
placées.
Les variables du tableau avec un indice ≤ i sont ≤ T [i − 1].
K Musumbu Algorithmique et Programmation
Tri à bulles
Idée et exemple
On permute tout couple de cases successives mal ordonnées.
Un premier parcours emmène la plus grande valeur jusqu’à la
dernière case du tableau, comme les grosses bulles qui
remontent à la surface de l’eau plus vite que les petites. Un
second parcours fait remonter la deuxième plus grande valeur,
et il suffit d’arrêter la remontée à l’avant-dernière case du
tableau ; et ainsi de suite.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice > i sont triées et
placées.
Les variables du tableau avec un indice ≤ i sont ≤ T [i − 1].
K Musumbu Algorithmique et Programmation
Algorithmes
Algorithme .5 : TriBulle(T)
Données : Un tableau T d’entiers
Résultat : Le tableau T trie par ordre croissant des valeurs
pour i=len(T)-1 à 1 decroissant faire /* Θ(n2 ) */
pour j=0 à i-1 faire /* Θ(i) */
si T[j] >T [j+1] alors /* Θ(1) */
DecalageDroite(T,j,j+1); /* Θ(1) */
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps : Ω(n), O(n2 )
Complexité en espace : Θ(1)
Tri stable : Oui sauf si T [i] ≤ T [j] au lieu de T [i] < T [j]
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps : Ω(n), O(n2 )
Complexité en espace : Θ(1)
Tri stable : Oui sauf si T [i] ≤ T [j] au lieu de T [i] < T [j]
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps : Ω(n), O(n2 )
Complexité en espace : Θ(1)
Tri stable : Oui sauf si T [i] ≤ T [j] au lieu de T [i] < T [j]
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps : Ω(n), O(n2 )
Complexité en espace : Θ(1)
Tri stable : Oui sauf si T [i] ≤ T [j] au lieu de T [i] < T [j]
K Musumbu Algorithmique et Programmation
Tri Bulle : python
from decalages import *
def triBulle(T) :
n = len(T)
for i in range(n-1,0,-1) :
for j in range(i) :
if T[j]>T[j+1] :
decalageDroite(T,j,j+1)
K Musumbu Algorithmique et Programmation
Tri par insertion
Idée et exemple
C’est le tri des joueurs de cartes, qui font glisser une carte
jusqu’à son emplacement dans la partie des cartes déjà
ordonnée.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < i sont triées.
Les variables du tableau avec un indice ≥ i n’ont jamais
été regardées.
K Musumbu Algorithmique et Programmation
Tri par insertion
Idée et exemple
C’est le tri des joueurs de cartes, qui font glisser une carte
jusqu’à son emplacement dans la partie des cartes déjà
ordonnée.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < i sont triées.
Les variables du tableau avec un indice ≥ i n’ont jamais
été regardées.
K Musumbu Algorithmique et Programmation
Tri par insertion
Idée et exemple
C’est le tri des joueurs de cartes, qui font glisser une carte
jusqu’à son emplacement dans la partie des cartes déjà
ordonnée.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < i sont triées.
Les variables du tableau avec un indice ≥ i n’ont jamais
été regardées.
K Musumbu Algorithmique et Programmation
Tri par insertion
Idée et exemple
C’est le tri des joueurs de cartes, qui font glisser une carte
jusqu’à son emplacement dans la partie des cartes déjà
ordonnée.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < i sont triées.
Les variables du tableau avec un indice ≥ i n’ont jamais
été regardées.
K Musumbu Algorithmique et Programmation
Algorithmes
Algorithme .6 : TriInsertion(T)
Données : Un tableau T d’entiers
Résultat : Le tableau T trié par ordre croissant des valeurs
pour i=1 à longueur(T)-1 faire /* Ω(n), O(n2 ) */
j ← i-1;
tant que j ≥ 0 and T[i] < T[j] faire /* Ω(1), O(i) */
j ← j-1;
si j 6= i-1 alors /* Ω(1), O(i − j) */
DecalageDroite(T,j+1,i); /* Θ(i − j) */
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps : Θ(n2 )
Complexité en espace : Θ(1)
Tri stable : Oui sauf si T [j] ≥ T [j + 1] au lieu de
T [j] > T [j + 1]
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps : Θ(n2 )
Complexité en espace : Θ(1)
Tri stable : Oui sauf si T [j] ≥ T [j + 1] au lieu de
T [j] > T [j + 1]
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps : Θ(n2 )
Complexité en espace : Θ(1)
Tri stable : Oui sauf si T [j] ≥ T [j + 1] au lieu de
T [j] > T [j + 1]
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps : Θ(n2 )
Complexité en espace : Θ(1)
Tri stable : Oui sauf si T [j] ≥ T [j + 1] au lieu de
T [j] > T [j + 1]
K Musumbu Algorithmique et Programmation
Tri Insertion : python
from decalages import *
def triInsertion(T) :
n = len(T)
for i in range(1,n) :
j = i-1
while j>=0 and T[i]<T[j] :
j = j-1
decalageDroite(T,j+1,i)
K Musumbu Algorithmique et Programmation
Recherche dans un tableau trié
Remarques
Compromis espace-temps.
Hypothèse non restrictive, l’algorithme est facile à adapter
avec trois paramètres (T, min, max) que l’on appelle
avec (T,min(T),max(T)).
La complexité en espace n’est pas dépendante de la taille
des objets du tableau, mais seulement de leur nombre.
Freq est un tableau de clefs (entiers, réels, . . .), et res est
un tableau d’adresses mémoire.
K Musumbu Algorithmique et Programmation
Recherche dans un tableau trié
Remarques
Compromis espace-temps.
Hypothèse non restrictive, l’algorithme est facile à adapter
avec trois paramètres (T, min, max) que l’on appelle
avec (T,min(T),max(T)).
La complexité en espace n’est pas dépendante de la taille
des objets du tableau, mais seulement de leur nombre.
Freq est un tableau de clefs (entiers, réels, . . .), et res est
un tableau d’adresses mémoire.
K Musumbu Algorithmique et Programmation
Recherche dans un tableau trié
Remarques
Compromis espace-temps.
Hypothèse non restrictive, l’algorithme est facile à adapter
avec trois paramètres (T, min, max) que l’on appelle
avec (T,min(T),max(T)).
La complexité en espace n’est pas dépendante de la taille
des objets du tableau, mais seulement de leur nombre.
Freq est un tableau de clefs (entiers, réels, . . .), et res est
un tableau d’adresses mémoire.
K Musumbu Algorithmique et Programmation
Recherche dans un tableau trié
Remarques
Compromis espace-temps.
Hypothèse non restrictive, l’algorithme est facile à adapter
avec trois paramètres (T, min, max) que l’on appelle
avec (T,min(T),max(T)).
La complexité en espace n’est pas dépendante de la taille
des objets du tableau, mais seulement de leur nombre.
Freq est un tableau de clefs (entiers, réels, . . .), et res est
un tableau d’adresses mémoire.
K Musumbu Algorithmique et Programmation
Recherche dans un tableau trié : python
def rechercheDichotomique(T,X) :
assert(estTrie(T))
# T est trie
# Retourne s’il existe l’indice d’un element egal a X,
# sinon la valeur "None"
g=0
d = len(T)-1
while g<=d :
m = (g+d)//2
if T[m]==X :
return m
elif T[m]<X :
g = m+1
else :
d = m-1
return None
K Musumbu Algorithmique et Programmation
Idée et exemple
Analogies avec la recherche dans un dictionnaire, et avec le jeu
deviner un nombre entre 1 et 1000.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < g sont
inférieures à X .
Les variables du tableau avec un indice > d sont
supérieures à X .
Les variables du tableau avec un indice dans [g, d] n’ont
pas été regardées et sont comprises entre T [g] et T [d].
K Musumbu Algorithmique et Programmation
Idée et exemple
Analogies avec la recherche dans un dictionnaire, et avec le jeu
deviner un nombre entre 1 et 1000.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < g sont
inférieures à X .
Les variables du tableau avec un indice > d sont
supérieures à X .
Les variables du tableau avec un indice dans [g, d] n’ont
pas été regardées et sont comprises entre T [g] et T [d].
K Musumbu Algorithmique et Programmation
Idée et exemple
Analogies avec la recherche dans un dictionnaire, et avec le jeu
deviner un nombre entre 1 et 1000.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < g sont
inférieures à X .
Les variables du tableau avec un indice > d sont
supérieures à X .
Les variables du tableau avec un indice dans [g, d] n’ont
pas été regardées et sont comprises entre T [g] et T [d].
K Musumbu Algorithmique et Programmation
Idée et exemple
Analogies avec la recherche dans un dictionnaire, et avec le jeu
deviner un nombre entre 1 et 1000.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < g sont
inférieures à X .
Les variables du tableau avec un indice > d sont
supérieures à X .
Les variables du tableau avec un indice dans [g, d] n’ont
pas été regardées et sont comprises entre T [g] et T [d].
K Musumbu Algorithmique et Programmation
Idée et exemple
Analogies avec la recherche dans un dictionnaire, et avec le jeu
deviner un nombre entre 1 et 1000.
Arguments de correction
Dans une situation intermédiaire :
Les variables du tableau avec un indice < g sont
inférieures à X .
Les variables du tableau avec un indice > d sont
supérieures à X .
Les variables du tableau avec un indice dans [g, d] n’ont
pas été regardées et sont comprises entre T [g] et T [d].
K Musumbu Algorithmique et Programmation
Algorithme
Algorithme .7 : RechercheDichotomique(T,X)
Données : Un tableau T d’entiers trie, et un entier X
Résultat : Un indice i tel que T[i]=X s’il existe
g ← 0;
d ← longueur(T)-1;
trouve ← faux;
tant que not trouve and g ≤ d faire
m ← (g+d) div 2;
si T[m]=X alors
trouve ← vrai;
sinon si T[m]<X alors
g ← m+1;
sinon
d ← m-1;
si trouve alors
retourner m; K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps :
Meilleur des cas (X = T[(n-1)div 2]) : une seule itération
donc Ω(1)
Pire des cas (X n’est pas dans T) : T (2n) = T (n) + 4 donc
O(log2 (n))
Complexité en espace : Θ(1)
Le premier si présence de doublons : Non
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps :
Meilleur des cas (X = T[(n-1)div 2]) : une seule itération
donc Ω(1)
Pire des cas (X n’est pas dans T) : T (2n) = T (n) + 4 donc
O(log2 (n))
Complexité en espace : Θ(1)
Le premier si présence de doublons : Non
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps :
Meilleur des cas (X = T[(n-1)div 2]) : une seule itération
donc Ω(1)
Pire des cas (X n’est pas dans T) : T (2n) = T (n) + 4 donc
O(log2 (n))
Complexité en espace : Θ(1)
Le premier si présence de doublons : Non
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps :
Meilleur des cas (X = T[(n-1)div 2]) : une seule itération
donc Ω(1)
Pire des cas (X n’est pas dans T) : T (2n) = T (n) + 4 donc
O(log2 (n))
Complexité en espace : Θ(1)
Le premier si présence de doublons : Non
K Musumbu Algorithmique et Programmation
Propriétés
Complexité en temps :
Meilleur des cas (X = T[(n-1)div 2]) : une seule itération
donc Ω(1)
Pire des cas (X n’est pas dans T) : T (2n) = T (n) + 4 donc
O(log2 (n))
Complexité en espace : Θ(1)
Le premier si présence de doublons : Non
K Musumbu Algorithmique et Programmation
Rappels sur les logarithmes
logb (n × m) = logb (n) + logb (m)
loga (n) = loga (b) × logb (n)
K Musumbu Algorithmique et Programmation
Version Python
import random
def estTrie(T) :
for i in range(1,len(T)) :
if T[i]<T[i-1] :
return False
return True
K Musumbu Algorithmique et Programmation
Version Python
def rechercheDichotomique(T,X) :
assert(estTrie(T))
# T est trie
# Retourne s’il existe l’indice d’un element egal a X,
# sinon la valeur "None"
g=0
d = len(T)-1
while g<=d :
m = (g+d)//2
if T[m]==X :
return m
elif T[m]<X :
g = m+1
else :
d = m-1
return None
K Musumbu Algorithmique et Programmation