Ctrl+K

Algorithmes de tri

Algorithmes de tri#

Tri par sélection#

L’algorithme de tri par sélection sépare le tableau en deux sous-tableaux.

  • Le premier sous tableau contient les valeurs déjà triées; il est vide au départ!

  • Le second sous tableau contient les valeurs non triées; c’est le tableau en entier au départ!

Toutes les valeurs de la partie non triée sont supérieures (ou égales) aux valeurs de la partie triée.

On cherche dans le sous-tableau non trié la plus petite valeur. Ensuite, on l’échange avec la première valeur du sous-tableau non trié. Après l’échange, le sous-tableau trié possède une valeur en plus et le sous-tableau non trié a une valeur en moins.

../_images/tri_selection.svg

Tri par sélection d’un tableau de nombres#

Ainsi, par itération, le sous-tableau non trié diminue jusqu’à être vide et le tableau est entièrement trié.

Avertissement

la difficulté de cet algorithme se situe dans la gestion des indices du tableau. On doit manipuler :

  • l’indice de la première valeur de la partie non triée qui est incrémentée de 1 à chaque itération;

  • l’indice de la valeur minimale de la partie non triée, qui permet l’échange avec la première valeur de la partie non triée.

Algorithme du tri par sélection

On donne ci-dessous en pseudo code l’algorithme de tri par sélection:

n = len(tableau)     # n - 1 est l'indice du dernier élément du tableau
i = 0                # indice des éléments du tableau à parcourir; i prend les valeurs de 0 à n - 1
tant que i < n:
   j = i             # j est l'indice des éléments du sous-tableau non encore trié à parcourir
   k = i             # k est l'indice du plus petit élément du sous-tableau non trié

   # on cherche dans le sous-tableau non trié, la valeur minimale soit entre entre les indices i et n-1
   tant que j < n:
      si tableau[j] < tableau[k]:
         k = j
      j = j + 1

   # après avoir trouvé l'indice du plus petit élement du sous-tableau non trié, on échange, si elles sont
   # différentes, la valeur minimale et la première valeur d'indice i du sous-tableau non trié
   si k != i
      on échange les valeurs d'indice i et k

   # on passe à la valeur suivante ce qui agrandit le sous-tableau trié et réduit le sous-tableau non trié.
   i = i + 1

Tri par insertion#

L’algorithme de tri par insertion sépare le tableau en deux sous tableaux.

  • Le premier sous-tableau contient les valeurs déjà triées; il contient la première valeur du tableau au début!

  • Le second sous-tableau contient les valeurs non triées; c’est le tableau sans son premier élément au début!

La première valeur du sous-tableau non trié est mémorisée dans une variable tampon. Toutes les valeurs du sous-tableau trié supérieures à la variable tampon sont décalées de 1 rang vers la droite dans le tableau. Après décalage de ces valeurs, on insère la valeur mémorisé dans la variable tampon.

../_images/tri_insertion.svg

Algorithme du tri par insertion

n = len(tableau)        # le dernier élément a pour indice n - 1
i = 1                   # indice de la valeur à insérer et mémorisée dans la variable tampon

tant que i < n:
   j = i - 1
   tampon = tableau[i]  # la variable tampon prend la valeur du tableau à insérer dans le sous tableau trié

   # on décale toutes les valeurs du tableau supérieures à la variable tampon
   tant que j >= 0 et tableau[j] > tampon :
      tableau[j + 1] = tableau[j]   # on décale à droite la valeur du tableau
      j = j - 1                     # on passe à l'élément plus à gauche

   # on insère la variable tampon dans le sous tableau trié en bonne place
   tableau[j + 1] = tampon    # j + 1 car pour sortir de la boucle on a décalé une fois de trop à gauche !

   # on passe à la valeur suivante dans le sous-tableau non trié
   i = i + 1

Complexité des tris#

Les tris par selection et par insertion ont la même complexité. On peut la mesurer en comptant le nombre de comparaisons effectuées à chaque itération des boucles while. Pour les deux algorithmes, on a 2 boucles imbriquées.

Pour un tableau de dimension \(n\):

  • La première boucle while effectue \(n\) fois la seconde boucle while;

  • La seconde boucle while réalise \(n\) comparaisons, puis \(n-1\) comparaisons, puis \(n-2\) comparaisons, etc.

Finalement l’algorithme effectue \(n+(n-1)+...+3+2+1 = \dfrac{n(n+1)}{2}\) comparaisons.

Ce nombre de comparaisons a pour ordre de grandeur \(n^{2}\).

On en déduit que le nombre de comparaisons dépend de la dimension \(n\) du tableau. On dit que la complexité de ces tris est quadratique et se note \(O(n^{2})\).

Contenu