Algorithmique II

3. Algorithmes de tri [complément]

Solutions des exercices

Exercice 1

Voir partie Apprendre.

Exercice 2

Voir partie Apprendre.

Exercice 3

Voir partie Apprendre.

Exercice 4

Voir partie Apprendre.

Exercice 5 – Une question à un million

Si une instruction prend 10-6 secondes, combien de temps faut-il pour trier un tableau d’un million d’éléments avec le tri à sélection comparé au tri rapide (sans tenir compte de la constante) ?

Solution 5 – Une question à un million

Cliquer ici pour voir la réponse

Pour trier 1 million d’éléments, le tri par sélection prend 106*106 *10-6 secondes ou 1 million de secondes (équivalent à plus de 11 jours), alors que le tri rapide a besoin de log2(106)*106 *10-6 ou ~20 secondes.

Cette différence de temps est suffisante pour rendre rédhibitoire l’utilisation du tri par sélection. Pensez au nombre de clients qu’un réseau social possède, ou au nombre de produits qu’un supermarché doit gérer.

Exercice 6 – Une question de pivot

Trier le tableau suivant avec l’algorithme de tri rapide : [3, 6, 8, 7, 1, 9, 4, 2, 5] à la main, en prenant le dernier élément comme pivot. Représenter l’état du tableau lors de toutes les étapes intermédiaires.

Est-ce que le choix du pivot est important ?

Solution 6 – Une question de pivot

Cliquer ici pour voir la réponse

Lors de la première étape du tri rapide, l’élément pivot est 5. On se retrouve donc avec les deux tableaux suivants :

     [[3, 1, 4, 2], 5, [6, 8, 7, 9]]

Les nouveaux éléments pivots sont les derniers éléments des nouveaux tableaux de gauche [3, 1, 4, 2] et le tableau de droite [6, 8, 7, 9] , donc 2 et 9. On réarrange tous les éléments des tableaux autour des éléments pivots, selon leur taille :

     [[1], 2, [3, 4], 5, [6, 8, 7], 9 [ ]]

On continue les mêmes opérations pour les tableaux qui contiennent plus d’un élément : [3, 4] et [6, 8, 7]. Les nouveaux pivots sont 4 et 7, car ils sont les derniers éléments des tableaux restants à plus d’un élément :

     [1, 2, [3], 4, [ ], 5, [6], 7, [8], 9]

Il ne reste plus de tableaux de plus d’un élément, le tableau est donc trié :

     [1, 2, 3, 4, 5, 6, 7, 8, 9]

Le choix du pivot est important et à prendre en compte si on a des indications sur le tableau à trier.

Exercice 7 – Une question de sélection

Trier le tableau suivant avec l’algorithme de tri par sélection : [3, 6, 8, 7, 1, 9, 4, 2, 5] à la main. Représenter l’état du tableau lors de toutes les étapes intermédiaires.

Solution 7 – Une question de sélection

Cliquer ici pour voir la réponse

Lors de la première étape du tri par insertion, on cherche à trouver la bonne position du 2e élément, dans ce cas l’élément 6 reste au même emplacement, car 3 est plus petit que 6 :

     [3, 6, 8, 7, 1, 9, 4, 2, 5]

Le prochain élément considéré est le 8. Cet élément est également déjà bien placé :

         [3, 6, 8, 7, 1, 9, 4, 2, 5]

Comme l’ordre des éléments ne change pas, nous notons cette configuration à droite.

Le prochain élément considéré est le 7. Cet élément n’est pas bien placé au regard du tableau que l’on a déjà trié. Sa place est avant le 8, on va donc l’insérer entre le 6 et le 8 :

         [3, 6, 8, 7, 1, 9, 4, 2, 5]

     [3, 6, 7, 8, 1, 9, 4, 2, 5]

Le prochain élément de la liste non triée est le 1 :

     [3, 6, 7, 8, 1, 9, 4, 2, 5]

Nous allons l’insérer à la bonne position du tableau déjà trié, c’est-à-dire tout au début :

     [1, 3, 6, 7, 8, 9, 4, 2, 5]

Tous les éléments qui ont changé de position dans l’étape précédente sont désignés en rouge. Le prochain élément à considérer est le 9. Il est déjà bien placé par rapport à la partie triée du tableau :

         [1, 3, 6, 7, 8, 9, 4, 2, 5]

