TP : les tris
Article mis en ligne le 11 janvier 2017 par C GIBERT
Imprimer cet article logo imprimer

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 la vidéo dont le lien est indiqué ci-dessous pour comprendre le principe de la méthode :

http://vimeo.com/38609513

2. Concevez un algorithme qui met en œuvre cette méthode.

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://vimeo.com/38610344

2. Reprenez les mêmes questions que pour le tri par sélection.

Partie D — Le tri à bulles

Le tri par remontée de bulles consiste à passer les éléments de la liste en revue plusieurs fois, comparer les éléments adjacents, et à les échanger s’ils ne sont pas dans l’ordre croissant. Lorsque l‘on réalise un passage, on range le plus petit élément en début de liste (les bulles les plus légères remontent en début de liste). La liste est classée lorsqu’il n’ya plus d’éléments à changer de place.

1) Trier la liste suivante avec le tri à bulles : [61, 1, 25, 33, 70, 20, 34, 19, 68, 79, 64, 24] Combien de d’échanges a-t-on effectué ?

2) Trier la liste suivante avec le tri à bulles : [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 1] Combien fait-on d’échanges ?

3) Implémenter un programme en Python qui permet de trier dans l’ordre croissant une liste d’entiers par remontée des bulles.

Partie E — 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.

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 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 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.

Dans la même rubrique :

Identification

Calendrier

avril 2019
lunmarmerjeuvensamdim
1234567
891011121314
15161718192021
22232425262728
293012345
Évènements à venir
Pas d'évènements à venir

Articles les plus vus

Statistiques du site

  • Nombre total de visites :
    213511 visiteurs
  • Aujourd'hui :
    41 visiteurs
  • Nombre de pages visitées :
    296330 pages
  • Actuellement en ligne :
    3 visiteurs
  • Ce site contient :
    204 articles
  • Dernier article paru :
    "Cross Solidaire 2019"
    le 9 avril 2019
puce Contact puce Espace rédacteurs puce squelette puce RSS puce Valid XHTML 1.0 Strict
Site réalisé sous SPIP
avec le squelette ESCAL-V2
Version : 2.6.7 [61555]