Page MenuHomePhabricator

Les algorithmes de tris
Updated 19 Days AgoPublic

tri par sélection

Le tri par sélection est celui qui utilise le concept le plus simple. Étant donné qu'il existe un algorithme qui permet de renvoyer la valeur la plus petite d'un tableau, on peut l'appliquer systématiquement pour reconstruire un tableau trié. En d'autres termes, à chaque case du tableau que l'on souhaite trier, on effectue une recherche dans la partie de droite pour retrouver l'élément le plus petit. Une fois trouvé, on échange les valeurs.

tri par sélection
PROCÉDURE TRI_SELECT(t: TABLEAU D'ENTIERS, n: ENTIER)
    VARIABLE i, j, min, swap: ENTIER
    POUR i DE 0 À N-2:
        min <- i

        POUR j DE i À N-1:
            SI t[j] < t[min], ALORS
                min = j
            FIN SI
        FIN POUR

        swap <- t[min]
        t[min] <- t[i]
        t[i] <- swap

    FIN POUR
FIN PROCÉDURE

tri à bulles

Il consiste à comparer répétitivement les éléments consécutifs d'un tableau, et à les permuter lorsqu'ils sont mal triés. Il doit son nom au fait qu'il déplace rapidement les plus grands éléments en fin de tableau, comme des bulles d'air qui remonteraient rapidement à la surface d'un liquide.

tri à bulles
PROCÉDURE TRI_A_BULLES(t: TABLEAU D'ENTIERS, n: ENTIER)
    VARIABLE i, j, swap: ENTIER
    POUR i DE 0 À N-1
        POUR j DE N-2 À i, PAR PAS DE -1:
            SI t[j+1] < t[j]:
                swap <- t[j+1]
                t[j+1] <- t[j]
                t[j] <- swap
            FIN SI
        FIN POUR
    FIN POUR
FIN PROCÉDURE
Notez que dès qu'une itération est effectuée sans échange. Cela signifie que tout le tableau est trié. Il est donc possible d'interrompre prématurément l'algorithme
tri à bulles interrompu
PROCÉDURE TRI_A_BULLES_FASTER(t: TABLEAU D'ENTIERS, n: ENTIER)
    VARIABLE i, j, swap: ENTIER
    VARIABLE trié: BOOLÉEN

    trié <- Faux
    TANT QUE trié != Vrai ET 0 < n -1

        trié <- Vrai
        POUR j DE N-2 À i, PAR PAS DE -1:
            SI t[j+1] < t[j]:
                swap <- t[j+1]
                t[j+1] <- t[j]
                t[j] <- swap
                trié <- Faux
            FIN SI
        FIN POUR

        i <- i+1
    FIN TANT QUE
FIN PROCÉDURE

tri par insertion

Le tri par insertion est considéré comme le tri le plus efficace sur des entrées de petite taille. Il est aussi très rapide lorsque les données sont déjà presque triées. La plupart des personnes l'utilisent naturellement pour trier des cartes à jouer.

tri par insertion
PROCÉDURE TRI_INSERT(t: TABLEAU D'ENTIERS, n: ENTIER)
    VARIABLE i, j, swap: ENTIER

    POUR i DE 1 À N-1:
        j <- i 
        TANT QUE j > 0 AND a[j-1] > a[j]:
            swap <- a[j]
            a[j] <- a[j-1]
            a[j-1] <- swap

            j <- j-1
        FIN TANT QUE
    FIN POUR
FIN PROCÉDURE

tri rapide

Il existe des familles de tri, plus rapide, mais aussi plus complexe à implémenter. L'un de ces algorithmes est celui de quicksort où l'idée est de diviser pour mieux régner.


L'idée est de fixer arbitrairement une valeur pivot, et de déplacer les valeurs à droite si elles sont plus grandes que le pivot ou à gauche dans le cas contraire. Une fois fait, il faut rééxécuter ce même algorithme sur ces deux nouvelles parties des tableaux. Il s'agit ici d'un algorithme récursif.

tri rapide
PROCÉDURE TRI_RAPIDE(t: TABLEAU D'ENTIERS, g: ENTIER, d: ENTIER)
    VARIABLES i, j, p, swap: ENTIER
    i <- g
    j <- d
    p <- t[j]

    TANT QUE i < j:
        TANT QUE t[i] < p:
            i <- i+1
        FIN TANT QUE
        TANT QUE t[j] > p:
            j <- j-1
        FIN TANT QUE

        SI i <= j, ALORS:
            swap <- t[i]
            t[i] <- t[j]
            t[j] <- swap

            i <- i+1
            j <- j-1
        FIN SI
    FIN TANT QUE

    SI g < j, ALORS:
        TRI_RAPIDE(t, g, j)
    FIN SI

    SI i < d, ALORS:
        TRI_RAPIDE(t, i, d)
    FIN SI
FIN PROCÉDURE
Attention, contrairement aux autres fonctions, il faut renseigner deux valeurs supplémentaires pour pouvoir effectuer le tri. Pour démarrer le tri, vous devez donc utiliser TRI_RAPIDE(t, 0, n-1). Une erreur commune est à tord utiliser la valeur n. Il s'agit ici bien de la dernière case et non pas de la taille du tableau.

La complexité des tris

Bien que QUICKSORT soit le plus rapide, il existe cependant un cas de figure théorique où l'algorithme est au pire cas en complexité quadratique. Toutefois malgré ce désavantage, c'est en pratique un des tris les plus rapides, et donc l'un des plus utilisés. Par contre, il restera plus lent que le tri par insertion dans le cas où le tableau est pratiquement déjà entièrement trié.

Il est d'ailleurs possible de combiner deux algorithmes ensembles pour éviter le pire cas. Par exemple, on peut utiliser le tri rapide lorsque le tableau est très grand, mais une fois que l'intervalle est suffisamment petit on peut utiliser un tri par insertion. C'est exactement le fonctionnement de Introsort.

tripire casmeilleur casmoyenne
sélectionO( n² )O( n² )O( n² )
bulleO( n² )O( n )O( n² )
insertionO( n² )O( n )O( n² )
rapideO( n² )O( n log n )O( n log n )
Last Author
Steve
Last Edited
Thu, Jan 7, 8:51 PM

Event Timeline

Steve created this object.Sep 16 2020, 2:26 PM
Steve edited the content of this document. (Show Details)Sep 16 2020, 3:08 PM
Steve edited the content of this document. (Show Details)Sep 16 2020, 3:40 PM
Steve edited the content of this document. (Show Details)Dec 14 2020, 9:24 AM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Dec 14 2020, 9:46 AM
Steve edited the content of this document. (Show Details)Dec 14 2020, 10:33 AM
Steve edited the content of this document. (Show Details)Dec 14 2020, 10:45 AM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Dec 14 2020, 2:11 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Dec 14 2020, 2:14 PM
Steve edited the content of this document. (Show Details)Dec 14 2020, 2:40 PM
Steve edited the content of this document. (Show Details)Dec 14 2020, 2:44 PM
Steve edited the content of this document. (Show Details)Dec 14 2020, 2:47 PM
Steve edited the content of this document. (Show Details)Dec 14 2020, 2:50 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Dec 17 2020, 5:31 PM
Steve edited the content of this document. (Show Details)Thu, Jan 7, 8:51 PM