Skip to content

Tri par Sélection

Trier

Un tableau est dit trié lorsque ses éléments sont ordonnés (du plus petit au plus grand si ça n'est pas précisé).

Un tableau dont les éléments ne sont pas ordonnés n'est pas trié. (ça peut paraître bête mais c'est important)

Lorsqu'on trie un tableau T, le tableau résultat doit: - Etre trié - Etre une permutation du tableau initial

Une permutation d'un tableau T est un tableau contenant exactement les mêmes éléments avec la même multiplicité, indépendamment de leur ordre.

Par exemple:

  • [1, 9, 7] est une premutation de [9, 1, 7]
  • [2, 8, 7, 8] est une permutation de [8, 2, 8, 7]

Il existe plusieurs méthodes pour trier. Cette opération est fondamentale en informatique.

Les méthodes ci-dessous permettent de le faire à la façon dont on peut trier un jeu de cartes.

Il en existe d'autres bien plus performantes

Il s'agit du problème SORTING pour lequel nous allons voir 2 algorithmes bien connu.

Tri par sélection

Algorithme imagé

Je veux trier des cartes

  • Dans ma main droite, j'ai l'ensemble des cartes.
  • Je déplace successivement sur ma main gauche la plus petite carte de la main droite.
  • A l'arrivée, ma main gauche est triée et ma main droite est vide

alt text

L'invariant est ici composé de 3 propriétés:

  1. Les cartes de la main gauches sont toutes inférieures ou égales à celles de la main droite
  2. Les cartes de la main gauche sont triées
  3. Les cartes de la main gauche et de la main droite sont une permutation du tableau initial

INITIALISATION L'invariant est vrai au début car :

  1. Toutes les cartes de la main droite sont supérieures aux 0 cartes de ma main gauche. Cette dernière affirmation à première vue étrange vient qu'en logique, c'est vrai parce que rien dans le vide ne permet de l'infirmer. De la même manière, "Tous les portables sont éteints dans la pièce" est vrai même s'il n'y a pas de portable dans la pièce. Les anglophones appellent ça une "vacuous truth", une vérité émanant de l'incapacité du vide à infirmer. (1)

  2. Ma main gauche est vide donc elle n'est pas désordonnée. Elle est donc triée.

  3. Dans ma main droite, j'ai l'ensemble du jeu de cartes, ni plus ni moins,donc une permutation du jeu de cartes.

CONSERVATION DE L'INVARIANT A un moment quelconque de l'algorithme, imaginons l'invariant vrai.

  1. Les cartes de ma main gauche sont inférieures à celles de la main droite
  2. La main gauche est triée
  3. L'ensemble des cartes en ma possession est une permutation du jeu de cartes

Si je prends la carte de la main droite, par (1.), elle reste donc supérieure à celles de la main gauche.

Dans le processus, je ne perds ni ne gagne de cartes (3. reste vraie).

De plus, les cartes de ma main droite sont encore supérieures ou égales à celles de la main gauche (1. reste vraie)

De ce fait, si je la place sur ma main gauche triée, ma main gauche reste triée (2. reste vraie)

Après avoir appliqué une étape de l'algorithme en supposant l'invariant vrai, on a donc prouvé que l'invariant est conservé.

TERMINAISON

La main droite perd exactement une carte par tour ; après n tours, elle est vide. On ne peut plus déplacer de cartes. Donc l'algorithme se termine.

L'invariant est vrai au départ, et il est conservé à chaque étape quelconque de l'algorithme. C'est donc qu'il est aussi vrai à la fin de l'algorithme.

A la fin de l'algorithme, toutes les cartes sont dans la main gauche et l'invariant est vrai.

C'est donc que ma main gauche contient une permutation triée du jeu de cartes.

Implémentation d'après l'exemple donné

Ecrire une fonction tri_selection(main_gauche: list[int], main_droite: list[int]) qui applique cet algorithme.

def tri_selection(main_gauche: list[int], main_droite: list[int]):
    """
    Applique le tri par sélection tel que présenté.

    TANT QUE "la main droite n'est pas vide"
       PRENDRE LE MINIMUM DE LA MAIN DROITE
       L'AJOUTER A LA FIN DE LA MAIN GAUCHE

    >>> g = []
    >>> d = [5, 3, 9, 6]
    >>> tri_selection(g, d)
    >>> g
    [3, 5, 6, 9]
    >>> d
    []
    """

Nous allons maintenant faire exactement la même chose, mais avec les notations usuelles.

Algorithme usuel

  • On dispose d'un tableau \(T\) de taille \(n\) noté \(T[0..n-1]\)
  • Pour \(i\) allant de \(0\) à \(\color{red}n-2\)
    • \(\displaystyle imin = \argmin_{j \in [i, n-1]} T[j]\)
    • échanger \(T[i]\) et \(T[imin]\)

