Fenoll
Loïse
Parallélisme
et
Répartition
TD4
Exercice
3
:
Tri
bitonique
1. Combinez
deux
comparateurs
pour
trier
une
séquence
bitonique
de
4
éléments
Voici
2
exemples,
l’un
avec
une
séquence
croissante
–
décroissante,
et
l’autre
décroissante
–
croissante
:
Le
premier
croissant
-‐
décroissant
3
1
𝐶!
1
3
2
𝐶!
2
2
3
𝐶!
4
4
Le
second
décroissant
-‐
croissant
1
1
1
𝐶!
𝐶!
4
4
2
2
𝐶!
3
2
4
3
𝐶!
𝐶!
2
3
4
2. Faites
fonctionner
le
tri
bitonique
sur
le
tableau
[5,
3,
6,
1,
0,
2,
7,
9]
5
Fusion
=
(5,3)
Tri
(3,5)
3
Fusion
=
(3,5,6
,1)
(1,3,5,6
)
6
Tri
(6,1)
Fusion
=
(6,1)
Tri
1
Fusion
=
(1,3,5,6,9,7,2,0)
0
(0,2)
Tri
Fusion
=
(0,2)
2
(9,7,2,0)
Fusion
=
( 0,2,9,7)
Tri
7
Fusion
=
(
7,9)
Tri
(9,7)
9
On
a
donc
un
tri
bitonique
de
type
croissant
-‐
décroissant
Fenoll
Loïse
3. Combien
de
comparateurs
faut-‐il
pour
trier
une
séquence
bitonique
de
𝑛
éléments
?
!
Pour
une
séquence
de
𝑛 éléments,
il
faut
!
comparateur
simultané
4. Montrez
que
la
partie
fusion
ne
nécessite
pas
de
comparateurs
mais
peut
être
implémentée
avec
ceux
utilisés
lors
des
étapes
de
tri
précédentes.
On
a
vu
dans
la
question
1
qu’il
n’est
pas
necessaire
de
fusionner
pour
obtenir
un
tri
bitonique,
il
suffit
de
trier
la
première
moitié
de
façon
croissante,
et
la
deuxième
de
façon
décroissante.
5. On
appelle
étage
le
couple
tri/fusion
utilisé
dans
le
tri
bitonique.
Combien
d’étage
sont-‐ils
nécessaires
pour
trier
une
séquence
de
𝑛
données
?
Il
y
a
log(𝑛)
étage
pour
trier
une
séquence
de
𝑛
données
6. Quelle
est
la
taille
des
données
traitées
par
chacun
des
tris
à
l’étage
𝑖
?
On
a
un
travail
en
𝑂(𝑛 log 𝑛),
en
effet
pour
chaque
étage
on
traite
𝑛
données
7. En
déduire
que
la
complexité
en
temps
du
tri
bitonique
est
𝑂(log ! (𝑛))
On
a
log(𝑛)
étape
qui
coutent
chacune
log(𝑛)
ainsi
on
a
log(𝑛) ∗ log(𝑛)
=
log ! (𝑛)
