human
Implémentez un algorithme de tri rapide avec Pytho
gpt
Le tri rapide est un algorithme de diviser pour régner. Il choisit un élément comme pivot et partitionne le tableau donné autour du pivot choisi. Il existe différentes variations du tri rapide, qui diffèrent par la façon dont le pivot est choisi. Voici une implémentation qui utilise le dernier élément du tableau comme pivot :

```
# Implémentation Python du tri rapide

def partitionner(tableau, bas, haut):

    # choisir l'élément le plus à droite comme pivot
    pivot = tableau[haut]
    # pointeur pour l'élément plus grand
    i = bas - 1

    # parcourir tous les éléments
    # comparer chaque élément avec le pivot
    for j in range(bas, haut):
        if tableau[j] <= pivot:
            # Si un élément plus petit que le pivot est trouvé
            # l'échanger avec l'élément plus grand pointé par i
            i = i + 1

            # Échanger l'élément à la position i avec l'élément à la position j
            (tableau[i], tableau[j]) = (tableau[j], tableau[i])

    # Échanger l'élément pivot avec l'élément plus grand spécifié par i
    (tableau[i + 1], tableau[haut]) = (tableau[haut], tableau[i + 1])

    # Retourner la position à partir de laquelle la partition est effectuée
    return i + 1


def tri_rapide(tableau, bas, haut):
    if bas < haut:
        # Trouver l'élément pivot de telle sorte que
        # les éléments plus petits que le pivot soient à gauche
        # les éléments plus grands que le pivot soient à droite
        pi = partitionner(tableau, bas, haut)

        # Appel récursif sur la partie gauche du pivot
        tri_rapide(tableau, bas, pi - 1)

        # Appel récursif sur la partie droite du pivot
        tri_rapide(tableau, pi + 1, haut)


# Exemple de test
donnees = [1, 7, 4, 1, 12, 8, -3]
print("Tableau non trié")
print(donnees)

taille = len(donnees)

tri_rapide(donnees, 0, taille - 1)

print('Tableau trié par ordre croissant :')
print(donnees)
```

Le code ci-dessus affichera la sortie suivante :

```
Tableau non trié
[1, 7, 4, 1, 12, 8, -3]

Tableau trié par ordre croissant :
[-3, 1, 1, 4, 7, 8, 12]
```

Cet algorithme a une complexité temporelle dans le pire des cas de O(N^2), mais sa complexité temporelle moyenne est de O(N log N). De plus, l'algorithme ne nécessite qu'un espace auxiliaire de O(1), en plus de l'espace O(N) consommé par le tableau lui-même.