Bloc-notes
Math Lycée
Info Lycée
Menu contextuel
Trier, la routine pour une machine (Fiche élève)
[UNB480]

Partie A — Introduction

Lorsque l'on a un peu d'expérience dans la programmation on constate vite qu'un certain nombre de problèmes élémentaires se posent très souvent. L'un se ces problèmes récurrents est celui qui consiste à trier un tableau de valeurs. Comme ce type de problème revient très souvent des méthodes de tri efficaces ont été recherchées et découvertes. Ces méthodes sont bien entendues aujourd'hui disponibles dans les bibliothèques de tous les langages de programmation mais l'objectif de l'activité est de tenter d'en redécouvrir certaines et de les mettre en œuvre dans notre langage Python.

Le problème est donc le suivant :

On dispose d'un tableau numpy appelé table. Ce tableau possède $N$ cases numérotées de 0 à $N-1$. Les cases ont été remplies par des nombres entre 0 et $MAX$ de façon aléatoire.

Il s'agit d'écrire une fonction Python qui prend le tableau en argument et qui trie les nombres dans l'ordre croissant. 

table = np.random.random_integers(0, MAX, N)  # Crée le tableau
tri(table)    # Tri le tableau
print table   # Affiche le tableau trié

Pour que l'énoncé du problème soit complet, il est nécessaire de préciser les instructions élémentaires à notre disposition pour écrire la fonction tri. Si on dispose par exemple de la fonction sort de la bibliothèque numpy le problème devient en effet extrêmement simple. Mais nous n'apprendrons rien.

Les instructions élémentaires disponibles sont :
  • comparer deux cases du tableau ;
  • échanger deux cases du tableau.

La deuxième action est particulièrement facile à écrire en Python :

table[i], table[j] = table[j], table[i] échange le contenu des cases i et j.

Il s'agit donc de trouver une méthode de tri. Pour cela on peut oublier momentanément l'aspect programmation. Pensez plutôt à un jeu de cartes à jouer. Le valeur d'une carte dépend de sa hauteur (as, roi, dame, etc). Si deux cartes ont la même hauteur on considère que les valeurs les plus fortes sont dans l'ordre pique, cœur, carreau, trèfle.

Réfléchissez cinq minutes à une méthode de tri suffisamment systématique pour pouvoir être traduite dans un programme.

Partie B — Le tri par sélection

L'une des méthodes classiques pour trier un tableau est le tri par sélection.

1.
Observez l'applet dont le lien est indiqué ci-dessous pour comprendre le principe de la méthode :

http://math.hws.edu/TMCM/java/xSortLab/
2.
(a)
Concevez un algorithme (écrit en pseudo-code) qui met en œuvre cette méthode.
(b)
Faites valider votre algorithme par le professeur puis traduisez votre algorithme en Python.
(c)
Montrez votre programme au professeur puis allez sur une machine pour coder et mettre au point votre programme.
3.
(a)
Évaluez la rapidité de votre programme. Pour cela utilisez la bibliothèque time qui permet de mesurer des temps : time.time() renvoie le nombre de secondes écoulées depuis le 1er janvier 1970 (au centième de seconde près).

Testez votre programme en doublant à chaque fois la taille $N$. Relevez à chaque fois le temps d'exécution et placez les résultats dans un tableau.
(b)
Étudiez les valeurs du tableau. Selon quelle progression évoluent les temps d'exécution.
(c)
Combien de temps prendrait le tri d'un tableau d'un million de valeurs ?

Partie C — Le tri par insertion

Une autre des méthodes classiques pour trier un tableau est le tri par insertion.

1.
Observez la vidéo dont le lien est indiquez ci-dessous pour comprendre le principe de la méthode :

http://www.youtube.com/watch?v=ROalU379l3U
2.
Reprenez les mêmes questions que pour le tri par sélection.

Partie D — Le tri fusion

Les méthodes précédentes trouvent leur limite lorsque la taille du tableau est grande. Le tri fusion est une méthode qui s'avère beaucoup plus efficace pour des grands tableaux. Elle repose sur un principe très général de l'algorithmique qui se nomme diviser pour régner. Le principe consiste à remplacer le problème par deux problèmes similaires mais plus petits. Il est alors fréquent que la résolution des deux problèmes plus petits prennent beaucoup moins de temps à résoudre que le seul gros problème de départ. Bien sûr il faudra aussi un peu de temps pour fabriquer la solution du gros problème à partir des solutions des deux petits problèmes.

1.
Nous allons illustrer la méthode en triant par fusion un jeu de 32 cartes :
  • L'élève n° 1 partage le jeu de cartes en deux tas égaux et donne l'un des tas à l'élève n° 2 et l'autre à l'élève n° 3.
  • Les élèves n° 2 et n° 3 font de même. Le premier donne ses tas aux élèves n° 4 et n° 5, le second aux élèves n° 6 et n° 7.
  • Les élèves qui viennent de recevoir les cartes font encore de même et donnent leurs tas (4 cartes) aux élèves restants (n° 8 à n°  15).
  • Les élèves qui viennent de recevoir 4 cartes trient maintenant ces cartes par ordre décroissant (as au dessus du roi, etc). En cas de hauteur identique appliquez la rèlge pique au-dessus de cœur, au-dessus de carreau, au-dessus de trèfle).

    Chacun rend ensuite son tas à l'élève qui le lui a donné.
  • Les élèves qui viennent de récupérer leur deux tas doivent maintenant rassembler ces deux tas en un seul bien ordonné. C'est l'étape de fusion des deux tas.

    Chacun rend ensuite son tas à l'élève qui le lui a donné.
  • Les élèves n° 2 et n° 3 fusionnent à leur tour leurs deux tas et rendent le tas ordonné à l'élève n°  1.
  • L'élève n° 1 termine le travail en fusionnant les deux tas.
Organisez-vous entre vous pour expérimenter la méthode décrite ci-dessus. Répétez plusieurs fois l'expérience afin de bien comprendre le principe.
2.
Pour mettre en œuvre le tri fusion dans un programme l'une des tâches à réaliser est de fusionner deux tableaux ordonnés en un seul tableau ordonné.
(a)
Proposez une fonction fusion (écrite en pseudo-code) qui à partir de deux tableaux ordonnés, l'un nommé gauche de taille $G$ et l'autre nommé droite de taille $D$ crée un nouveau tableau ordonné de taille $G+D$.
(b)
Proposez une fonction récursive tri-fusion (écrite en pseudo-code) qui trie un tableau table passé en argument. Cette fonction utilisera en particulier la fonction fusion ci-dessus.
(c)
Codez et mettez au point votre programme.
(d)
Comparez les temps d'exécution avec ceux des tris par sélection ou par insertion.


Denis Pinsard -- Mis à jour le samedi 16 février 2013

Infos site
Ecrire à Denis Pinsard  Contact
Ajouter aux favoris  Favoris
Visites

 0 visiteurs

 1 visiteur en ligne

Calendrier
^ Haut ^