Quelques algorithmes de tri en Python

Ce billet date de plusieurs années, ses informations peuvent être devenues obsolètes.

Aujourd'hui on poursuit un voyage que j'ai entamé dans la science du computer avec quelques notes sur les algorithmes de tri de tableaux.

Il y a beaucoup de ressources en lignes qui permettent de comprendre. Il y a notamment le Swift Algorithm Club qui est très pédagogue. Il existe un dépôt un peu similaire en Python mais avec moins d'explications.

Au menu du jour : Bubble Sort, Quick Sort et Merge Sort.

Au passage, CPython utilise le Timsort depuis 2002. En JavaScript, V8 aussi à partir de sa v7.0 depuis fin 2018.

Vu l'avance de Python, je vais l'utiliser pour ce billet :D

Bubble Sort

Le tri à bulles est un algorithme vieux et lent, mais c'est aussi le plus simple à comprendre, ce qui en fait une bonne entrée en matière.

L'idée est de comparer chaque élément du tableau avec tous les autres. On compare l'élément avec son voisin. La plus petite valeur est permutée à gauche. La comparaison continue jusqu'à la fin du tableau de façon à ce que la plus grande valeur se retrouve à la fin. À la seconde itération, on recommence sur la longueur du tableau moins 1 élément, car on sait que la plus grande valeur est déjà en place. À la troisième itération, on recommence sur la longueur du tableau moins 2 éléments etc.

Pour les explications, je comprends toujours mieux avec un exemple visuel :

If you give this gentleman a few cups, he can save our world…

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j + 1], arr[j] = arr[j], arr[j + 1]
    return arr

La source du code vient de là. Dans cette implémentation, j'aime bien l'utilisation de range avec un pas négatif. Il ne faut pas oublier d'enlever 1 à len(arr) dans la boucle extérieure pour pouvoir accéder à l'élément suivant sans encombre dans la boucle intérieure : arr[j + 1]. Le tri est fait sur-place, c'est à dire que le tableau en entrée est muté, de quoi alimenter quelques conversations avec des fans d'immutabilité.

Quicksort

La clé de cet algorithme est la récursivité. Le tri rapide fonctionne de la manière suivante :

  • un élément du tableau est choisi en tant que pivot
  • les autres éléments du tableau sont permutés en fonction de ce pivot : tout ce qui est plus petit d'un côté, tout ce qui est plus grand de l'autre
  • on obtient un tri partiel
  • on recommence ces étapes de façon récursive sur les partitions obtenues

Ce qui pourrait donner ça :

def quick_sort(arr):

    if len(arr) < 2:
        return arr

    pivot_index = len(arr) - 1
    pivot = arr[pivot_index]

    lesser = [item for item in arr[:pivot_index] if item <= pivot]
    greater = [item for item in arr[:pivot_index] if item > pivot]

    return quick_sort(lesser) + [pivot] + quick_sort(greater)

Sauf que ça n'est pas efficace écrit comme ça. À chaque passage dans la fonction, des nouvelles instances de tableaux sont créés au moment de la partition et stockées dans la pile d'exécution.

Il y a mieux à faire au niveau de la complexité algorithmique et des méthodes de partition comme celle de Lomuto sont basées sur la mutation du tableau en entrée.

Voyez cette explication visuelle qui est presque identique au code qui va suivre :

def quicksort(arr, lo=0, hi=None):

    if hi is None:
        hi = len(arr) - 1

    # Il nous faut au moins 2 éléments.
    if lo < hi:

        # `p` est la position du pivot dans le tableau après partition.
        p = partition(arr, lo, hi)

        # Tri récursif des 2 parties obtenues.
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)

    return arr

def partition(arr, lo, hi):

    # Choisir le dernier élément en tant que pivot.
    pivot_index = hi

    # `l` (comme less) sert à trouver la place du pivot dans le tableau.
    l = lo

    # Bien exclure `hi` lors de l'itération car c'est le pivot.
    for i in range(lo, hi):
        if arr[i] <= arr[pivot_index]:
            # Les éléments plus petit que le pivot passent à gauche.
            swap(arr, i, l)
            l = l + 1

    # Déplacer le pivot à sa bonne position.
    swap(arr, l, pivot_index)

    return l

def swap(arr, left, right):
    arr[left], arr[right] = arr[right], arr[left]

Vous pouvez comparer l'espace consommé par les deux façons de faire en visualisant la pile d'exécution de Python, c'est assez funky.

Merge Sort

Là encore, la clé est la récursivité.

Le tri fusion repose sur le fait qu'il est facile de construire à partir de deux listes déjà triées A et B une autre liste triée C.

Il suffit d'identifier de façon répétée les plus petites valeurs dans A et B et de les fusionner au fur et à mesure dans C.

Puisque les listes A et B sont triées, la valeur minimale de A est inférieure à toutes les autres valeurs de A, et la valeur minimale de B est inférieure à toutes les autres valeurs de B. Si la valeur minimale de A est inférieure à la valeur minimale de B, alors elle doit également être inférieure à toutes les valeurs de B. Par conséquent, elle est inférieure à toutes les autres valeurs de A et toutes les valeurs de B.

L'objectif est donc d'avoir deux listes déjà triées. Pour cela, le tableau en entrée est séparé en groupes jusqu'à ce qu'il ne reste plus qu'un élément dans chaque groupe et aucun doute sur le tri.

def mergesort(arr):

    if len(arr) == 1:
        return arr

    middle = len(arr) // 2
    a = mergesort(arr[:middle])
    b = mergesort(arr[middle:])
    return merge(a, b)

def merge(a, b):

    c = []

    while len(a) and len(b):
        if a[0] < b[0]:
            c.append(a[0])
            a.remove(a[0])
        else:
            c.append(b[0])
            b.remove(b[0])

    c.extend(a) if len(a) else c.extend(b)

    return c

L'exemple ci-dessus est bien lisible mais pas idéal au niveau de la complexité algorithmique puisque à chaque passage on va créer plusieurs tableaux et en plus la suppression d'un élément dans une liste est une opération qui dure O(n).

Pour améliorer ça, on peut passer chaque tableau obtenu de façon récursive dans mergesort à la fonction merge. Au sein de cette dernière, on va alors utiliser 3 index pour suivre la progression dans les 3 tableaux qui lui sont passés en entrée et muter le tableau principal :

def mergesort(arr):

    if len(arr) == 1:
        return arr

    middle = len(arr) // 2
    a = mergesort(arr[:middle])
    b = mergesort(arr[middle:])
    return merge(arr, a, b)

def merge(arr, a, b):

    i = 0
    j = 0
    k = 0

    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            arr[k] = a[i]
            i += 1
        else:
            arr[k] = b[j]
            j += 1
        k += 1

    while i < len(a):
        arr[k] = a[i]
        i += 1
        k += 1

    while j < len(b):
        arr[k] = b[j]
        j += 1
        k += 1

    return arr

Avant Les fermetures en JavaScript Après Un Arbre Binaire de Recherche en Python

Tag Kemar Joint