TD4

Tri bitonique

Combinez deux comparateurs pour fabriquer un séparateur bitonique pour 4 éléments
Construisez maintenant un séparateur pour 8 éléments
Rappelez le principe du tri bitonique
Faites fonctionner le tri bitonique sur le tableau [5, 3, 6, 1, 0, 2, 7, 9]
Combien de comparateurs faut-il pour construire un séparateur bitonique pour une liste de n éléments
Montrez que la partie fusion ne nécessite pas de comparateurs mais peut être implémentée avec ceux utilisés lors des étapes précédentes
On appelle étage le couple tri/fusion utilisé dans le tri bitonique. Combien d'étages sont-ils nécessaires pour trier une séquence de n éléments?
Quelle est la taille des données traitées par chacun des tri à l'étage i?
En déduire que la complexité en temps du tri bitonique est O(log2(n)^2).