Introduction

Le tri rapide est un algorithme de tri généralement efficace de type “diviser pour régner”. Son principe de fonctionnement est le suivant :

  • choix d’une valeur pivot — le dernier élément du tableau dans la version de base présentée ici ;
  • partitionement du tableau selon cette valeur en deux sous tableaux :
    • éléments plus petits (ou plus grands pour un tri décroissant que la valeur pivot dans la partie gauche / inférieure,
    • les autres dans éléments dans le partie droite / supérieure ;
  • tri récursif des deux sous-tableaux.

A titre de comparaison, le tri fusion fait l’inverse : il découpe d’abord en sous tableaux, puis fusionne.

Opération de partitionnement

Trois variables (en plus du tableau) sont nécessaires pour effectuer le partitionnement :

  • la valeur pivot vp - choisie ici (arbitrairement) au niveau du dernier indice ;
  • l’indice du pivot ip qui sert à partager le tableau en deux sous-tableaux ; après la dernière itération, tout ce qui est avant ip est plus petit que vp (et ce qui est après plus grand).
  • l’indice i de la valeur traitée.

Exemple :

indices 0 1 2 3 4 5 6
valeurs 3 6 1 5 2 2 4
i/ip vp

vp est initialisée à 4, i et ip à 0.

  • A la première itération, tab[i] (3) est comparé à vp (4) ; comme ip est égal à i, il n’y a rien d’autre à faire qu’incrémenter ip.
  • A la deuxième itération, tab[i] (6) est comparé à vp (4) ; comme la valeur est plus grande, il n’y a rien à faire.
  • A la première itération, tab[i] (1) est comparé à vp (4) ; comme elle est plus petite et que ip ≠ i, tab[i] et tab[ip] sont inversés, et ip est ensuite incrémenté :
    • avant :
indices 0 1 2 3 4 5 6
valeurs 3 6 1 5 2 2 4
avant ip i vp 
- après :
indices 0 1 2 3 4 5 6
valeurs 3 1 6 5 2 2 4
avant i/ip vp
  • L’algorithme continue ainsi jusqu’à l’avant dernier indice (le pivot est exclu de la comparaison avec lui même) :
indices 0 1 2 3 4 5 6
valeurs 3 1 2 5 6 2 4
avant ip i vp

Puis :

indices 0 1 2 3 4 5 6
valeurs 3 1 2 2 6 5 4
avant ip i vp

Enfin, la valeur pivot est inversée avec celle de tab[ip] :

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

La récursion est effectuée sur les sous-tableaux [3, 1, 2, 2] et [5, 6] (la valeur pivot est à sa place définitive).

Complexité

L’efficacité en moyenne est on ϴ(n.log2(n)), mais dans le pire cas la complexité est en O(n²). Cet algorithme n’est donc pas stable.

Le pire cas survient quant la valeur pivot est la plus grande ou petite et que le partage en deux sous tableaux est disproportionné (un seul élément d’un côté, les autres de l’autre).

Code de la fonction de tri

Cette fonction sert d’enveloppe pour initialiser la sous-fonction récursive.

from typing import List
import math #pour le calcul de la complexité théorique

def triRapide(tab: List[int]) -> List[int]:
    """
    trie le tableau selon la méthode du tri rapide, par ordre croissant
    @param tab le tableau de valeurs, en entrée-sortie (par adresse)
    @return le tableau trié par ordre croissant (pour doctests)
    >>> triRapide([])
    []
    >>> triRapide([1])
    [1]
    >>> triRapide([2, 1])
    [1, 2]
    >>> triRapide([1, 3, 2])
    [1, 2, 3]
    >>> triRapide([4, 1, 3, 2])
    [1, 2, 3, 4]
    >>> triRapide([4, 2, 4, 2, 1, 4, 4])
    [1, 2, 2, 4, 4, 4, 4]
    """
    def _triRapide(tab: List[int], inf: int, sup: int):
        cout += 1            #CPLX
        if inf < sup - 1: #cas d'arrêt (condition pour continuer)
            #partition:
            vp = tab[sup - 1]
            ip = inf
            for i in range(inf, sup - 1):
                cout += 1   #CPLX
                if tab[i] < vp: #échange
                    if i != ip: #sauf si c'est inutile (test facultatif)
                        tab[i], tab[ip] = tab[ip], tab[i]
                    ip += 1
            tab[sup - 1], tab[ip] = tab[ip], tab[sup - 1] #pivot
            #division:
            _triRapide(tab, inf, ip)
            _triRapide(tab, ip + 1, sup)
    
    global cout #CPLX
    cout = 0    #CPLX
    _triRapide(tab, 0, len(tab))
    return tab


if __name__ == "__main__":
    import doctest; doctest.testmod()
    
    tab = [4, 7, 4, 8, 5, 9, 6] #meilleur cas
    print("Avec tab =", tab) 
    triRapide(tab)
    print(tab)
    n = len(tab)
    print("- complexité théorique n.log2(n) : " + str(int(n*math.log2(n))))
    print("- complexité pire cas : " + str(int((n**2 - n)/2)))
    print("- complexité effective : " + str(cout))
    
    tab = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] #déjà trié
    print("Avec tab =", tab) 
    triRapide(tab)
    print(tab)
    n = len(tab)
    print("- complexité théorique n.log2(n) : " + str(int(n*math.log2(n))))
    print("- complexité pire cas : " + str(int((n**2 - n)/2)))
    print("- complexité effective : " + str(cout))