Tri par sélection

12.3. Tri par sélection#

12.3.1. L’algorithme#

Algorithm 12.1 (Tri sélection)

  1. Parcourir la liste à la recherche du minimum.

  2. Échanger le minimum trouvé avec la valeur en première position

  3. Recommencer 1 et 2 jusqu’à avoir parcouru tous les éléments.

12.3.2. Une implémentation possible#

On se donne une fonction echanger :

def echanger(t: list, i: int, j: int) -> list:
    assert 0 <= i < len(t), 'Indice i en dehors des bornes'
    assert 0 <= j < len(t), 'Indice j en dehors des bornes'
    t[i],t[j] = t[j],t[i]
    return t


echanger([1,2,3],1,2)

[1, 3, 2]

echanger([0,1],1,1)

[0, 1]

L’algorithme peut se mettre en œuvre de la façon suivante.

def tri_selection(tableau: list) -> list:
    for i in range(len(tableau) - 1):
        min = i
        for j in range(i + 1, len(tableau)):
        # Recherche du plus petit élément à échanger dans la partie non-triée
            if tableau[j] < t[min]:
                min = j
        if min != i:
            tableau = echanger(tableau, i, min)
    return tableau

On peut tester notre fonction sur un premier exemple.

t = [i for i in range(10)]
shuffle(t)
t

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[4], line 2
      1 t = [i for i in range(10)]
----> 2 shuffle(t)
      3 t

NameError: name 'shuffle' is not defined

tri_selection(t)

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

Afin d’augmenter la lisibilité du code, on peut remplacer la partie de recherche du plus petit élément par une fonction ad-hoc.

def mini(t, debut):
    """
    Une fonction qui cherche le minimum d'une liste à partir d'un indice.
    """
    m = t[debut]
    index = debut
    for i in range(debut,len(t)):
        if t[i] < m:
            m = t[i]
            index = i
    return index

Cette fonction coïncide avec le minimum usuel quand on part de 0.

mini([1,2,3],0)

0

Mais cette fonction renvoie l’indice du minimum de la sous-liste débutant à la valeur spécifiée.

mini([1,2,3],1)

1

Le code précédent devient

def tri_selection(tableau):
    for i in range(len(tableau)):
        index_min = mini(tableau,i)
        tableau = echanger(tableau,i,index_min)
    return tableau

On peut tester la fonction ainsi écrite.

t = [i for i in range(10)]
shuffle(t)
t

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[10], line 2
      1 t = [i for i in range(10)]
----> 2 shuffle(t)
      3 t

NameError: name 'shuffle' is not defined

tri_selection(t)

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

t

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

12.3.3. Première approche des interrogations sur les algorithmes#

Parmi les questions qu’on peut se poser sur un algorithme, on en dénombre trois :

  • quelle est la complexité de l’algorithme ;

  • est-ce que l’algorithme est correct, c’est-à-dire qu’il est conforme à sa spécification ;

  • est-ce que l’algorithme termine (ou s’arrête) sur une entrée, sur toutes les entrées (terminaison uniforme)

Si un algorithme est correct et termine, on parle de correction totale.

12.3.3.1. Complexité#

La complexité sera étudiée en détail dans un autre chapitre, mais il est nécessaire de dire plusieurs choses. On distingue pour commencer

  • le meilleur des cas (ici la liste est déjà triée)

  • le pire des cas (aucun élément n’est à sa bonne place)

  • le cas moyen (hors-programme)

On montre que la complexité d’un tel algorithme est \(\mathcal{O}(n^2)\). En effet, l’algorithme réalise \(n\) recherche du minimum dans une liste à \(n - i\) éléments, pour \(i\) variant de \(1\) à \(n - 1\). Il y a donc, au facteur multiplicatif près, \(n + n - 1 + n - 2 + … + 1\) opérations. Cette somme vaut \(\frac{n(n+1)}2\), ce qui achève la preuve.

12.3.4. Correction#

Pour montre qu’un algorithme est correct, il faut montrer qu’à chaque itération, une certaine propriété est vérifiée. Dans notre cas, on peut vérifier que le début de la liste est toujours trié. En effet, à la première itération, on a placé le plus petit élément en première position, puis le plus petit élément parmi les restants a été placé en première position, … Ainsi, la propriété est bien vérifiée.

12.3.5. Terminaison#

Pour montrer qu’un algorithme termine, il faut montrer que par exemple la taille de la liste des éléments restant à trier diminue à chaque itération. Ici, c’est bien le cas : à l’itération i, il reste len(tableau) - 1 - i éléments à trier et donc à l’itération i = len(tableau) - 1, il ne restera plus d’éléments à trier.

Contenu