On continue de la sorte jusqu’à ce que tous les éléments du tableau soient parcourus :

         [1, 3, 6, 7, 8, 9, 4, 2, 5]

     [1, 3, 4, 6, 7, 8, 9, 2, 5]

         [1, 3, 4, 6, 7, 8, 9, 2, 5]

     [1, 2, 3, 4, 6, 7, 8, 9, 5]

         [1, 2, 3, 4, 6, 7, 8, 9, 5]

Lorsque le dernier élément du tableau est inséré à la bonne position, tout le tableau est trié :

     [1, 2, 3, 4, 5, 6, 7, 8, 9]

Exercice 8 – Une question d’insertion

Trier le tableau suivant avec l’algorithme de tri par insertion : [3, 6, 8, 7, 1, 9, 4, 2, 5] à la main. Représenter l’état du tableau lors de toutes les étapes intermédiaires.

Solution 8 – Une question d’insertion

Cliquer ici pour voir la réponse

Lors de la première étape du tri par sélection, on cherche le plus petit élément :

     [3, 6, 8, 7, 1, 9, 4, 2, 5]

On échange les positions du premier et du plus petit élément :

     [1, 6, 8, 7, 3, 9, 4, 2, 5]

On cherche le plus petit élément dans le tableau, en excluant l’élément que l’on vient de trier :

         [1, 6, 8, 7, 3, 9, 4, 2, 5]

On échange sa position avec le 2e élément du tableau :

     [1, 2, 8, 7, 3, 9, 4, 6, 5]

Notez que les étapes qui changent l’ordre des éléments du tableau sont disposées à gauche. On cherche le plus petit élément du tableau non trié et on l’échange avec le troisième élément :

         [1, 2, 8, 7, 3, 9, 4, 6, 5]

     [1, 2, 3, 7, 8, 9, 4, 6, 5]

On continue de la sorte jusqu’à ce que tous les éléments soient triés (les éléments triés sont en vert) :

         [1, 2, 3, 7, 8, 9, 4, 6, 5]

     [1, 2, 3, 4, 8, 9, 7, 6, 5]

         [1, 2, 3, 4, 8, 9, 7, 6, 5]

     [1, 2, 3, 4, 5, 9, 7, 6, 8]

         [1, 2, 3, 4, 5, 9, 7, 6, 8]

     [1, 2, 3, 4, 5, 6, 7, 9, 8]

Le septième élément du tableau est déjà à la bonne position, donc il n’y a pas besoin d’échanger la position de deux éléments. Le tableau est trié lorsque tous les éléments sont parcourus.

         [1, 2, 3, 4, 5, 6, 7, 9, 8]

         [1, 2, 3, 4, 5, 6, 7, 9, 8]

     [1, 2, 3, 4, 5, 6, 7, 8, 9]

Exercice 9 – Une question de bulles

Trier le tableau suivant avec l’algorithme de tri à bulles : [3, 6, 8, 7, 1, 9, 4, 2, 5] à la main. Représenter l’état du tableau lors de toutes les étapes intermédiaires.

Solution 9 – Une question de bulles

Cliquer ici pour voir la réponse

Lors du tri à bulles, on considère les éléments deux par deux. S’ils sont dans le bon ordre, on ne fait rien, sinon on échange leur position :

     [3, 6, 8, 7, 1, 9, 4, 2, 5]     [3, 6, 8, 7, 1, 9, 4, 2, 5]     [3, 6, 8, 7, 1, 9, 4, 2, 5]         [3, 6, 7, 8, 1, 9, 4, 2, 5]     [3, 6, 7, 8, 1, 9, 4, 2, 5]         [3, 6, 7, 1, 8, 9, 4, 2, 5]     [3, 6, 7, 1, 8, 9, 4, 2, 5]     [3, 6, 7, 1, 8, 9, 4, 2, 5]         [3, 6, 7, 1, 8, 4, 9, 2, 5]     [3, 6, 7, 1, 8, 4, 9, 2, 5]         [3, 6, 7, 1, 8, 4, 2, 9, 5]     [3, 6, 7, 1, 8, 4, 2, 9, 5]         [3, 6, 7, 1, 8, 4, 2, 5, 9]

Il faut procéder à nouveau par un parcours de la liste depuis son début, où on compare et on réarrange les éléments deux par deux :

     [3, 6, 7, 1, 8, 4, 2, 5, 9]      [3, 6, 7, 1, 8, 4, 2, 5, 9]      [3, 6, 7, 1, 8, 4, 2, 5, 9]          [3, 6, 1, 7, 8, 4, 2, 5, 9]      [3, 6, 1, 7, 8, 4, 2, 5, 9]      [3, 6, 1, 7, 8, 4, 2, 5, 9]          [3, 6, 1, 7, 4, 8, 2, 5, 9]      [3, 6, 1, 7, 4, 8, 2, 5, 9]          [3, 6, 1, 7, 4, 2, 8, 5, 9]      [3, 6, 1, 7, 4, 2, 8, 5, 9]           [3, 6, 1, 7, 4, 2, 5, 8, 9]

