Tris

Définition

Algorithme de tri

Algorithme qui, partant d’un tableau, renvoie une version ordonnée du tableau. $$[5,1,4,3,2] \rightarrow [1,2,3,4,5]$$

Tris par comparaison

Tous les algorithmes étudiés reposent sur les comparaisons. Tout ce qu’on peut faire c’est :

  • comparer deux éléments entre eux et choisir le plus petit
  • échanger deux éléments dans le tableau.

Et c’est suffisant.

Il existe de nombreux algorithmes de tri disposant de complexités différentes.

En première : tri par insertion et tri par sélection.

Python

Python utilise TimSort qui est plus efficace et mieux implémenté que ce que nous ferons.

>>> tableau = [4, 3, 1, 2]
>>> sorted(tableau) # renvoie une copie triée
[1, 2, 3, 4]
>>> tableau # l'objet de départ N'EST PAS MODIFIÉ
[4, 3, 1, 2]
>>> tableau.sort() # trie DANS l'objet, ne renvoie rien
>>> tableau # l'objet de départ EST MODIFIE
[1, 2, 3, 4]

Tri par sélection

Description

On cherche à trier des boîtes. Tout ce qu’on peut faire c’est le comparer 1 à 1 et les échanger.

Pseudo code

Je débute avec un alignement vide de boîtes triées
Tant qu'il y a des boîtes non triées :
   Je cherche la plus légère parmi les boîtes non triées
   Je la place à la suite des boîtes déjà triées.
fin Tant que

Et pour la fonction trouver la boite la plus légère :

Entrée : Des boîtes
Sortie : La boite la plus légère
Effet de Bord : Enlève une boite

Je prends une boîte (main gauche)
Pour chacune des autres (main droite) :
    Si elle est plus légère que la boite dans ma main,
    Alors j'échange.
	Fin Si
	Je mets l'autre de côté.
Fin Pour

Python

def selection(tableau):
    '''
    tri par sélection d'un tableau.
    @param tableau: (list) objets pouvant être comparés dans Python
    @return: None
    @Effet de bord: modifie le tableau
    '''
    n = len(tableau)
    for i in range(n):
        m = i  # on cherche l'indice du min
        for j in range(i+1, n):
            if tableau[m] > tableau[j]:
                m = j
        tableau[m], tableau[i] = tableau[i], tableau[m]  # on echange

Exemple

Triés Non Triés Plus petit restant
() (1, 3, 4, 2) (1)
(1) (3, 4, 2) (2)
(1, 2) (3, 4) (3)
(1, 2, 3) (4) (4)
(1, 2, 3, 4)

Tri par insertion

En français

    Je débute avec un alignement vide de boîtes triées
    Tant qu'il y a des boîtes non triées :
       Je choisis une boite
	   Je l'insère dans l'alignement de telle sorte
     qu'il reste trié
    fin Tant

et, pour l’opération d’insérer :

Entree : Un alignement de boîtes trié, une boîte b
Sortie : rien
Effet de bord: l'alignement reste trié

Prends la boîte la plus à droite (la plus lourde)
Tant que cette boite est plus lourde que b
     passe à la boite suivante
insère b à la droite de la boite courante

Exemple

Triés Non Triés Élément le plus à gauche
() (1, 3, 4, 2) (1)
(1) (3, 4, 2) (3)
(1, 3) (4, 2) (4)
(1, 3, 4) (2) (4)
(1, 2, 3, 4)

Python

def tri_insertion(tableau):
  '''
  tri par insertion d'un tableau.
  @param tableau: (list) objets pouvant être comparés dans Python
  @return: None
  @Effet de bord: modifie le tableau
  '''
  for i in range(1, len(tableau)):
    j = i
    while j > 0 and tableau[j-1] > tableau[j]:
      tableau[j-1], tableau[j] = tableau[j], tableau[j-1]
      j = j - 1

Propriétés communes des tris par insertion et sélection

Caractéristiques :

  • Tris stables : ils ne changent pas l’ordre de deux éléments “égaux”
  • Tris en place : ils n’utilisent pas plus de mémoire que le tableau initial

Invariant de boucle et terminaison

Un invariant de boucle est un propriété qui est vraie avant et après chaque tour d’une boucle.

Durant le tour n° i de la boucle extérieure :

  • les i premiers éléments du tableau sont triés.
  • le nombre d’élément à trier diminue de 1.

Donc ces algorithmes trient bien la liste et ils s’arrêtent.

Complexité

Ils sont de complexité quadratique : $O(n^2)$. Le nombre de comparaisons (et la durée d’exécution) sont proportionnels au carré de la taille du tableau.