UdMHaut
UdMBAS

IFT1020
Programmation II

Département d'informatique et de recherche opérationnelle

Direction de l'enseignement de service en informatique
 

Image Java
 
Été 2005

Accueil

Professeurs et
Démonstrateurs

Horaires et locaux

Notes de cours

Cours
après Cours

Démonstrations
et devoirs

Examens

Liens utiles

Au sujet du
livre de cours

Consultez vos notes

Foire aux questions
(FAQ)

Sessions antérieures

  Démonstration #11  
 
Dernière mise à jour : lun 06 jun 2005 22:26:09 EDT
 

Buts:

  • Algorithmiques

Exercice 1 (Solution)

Programmer un des tris les plus populaires, implanté dans la plupart des langages: le quick sort. Cet algorithme de tri efficace se décompose en deux étapes:
  • le partionnement: qui consiste à organiser le tableau à trier selon une valeur pivot (le premier élément du tableau à trier). Le pivot doit à la suite de cette opération se trouver à sa place finale avec à sa gauche des éléments (pas nécessairement triés) inférieurs et à sa droite des éléments (pas nécessairement triés) supérieurs.
  • la récursion: l'étape précédente fait apparaître deux tableaux: celui à droite de la valeur pivot et celui à gauche. Lancer le partitionnement de ces deux tableaux.
On voit clairement la récursion inhérente à cette définition: programmez là ! Vous définirez pour cela une méthode à trois arguments: une référence sur le tableau à trier, l'indice de l'élément où doit commencer le tri, et l'indice du dernier élément à trier.

Note: pour placer le premier élément du tableau T à sa place finale, appliquez l'algorithme suivant où d et f désignent respectivement l'indice de début et de fin de tableau et T[i] le i-ème élément de T:

  1. tant que T[f] est supérieur à T[d], décrémenter f de 1.
  2. permuter (s'il y a lieu) T[f] avec T[d]
  3. incrémenter d de 1.
  4. tant que T[d] est inférieur à T[f], incrémenter d.
  5. permuter (s'il y a lieu) T[d] avec T[f]
  6. décrémenter f
  7. aller en 1

Inspirez-vous de l'exemple suivant où le nombre en gras représente le pivot et celui en italique la valeur à permuter.

3726489810126845
1226489810376845
1226437810896845
1226410837896845

Exercice 2

Comparez les performances du quicksort et du tri à bulles pour trier des tableaux de différente taille (100, 1000, 10000 éléments) initialisés avec des entiers entre 0 et 1000. Faites le tests dans les deux situations suivantes:
  • un tableau dont les valeurs ont été remplies aléatoirement par des entiers entre 0 et 1000
  • un tableau presque trié (pour obtenir un tableau presque trié, triez d'abord ce tableau puis permutez quelques éléments



dift1020@iro.umontreal.ca
[top]