Notez que nous avons déjà résolu et étudié le problème ARGMIN

Notations

  • \(T[i..j]\) représente le sous-tableau de \(T\) de l'indice \(i\) à l'indice \(j\) inclus. - Si \(i>j\), alors il s'agit du tableau vide.
  • \(T[i..j] \le T[k..l]\) signifie que toutes les valeurs du tableau de gauche sont inférieures ou égales aux valeurs du tableau de droite
  • \(T[i] \le T[j..k]\) signifie que la valeur \(T[i]\) est inférieure ou égale à toutes les valeurs de \(T[j..k]\)
  • \(T[i..i]\) représente le sous-tableau à 1 élément
  • L'opérateur + sur des tableaux est la concaténation

FORMULATION DE L'INVARIANT:

On reprend l'invariant précédent avec les notations.

Au début de chaque itération \(i\):

  1. \(T[0..i-1] \le T[i..n-1]\)
  2. \(T[0..i-1]\) est trié
  3. \(T[0..n-1]\) est une permutation du tableau initial

INITIALISATION:

Pour i=0:

\(T[0..i-1] = T[0..-1] = []\)

  1. Tous les éléments de \([]\) sont inférieurs aux éléments de \(T[0..n-1]\) (Le tableau entier)
  2. \(T[0..-1]\) est le tableau vide. Il est trié.
  3. \(T[0..n-1]\) est une permutation de lui-même.

L'invariant est donc vrai avant la première itération.

CONSERVATION

On suppose l'invariant vrai avant l'itération \(i\):

Indice \(0\) … \(i‑1\) \(i\) … \(n‑1\)
Valeur \(T[0]\) … \(T[i‑1]\) \(T[i]\) … \(T[n‑1]\)
  1. \(T[0..i-1] \le T[i..n-1]\)
  2. \(T[0..i-1]\) est trié
  3. \(T[0..n-1]\) est une permutation du tableau initial

On veut prouver que l'invariant est toujours vrai avant l'itération \(i+1\), donc qu'à la fin de l'itération \(i\) transformant \(T\) en \(T'\):

  • \(T'[0..i] \le T'[i+1..n-1]\)
  • \(T'[0..i]\) est trié
  • \(T'[0..n-1]\) reste une permutation de \(T\)

A l'itération \(i\), on calcule \(\displaystyle imin = \argmin_{k \in \![ i, n-1\!]} T[k]\)

On a donc trouvé \(imin\) tel qu'on peut décomposer le tableau en:

0 … i‑1 i i+1 … imin‑1 imin imin+1 … n‑1
T[0] … T[i‑1] T[i] T[i+1] … T[imin‑1] T[imin] T[imin+1] … T[n‑1]

\(T = T[0..i-1] + {\color{red}T[i..i]} + T[i+1..imin-1] + {\color{blue}T[imin..imin]} + T[imin+1..n-1]\)

Puis on intervertit \(T[imin]\) et \(T[i]\), et notre tableau final devient:

\(T' = \underbrace{T[0..i-1] + {\color{blue}T[imin..imin]}}_{\large T'[0..i]} + \underbrace{T[i+1..imin-1] + {\color{red}T[i..i]} + T[imin+1..n-1]}_{\large T'[i+1..n-1]}\)

On note immédiatement que (3.) est conservé car on ne fait que transposer 2 éléments de \(T\). \(T'\) reste donc une permutation de \(T\).

Par définition de \(imin\), et sachant (1.)

\(T[0..i-1] \le T[imin..imin] \le T[i+1..imin-1] + T[imin+1..n-1]\)

Donc \(T'[0..i] \le T'[i+1..n-1]\), et donc (1.) est conservé.

Mais \(T[imin]\) est aussi plus grand ou égal aux éléments triés de \(T[0..i-1]\) car il appartient à \(T[i..n-1]\). Donc en le rattachant à \(T[0..i-1]\), on ne brise pas le tri. \(T'[0..i]\) est donc trié et (2.) est conservé.

L'invariant est donc conservé.

TERMINAISON

A la fin de la dernière itération pour \(i=n-2\), l'invariant est conservé. Il est donc vrai pour \(i=n-1\)

  1. \(T[0..n-2] \le T[n-1..n-1]\)
  2. \(T[0..n-2]\) est trié
  3. \(T[0..n-1]\) est une permutation du tableau initial

(1.) et (2.) impliquent que \(T[0..n-1]\) est trié. (c'est pour ça que ça suffit d'aller jusqu'à \(n-2\))

(3.) implique que le tableau est une permutation du tableau initial.

A la fin de l'exécution de l'algorithme le tableau est donc une permutation triée du tableau initial.

L'algorithme est totalement correct.

Complexité

Quelle est la complexité de l'algorithme de tri par insertion