Ecole
Polytechnique
INF411
Les bases de la programmation
et de lalgorithmique
Jean-Christophe Filliatre
Bloc 6 / lundi 3 octobre 2016
motivation
quels sont les dix mots les plus frequents dans
Le tour du monde en quatre-vingts jours ?
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
une solution en une ligne
on peut le faire avec le shell, en une ligne !
cat file | tr -cs [:alpha:] [\n*] | sort | uniq -c | sort -rn
2826
1616
1587
1472
1112
952
832
788
766
670
...
de
le
la
et
il
les
un
en
du
Fogg
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
explication
on envoie le fichier sur la sortie standard
cat ltdme80j.txt
on remplace les caract`eres non-alphabetiques par un retour-charriot
| tr -cs [:alpha:] [\n*]
on trie les lignes par ordre alphabetique
| sort
on regroupe les lignes identiques, en les comptant (-c)
| uniq -c
on trie numeriquement (-n), en ordre inverse (-r)
| sort -rn
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
tri
on a utilise ici deux tris
un tri par ordre alphab
etique (de 76 420 lignes)
un tri num
erique (de 8 608 lignes)
lobjet de lamphi daujourdhui est justement le tri
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
melanger
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
melanger
comment melanger N valeurs correctement ?
par exemple les N elements dun tableau
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
le melange de Knuth (Knuth shuffle)
chaque element i est echange avec un element j [0, i]
static<E> void shuffle(E[] a) {
for (int i = 1; i < a.length; i++) {
int j = (int)(Math.random() * (i + 1)); // j dans 0..i
swap(a, i, j);
}
}
0
1
1
1
1
1
Jean-Christophe Filli
atre
1
0
0
3
3
3
2
2
2
2
2
2
3
3
3
0
0
5
4
4
4
4
4
4
INF411
5
5
5
5
5
0
j=0
j=2
j=1
j=4
j=3
X2015 / bloc 6
bon melange
for (int i = 1; i < a.length; i++) {
int j = (int)(Math.random() * (i + 1)); // j dans 0..i
swap(a, i, j);
}
avant
x0
x1
x2
...
xn1
apr`es
y0
y1
y2
...
yn1
montrons que la probabilite que yk = xl apr`es letape i vaut
Pi (yk = xl ) =
1
i +1
pour 0 k, l i
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
preuve
par recurrence sur i
clair pour i = 0
supposons le r
esultat pour i 1
avant
x0
x1
...
xi1
xi
apr`es
y0
y1
...
yi1
yi
pour k = i
Pi (yi = xi ) =
l < i,
Pi (yi = xl ) =
1
i +1
X
0j<i
X
0j<i
Jean-Christophe Filli
atre
(pas dechange)
1
Pi1 (yj = xl )
i +1
1
1
i +1
i
1
i +1
INF411
X2015 / bloc 6
10
preuve
par recurrence sur i
clair pour i = 0
supposons le r
esultat pour i 1
avant
x0
x1
...
xi1
xi
apr`es
y0
y1
...
yi1
yi
pour k < i
Pi (yk = xi ) =
l < i,
Pi (yk = xl ) =
=
=
1
(echange)
i +1
i
Pi1 (yk = xl )
i +1
1
i
i +1
i
1
i +1
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
11
le melange de Knuth
est facile `
a ecrire
de complexit
e O(N)
donne chacune des N! permutations avec la m
eme probabilite
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
12
complexite du probl`eme du tri
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
13
optimalite
`a quelle vitesse peut-on esperer trier ?
dit autrement : quelle est la meilleure complexite dans le pire des cas ?
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
14
hypoth`ese
on suppose que lalgorithme
ne proc`
ede que par comparaisons entre elements
ne poss`
ede aucune information quant `a la distribution
le co
ut sera justement le nombre de comparaisons effectuees
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
15
exemple
on peut trier trois valeurs a, b, c ainsi
a < b?
b<c?
abc
b<c?
a<c?
acb
cab
a<c?
bac
cba
bca
(un tel arbre, appele questionnaire, represente lalgorithme)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
16
cout
ici, on fait 2 ou 3 comparaisons selon lentree
donc 3 comparaisons dans le pire des cas
on se persuade facilement que cest optimal pour N = 3 :
on ne peut trier trois valeurs avec au plus deux comparaisons
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
17
de mani`ere generale
un algorithme qui trie N valeurs peut etre vu comme un arbre binaire
o`
u chaque nud est un test et chaque feuille une permutation
il y a au moins N! feuilles
la complexit
e dans le pire des cas est la hauteur de cet arbre
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
18
minoration
N! nombre de feuilles 2hauteur
donc
hauteur log2 (N!) =
log2 (i) N log2 (N)
1iN
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
19
complexite du probl`eme du tri
aucun algorithme, procedant par comparaisons uniquement,
ne peut trier N valeurs en effectuant toujours moins que
N log N
comparaisons
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
20
en particulier
le tri par tas, vu la semaine derni`ere, est optimal
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
21
cas particuliers
bien entendu, on peut faire mieux quand on poss`ede une information
supplementaire sur les elements
exemple : si les N elements ne prennent que deux valeurs distinctes,
alors on peut trier en O(N)
(cf exercices 82, 83 et 84 du poly)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
22
tri par insertion
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
23
tri par insertion
le plus naturel : on ins`ere successivement chaque nouvel element
parmi les elements dej`a tries
0
i-1 i
. . . dej`a trie . . . v
Jean-Christophe Filli
atre
INF411
. . . `a trier . . .
X2015 / bloc 6
24
code
static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int v = a[i], j = i;
// on d
ecale les
el
ements vers la droite
for (; 0 < j && v < a[j-1]; j--) a[j] = a[j-1];
// jusqu`
a avoir trouv
e la place j de v
a[j] = v;
}
}
v
j
Jean-Christophe Filli
atre
. . . `a trier . . .
INF411
X2015 / bloc 6
25
questionnaire pour N = 4
a
a < b?
b<c?
a<c?
c <d?
abcd
a<c?
b<d?
abdc
b<d?
a<d?
adbc
acbd
dabc
b<d?
c <d?
acdb
c <d?
cabd
a<d?
adcb
dacb
bacd
a<d?
cadb
a<d?
badc
c <d?
cdab
b<c?
dcab
a<d?
b<d?
bdac
dbac
bcad
a<d?
c <d?
bcda
cbad
cbda
b<d?
bdca
b<d?
dbca
c <d?
cdba
dcba
(hauteur 6 > dlog(24)e)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
26
complexite
dans le pire des cas, linsertion de a[i] demande i comparaisons (tableau
trie en ordre inverse), do`
u un total
1 + 2 + + N 1
N2
2
dans le meilleur des cas, linsertion de a[i] demande une seule
comparaison (le tableau est dej`a trie), do`
u un total
N
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
27
complexite
comparaisons
affectations
meilleur cas
N
N
moyenne
N 2 /4
N 2 /4
pire cas
N 2 /2
N 2 /2
+ lineaire sur un tableau dej`a trie
quadratique dans le pire des cas
N = 105 plusieurs milliards doperations
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
28
tri fusion
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
29
diviser pour regner
1. couper le tableau en deux moities egales
2. les trier recursivement
3. fusionner les resultats
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
30
tri fusion (mergesort)
il faut generaliser au tri de a[l..r[
1. couper le tableau en deux moities egales m = b l+r
2 c
l
a
2. trier recursivement a[l..m[ et a[m..r[
l
m
a
trie
trie
3. fusionner les resultats
l
r
trie
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
31
exemple
2 5 3 8 5 1 4
2 5 3
8 5 1 4
5 3
2
3
3 5
2 3 5
8 5
8
1 4
5
5 8
1 4
1 4 5 8
1 2 3 4 5 5 8
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
32
difficulte
il est extremement difficile de realiser la fusion en place
on va utiliser un second tableau
static void mergesort(int[] a) {
mergesortrec(a, new int[a.length], 0, a.length);
}
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
33
code
trier a[l..r[ en utilisant le tableau auxiliaire tmp
static void mergesortrec(int[] a, int[] tmp, int l, int r){
if (l >= r-1) return; // au plus un
el
ement
int m = l + (r - l) / 2;
mergesortrec(a, tmp, l, m);
mergesortrec(a, tmp, m, r);
for (int i = l; i < r; i++) tmp[i] = a[i];
merge(tmp, a, l, m, r);
}
(note : (l + r) / 2 pourrait provoquer un debordement arithmetique)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
34
fusion
fusionne a1[l..m[ et a1[m..r[ dans a2[l..r[
static void merge(int[] a1, int[] a2, int l, int m, int r){
int i = l, j = m;
for (int k = l; k < r; k++)
if (i < m && (j == r || a1[i] <= a1[j]))
a2[k] = a1[i++];
else
a2[k] = a1[j++];
}
l
a1
a2
m
trie
i
r
trie
j
trie
k
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
35
questionnaire pour N = 4
a < b?
c <d?
c <d?
a<c?
a<d?
b<c?
abcd
a<d?
b<d?
acbd
acdb
b<d?
cabd
cdab
cadb
b<c?
b<d?
abdc
a<c?
b<c?
adbc
adcb
b<c?
dabc
b<d?
a<c?
dcab
bacd
dacb
b<d?
a<d?
bcad
bcda
a<d?
cbad
cbda
cdba
a<d?
badc
b<c?
a<c?
bdac
bdca
a<c?
dbac
dcba
dbca
(hauteur 5 = dlog(24)e)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
36
complexite
soit CN le nombre de comparaisons pour trier N elements
on a
C0 = C1 = 0
C =C N +C N +f
N
N
b c
d e
2
o`
u fN est le co
ut de la fusion
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
37
complexite
supposons le pire des cas (fN = N) et N = 2n pour simplifier les calculs
il vient
C2n
= C2n1 + C2n1 + 2n
C2n
2n
C2n1
+1
2n1
C2n2
+1+1
2n2
= n
cest-`a-dire
CN = N log2 (N)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
38
complexite
comparaisons
affectations
meilleur cas
1
2 N log N
2N log N
moyenne
N log N
2N log N
pire cas
N log N
2N log N
+ complexite optimale
espace supplementaire O(N)
+ sapplique facilement aux listes, en place
(cf TD de cette semaine)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
39
taille de pile
les appels recursifs imbriques occupent de lespace sur la pile (cf amphi 1)
mais cet espace est en O(log N),
car |r l| est divise par deux `a chaque fois
donc on ne provoquera pas StackOverflowError
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
40
optimisations
quand r l devient tr`
es petit, faire un tri par insertion
pas besoin de fusionner si a[m-1] a[m]
(devient alors lineaire sur un tableau dej`a trie)
pour
eviter la copie dans tmp,
echanger le role des deux tableaux `a chaque fois
(cf exercice 79 du poly)
on peut sarr
eter d`es que le segment est dej`a trie (natural mergesort)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
41
variantes
on a procede de haut en bas (top-down mergesort)
on peut aussi proceder de bas en haut (bottom-up mergesort)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
42
tri rapide
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
43
question
comment eviter lespace auxiliaire
tout en conservant le principe diviser pour regner ?
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
44
tri rapide (quicksort)
on conserve lidee de trier a[l..r[
1. r
earranger les elements pour avoir
l
a
<p
r
p
pour une certaine valeur p appelee pivot
2. trier r
ecursivement a[l..m[ et a[m..r[
l
m
a
trie
trie
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
45
exemple
2 5 3 8 5 1 4
1 2 5 3 8 5 4
5 3 8 5 4
3 4 5 8 5
3 4
3 4
4
Jean-Christophe Filli
atre
INF411
8 5
5 8
5
X2015 / bloc 6
46
code
static void quicksort(int[] a) {
quickrec(a, 0, a.length);
}
static void quickrec(int[] a, int l, int r) {
if (l >= r-1) return; // au plus un
el
ement
int m = partition(a, l, r);
quickrec(a, l,
m);
l
m
quickrec(a, m + 1, r);
<p
p
}
r
p
il ne reste plus qu`a ecrire partition
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
47
partition
on choisit arbitrairement a[l] comme pivot
l
p
i
p
<p
r
?
static int partition(int[] a, int l, int r) {
int p = a[l], m = l;
for (int i = l + 1; i < r; i++)
if (a[i] < p)
swap(a, i, ++m);
swap(a, l, m);
return m;
}
l
<p
Jean-Christophe Filli
atre
m
p
INF411
r
p
X2015 / bloc 6
48
complexite
soit CN le nombre de comparaisons pour trier N elements
C0 = C1 = 0
CN = N
1} + CK + CN1K
| {z
|{z}
| {z }
partition
`
a gauche
`
a droite
pour un tableau dej`a trie, K = 0
CN = N 1 + CN1
Jean-Christophe Filli
atre
INF411
N2
2
X2015 / bloc 6
49
complexite
en moyenne, cependant, cest optimal (preuve dans le poly)
comparaisons
affectations
meilleur cas
N log N
0
moyenne
2N log N
2N log N
pire cas
N 2 /2
N2
meilleur cas comparaisons = pivot au milieu
meilleur cas affectations = pivot `a gauche = pire cas comparaisons
+ en place
pire cas O(N 2 )
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
50
eviter le pire cas
le pire cas correspond `a un pivot au bord
idee : prendre comme pivot un element de a[l..r[ au hasard
encore plus simple : m
elanger avant de trier !
static void quicksort(int[] a) {
KnuthShuffle.shuffle(a);
quickrec(a, 0, a.length);
}
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
51
eviter le pire cas
ne suffit cependant pas si beaucoup delements egaux
(tous les elements egaux pivot forcement au bord)
solution : partitionner en trois (3-way partition)
l
m
<p
{z
puis trier
n
=p
r
>p
{z
puis trier
(cf exercices 76 et 83 dans le poly)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
52
taille de pile
comme pour le tri fusion,
les appels recursifs imbriques occupent de lespace sur la pile
mais ici cet espace peut etre en O(N)
(on ne decoupe plus systematiquement en deux moities egales)
provoque alors StackOverflowError !
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
53
solution
on peut
faire un appel r
ecursif sur la plus petite des deux moities
remplacer lautre appel r
ecursif par une boucle while
on retrouve alors une taille de pile en O(log N)
(cf exercice 77 du poly)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
54
autre optimisation
quand r l devient tr`
es petit, faire un tri par insertion
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
55
tri par tas
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
56
tri par tas (cf amphi 5)
static void moveDown(int[] a, int i, int x, int n) {
while (true) {
int j = 2 * i + 1;
if (j >= n) break;
if (j + 1 < n && a[j] < a[j + 1]) j++;
if (a[j] <= x) break;
a[i] = a[j]; i = j;
}
a 8 3 7 1 2 4 3
a[i] = x;
8
}
static void heapsort(int[] a) {
3
7
int n = a.length;
for (int k = n / 2 - 1; k >= 0; k--)
moveDown(a, k, a[k], n);
1
2
4
3
for (int k = n - 1; k >= 1; k--) {
int v = a[k]; a[k] = a[0];
moveDown(a, 0, v, k);
}
}
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
57
complexite
le tri par tas est en O(N log N) dans le pire des cas
(cf amphi 5)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
58
pourquoi tous ces tris ?
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
59
pourquoi tous ces tris ?
ils ont chacun des avantages et des inconvenients
en place ou non
efficace sur un tableau (presque) d
ej`a trie
optimal dans le pire des cas
stable
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
60
stabilite
Definition
Un tri est stable sil preserve lordre dapparition des elements egaux.
non significatif pour des elements de type int
mais de mani`ere generale on trie des objets dun type E quelconque
class Sort<E extends Comparable<E>> { ... }
static<E extends Comparable<E>> void sort(E[] a) { ... }
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
61
exemple
un ensemble de films est donne par ordre chronologique
on trie selon la note moyenne des commentaires, avec un tri stable
r
esultat : `a note egale, les films restent tries par ordre chronologique
(cest une facon dobtenir un ordre lexicographique)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
62
comparaison
insertion
fusion
rapide
par tas
moyenne
O(N 2 )
O(N log N)
O(N log N)
O(N log N)
pire cas
O(N 2 )
O(N log N)
O(N 2 )
O(N log N)
dej`a trie
O(N)
O(N)
O(N 2 )
O(N log N)
en place
oui
non
oui
oui
stable
oui
oui
non
non
et les constantes cachees dans les O peuvent faire une difference
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
63
la biblioth`eque Java
fournit un grand nombre de methodes Arrays.sort(...)
tri rapide pour les types primitifs
void sort( char[] a);
void sort(
int[] a);
void sort(double[] a);
...
tri fusion pour les objets
void sort(T[] a); // si T impl
emente Comparable<T>
void sort(T[] a, Comparator<T> c);
garanti stable
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
64
applications
le tri ne sert pas qu`a organiser des donnees
cest aussi un ingredient de base de nombreux algorithmes
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
65
exemple : calcul de lenveloppe convexe
entree = N points dans le plan
sortie = points formant lenveloppe convexe
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
66
algorithme de Graham
1 determiner le point p le plus bas
2 trier tous les points selon langle fait avec p
3 considerer les points dans cet ordre,
en les ajoutant/retirant de lenveloppe convexe
d
emo
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
67
complexite
letape 1 est clairement en O(N)
letape 2 est en O(N log N) (tri de N valeurs)
letape 3 est O(N), car chaque point est ajoute une fois dans lenveloppe,
retire au plus une fois de lenveloppe
cest donc une solution en O(N log N)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
68
optimalite
on ne peut pas faire mieux
en effet, soient N entiers x1 , . . . , xN
trouver lenveloppe convexe des N points (xi , xi2 ) revient `a les trier
et on a vu que le tri ne peut etre fait en moins de N log N
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
69
lecon
quand on programme, il faut faire des petits dessins !
l
p
Jean-Christophe Filli
atre
m
<p
i
p
INF411
r
?
X2015 / bloc 6
70
le TD de cette semaine
le tri fusion de listes, en place
application : une autre facon de trouver les mots les plus frequents
Le tour du monde
`a `a `a `a
`a(1678) ah(4) bien(13)
de(2826) `a(1678) le(1616) la(1499)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
71
la semaine prochaine
lire le poly, chapitre 13. Tri
il y a des exercices dans le poly
bloc 7 : graphes (1/2)
Jean-Christophe Filli
atre
INF411
X2015 / bloc 6
72
