Tri sélection

Le tri par sélection est un tri simple qui consiste à chercher l’indice de la plus petite valeur (ou la plus grande si tri décroissant) du tableau pour la mettre au début. Exemple :

indices	0	1	2	3	4	5
valeurs	3	6	1	5	2	2

A la première itération, la plus petite valeur (1) est à l’indice 2. L’algorithme intervertit alors cette valeur avec celle à l’indice 0 (3).

indices	0	1	2	3	4	5
valeurs	1	6	3	5	2	2

A la deuxième itération, on cherche l’indice de la plus petite valeur à partir de l’indice 1. Cette fois c’est 2, à l’indice 4 (première occurence). L’algorithme intervertit alors tab[4] avec tab[1].

indices	0	1	2	3	4	5
valeurs	1	2	3	5	6	2

On remarque que la position avec laquelle la plus petite valeur est intervertie est 0, puis 1… De même, on cherche la plus petite valeur à partir de 0, puis 1… Ainsi, la boucle principale est de la forme :

for i in range(len(tab) - 1):
    k = indiceMin(tab, i) #à partir de i
    tmp = tab[k]
    tab[k] = tab[i]
    tab[i] = tmp

Lorsque il ne reste qu’une seule cellule, il est inutile de rechercher l’indice de la plus petite valeur (…), d’où le -1 dans range.

La complexité en temps de calcul de cet algorithme est en O(n²) ; il y a précisément (n - 1) x n / 2 opérations.

• n - 1 est le nombre d’itérations (boucle principale).
• n / 2, est la moyenne du nombre d’itérations secondaires : n - 1 lors de la première itération principale, 1 à la dernière, soit (n - 1 + 1) / 2.

Dans cette version, indiceMini est intégré à la fonction :

from typing import List

def triSelection(tab : List[float]) -> List[float]:
    """
    trie le tableau selon la méthode du tri par sélection, par ordre croissant
    @param tab le tableau de valeurs, en entrée-sortie (par adresse)
    @return le tableau trié par ordre croissant (pour doctests)
    >>> triSelection([])
    []
    >>> triSelection([2, 1, 3])
    [1, 2, 3]
    >>> triSelection([5, 4, 3, 2, 1])
    [1, 2, 3, 4, 5]
    """
    
    global cout         #CPLX
    cout = 0            #CPLX
    for i in range(len(tab) - 1):
        #invariant: tab est trié jusqu'à l'indice i - 1, et tous les éléments à partir de i sont supérieurs à celui à l'indice i - 1
        
        #recherche de l'indice de la plus petite valeur :
        k = i
        for j in range(i + 1, len(tab)):
            cout += 1   #CPLX (dénombre le nombre de comparaisons)
            if tab[j] < tab[k]:
                k = j
                
        #permutation :
        if k != i: #permutation uniquement si nécessaire
            v = tab[i]
            tab[i] = tab[k]
            tab[k] = v
    return tab


if __name__ == "__main__":
    import doctest; doctest.testmod()
    t1 = [1,3,2,5,4]
    triSelection(t1)
    print(t1)
    n = len(t1)
    print("complexité théorique : " + str(int((n-1)*n/2)))
    print("complexité effective : " + str(cout))

Observer qu’en pratique, la complexité (effective) de l’algorithme est toujours égale à la théorique. L’algorithme est stable.

Remarque : il est inutile de renvoyer le tableau (car il est modifié par la fonction — cf passage en entrée-sortie), mais c’est plus pratique pour écrire des doctests.