from random import *

# Tri rapide

def Tri_Rapide(liste):
    "Trie une liste de nombres de manière croissante"

    Tri_Rapide_Partition(liste, 0, len(liste)-1)
    

def Tri_Rapide_Partition(liste, premier, dernier):
    "Trie une liste en la partitionnant récursivement en sous-listes"
    if premier < dernier:

        cesure = partition(liste, premier, dernier)

        Tri_Rapide_Partition(liste, premier, cesure-1)
        Tri_Rapide_Partition(liste, cesure+1, dernier)


def partition(liste, premier, dernier):
    "Partitionne la liste relativement à un pivot situé en première position"

    pivot = liste[premier]

    gauche = premier + 1
    droite = dernier

    flag = 0

    while flag == 0:

        while gauche <= droite and liste[gauche] <= pivot:
            gauche = gauche + 1

        while droite >= gauche and liste[droite] >= pivot:
            droite = droite - 1

        if droite < gauche:
            flag = 1
        else:
            liste[gauche], liste[droite] = liste[droite], liste[gauche]
            gauche = gauche + 1
            droite = droite - 1

    liste[premier], liste[droite] = liste[droite], liste[premier]

    return droite

### Programme test ###

l = [54, 26, 93, 31, 77, 17, 44, 55, 20, 31]
print(l)
Tri_Rapide(l)
print(l)