Tri rapide

Le tri rapide est une application du principe diviser pour régner. Il consiste

• à choisir un élément du tableau à trier comme pivot ;
• à séparer le tableau à trier en deux sous-tableaux contenant respectivement les éléments inférieurs et supérieurs au pivot ;
• et à répéter le processus sur les deux sous-tableaux.

Comme tout algorithme du type diviser pour régner, le tri rapide se prête bien à une implémentation récursive.

Python

    from numpy.random import choice

    def tri_rapide(tab):
        if len(tab) == 0:
            return []
        pivot = choice(tab)     # Choix aléatoire d'un élément comme pivot
        t1, t2, t3 = [], [], []
        for x in tab:
            if x < pivot:
                t1.append(x)
            elif x > pivot:
                t2.append(x)
            else:
                t3.append(x)
        return tri_rapide(t1) + t3 + tri_rapide(t2)

Python

    from numpy.random import randint

    tab = randint(100, size=10)
    tab
    tri_rapide(tab)

L'algorithme précédent crée une nouvelle liste à chaque appel de la fonction :code:tri_rapide. D'un point de vue de l'utilisation de la mémoire, on peut préférer effectuer un tri en place : on modifie le tableau au cours de l'algorithme de tri.

Python

    def partition(tab, g, d, p):
        j = g
        tab[p], tab[d] = tab[d], tab[p]
        for i in range(g, d):
            if tab[i] <= tab[d]:
                tab[i], tab[j] = tab[j], tab[i]
                j += 1
        tab[d], tab[j] = tab[j], tab[d]
        return j


    def tri_rapide(tab, g=0, d=None):
        if d == None:
            d = len(tab) - 1
        if g < d:
            p = randint(g, d + 1)
            pp = partition(tab, g, d, p)
            tri_rapide(tab, g, pp - 1)
            tri_rapide(tab, pp + 1, d)