Bloc-notes
Math Lycée
Info Lycée
Menu contextuel
|
Trier, la routine pour une machine (Fiche élève)
Partie A — IntroductionLorsque 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é
Partie B — Le tri par sélectionL'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 insertionUne 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 fusionLes 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 :
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 |