Une deuxième « bulle » remonte, le deuxième élément le plus grand. On refait à nouveau un parcours du tableau (les éléments bien triés sont en gras) :

     [3, 6, 1, 7, 4, 2, 5, 8, 9]      [3, 6, 1, 1, 7, 4, 2, 5, 8, 9]          [3, 1, 6, 7, 4, 2, 5, 8, 9]      [3, 1, 6, 7, 4, 2, 5, 8, 9]      [3, 1, 6, 7, 4, 2, 5, 8, 9]          [3, 1, 6, 4, 7, 2, 5, 8, 9]      [3, 1, 6, 4, 7, 2, 5, 8, 9]          [3, 1, 6, 4, 2, 7, 5, 8, 9]      [3, 1, 6, 4, 2, 7, 5, 8, 9]          [3, 1, 6, 4, 2, 5, 7, 8, 9]

Lorsqu’on atteint la partie déjà triée du tableau (éléments en gras), on recommence depuis le début du tableau :

     [3, 1, 6, 4, 2, 5, 7, 8, 9]          [1, 3, 6, 4, 2, 5, 7, 8, 9]      [1, 3, 6, 4, 2, 5, 7, 8, 9]      [1, 3, 6, 4, 2, 5, 7, 8, 9]          [1, 3, 4, 6, 2, 5, 7, 8, 9]      [1, 3, 4, 6, 2, 5, 7, 8, 9]          [1, 3, 4, 2, 6, 5, 7, 8, 9]      [1, 3, 4, 2, 6, 5, 7, 8, 9]          [1, 3, 4, 2, 5, 6, 7, 8, 9]

On a atteint la partie triée du tableau, on recommence depuis le début :

     [1, 3, 4, 2, 5, 6, 7, 8, 9]      [1, 3, 4, 2, 5, 6, 7, 8, 9]      [1, 3, 4, 2, 5, 6, 7, 8, 9]          [1, 3, 2, 4, 5, 6, 7, 8, 9]      [1, 3, 2, 4, 5, 6, 7, 8, 9]

Les bulles (les plus grands nombres) continuent à remonter :

     [1, 3, 2, 4, 5, 6, 7, 8, 9]      [1, 3, 2, 4, 5, 6, 7, 8, 9]          [1, 2, 3, 4, 5, 6, 7, 8, 9]      [1, 2, 3, 4, 5, 6, 7, 8, 9]      [1, 2, 3, 4, 5, 6, 7, 8, 9]

On recommence à nouveau à comparer les éléments depuis le début du tableau :

     [1, 2, 3, 4, 5, 6, 7, 8, 9]      [1, 2, 3, 4, 5, 6, 7, 8, 9]      [1, 2, 3, 4, 4, 5, 6, 7, 8, 9]

Même si nous n’avons pas du intervertir la position de deux éléments, il faut à nouveau parcourir le tableau depuis le début :

     [1, 2, 3, 4, 5, 6, 7, 8, 9]      [1, 2, 3, 4, 5, 6, 7, 8, 9]

Et on fait une dernière comparaison :

     [1, 2, 3, 4, 5, 6, 7, 8, 9]

Le tableau est désormais trié :

     [1, 2, 3, 4, 5, 6, 7, 8, 9]

Exercice 10 – Une question de chronomètre 🔌

Créer une liste qui contient les valeurs de 1 à n dans un ordre aléatoire, où n prend la valeur 100, par exemple. Indice : utiliser la fonction shuffle() du module random.

Implémenter au moins deux des trois algorithmes de tri vu au cours. A l’aide du module time et de sa fonction time(), chronométrer le temps prend le tri d’une liste de 100, 500, 1000, 10000, 20000, 30000, 40000 puis 50000 nombres.

Noter les temps obtenus et les afficher sous forme de courbe dans un tableur. Ce graphique permet de visualiser le temps d’exécution du tri en fonction de la taille de la liste. Que peut-on constater ?

Sur la base de ces mesures, peut-on estimer le temps que prendrait le tri de 100000 éléments ?

Lancer votre programme avec 100000 éléments et comparer le temps obtenu avec votre estimation.

Solution à compléter