Tri bulle

Le tri bulle est un tri simple qui consiste à faire “remonter” vers la fin du tableau le plus grand (ou plus petit si tri décroissant) élement du tableau, la plus petite valeur du tableau pour la mettre au début. Exemple :

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

Première passage (boucle principale)

• 3 et 6 sont comparés : ils sont dans l’ordre (pas de modification).
• 6 et 1 sont comparés : inversion de leur position (ce qui fait remonter 6).

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

• 6 et 5 sont comparés : inversion de leur position.
• …

A la fin de ce premier passage, le plus grand élément est correctement placé.

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

Deuxième passage (boucle principale)

Il faure recommencer depuis le début :

• 3 et 1 sont comparés (inversion)

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

• 3 et 5 sont comparés (pas de modification).
• 5 et 2 sont comparés (inversion).
• 5 et 2 (l’autre) sont comparés (inversion).

A la fin de ce passage, le tableau contient :

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

Puis on continue avec un troisième passage (il y en à n - 1 au total).

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 triBulle(tab: List[float]) -> List[float]:
    """
    trie le tableau selon la méthode du tri bulle, par ordre croissant
    @param tab le tableau de valeurs, en entrée-sortie (par adresse)
    @return le tableau trié par ordre croissant (pour doctests)
    >>> triBulle([])
    []
    >>> triBulle([2, 1, 3])
    [1, 2, 3]
    >>> triBulle([5, 4, 3, 2, 1])
    [1, 2, 3, 4, 5]
    """
    
    global cout         #CPLX
    cout = 0            #CPLX
    for i in range(len(tab) - 1): #passages
        #invariant: le tableau est trié à partir de len(tab) - 1 - i
        for j in range(len(tab) - 1 - i):
            cout += 1   #CPLX
            if tab[j] > tab[j+1]:
                pivot = tab[j+1] #permutation
                tab[j+1] = tab[j]
                tab[j] = pivot
    return tab
    

if __name__ == "__main__":
    import doctest; doctest.testmod()
    t1 = [1,3,2,5,4]
    triBulle(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.

Cet algorithme peut être optimisé :

• il est inutile de refaire un passage s’il n’y a pas eu de permuration ;
• ou mieux, il est inutile de regarder après l’indice de la dernière permutation.

from typing import List

def triBulleOpti(tab: List[float]) -> List[float]:
    """
    trie le tableau selon la méthode du tri bulle, par ordre croissant
    @param tab le tableau de valeurs, en entrée-sortie (par adresse)
    @return le tableau trié par ordre croissant (pour doctests)
    >>> triBulleOpti([])
    []
    >>> triBulleOpti([2, 1, 3])
    [1, 2, 3]
    >>> triBulleOpti([5, 4, 3, 2, 1])
    [1, 2, 3, 4, 5]
    """
    
    global cout         #CPLX
    cout = 0            #CPLX
    k = len(tab) #emplacement de la dernière permutation
    while k > 1: #tant que la zone non triée fait au moins deux cellules
        """
        variant: k, tend vers 0 (preuve de terminaison)
        invariant: le tableau est trié à partir de k
        """
        k = k - 1   
        for j in range(k):
            cout += 1   #CPLX
            if tab[j] > tab[j+1]:
                tab[j], tab[j+1] = tab[j+1], tab[j] #permutation Python
                k = j + 1 #mise à jour de l'emplacement de la dernière permutation
    return tab
    

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

Dans le meilleur des cas (si le tableau est déjà trié), le coût est de n - 1 (soit une complexité en O(n)). Cependant, bien que la complexité moyenne soit inférieure à celle de l’algorithme non optimisé, dans le pire cas (tableau trié dans l’ordre inverse), elle reste identique ; cet algorithme reste en O(n²).