###############################################################################
# Tri par insertion : temps quadratique dans tous les cas sauf ceux vraiment
# favorables
###############################################################################
def insertion(table):
    for i in range(0, len(table)):
        # Invariant de boucle : les cellules avant i sont triées, il s'agit
        # maintenant d'insérer table[i] à sa place

        t_i = table[i]
        j = i-1
        while j >= 0 and table[j] > t_i:
            # Invariant de boucle : les cellules après j sont triées et plus
            # grandes que t_i
            table[j+1] = table[j]
            j -= 1
        table[j+1] = t_i

    return table

###############################################################################
# Tri par sélection : temps quadratique dans tous les cas
###############################################################################
def selection(table):
    for i in range(0, len(table)-1):
        # Invariant de boucle : les cellules avant i sont triées et contiennent
        # les i plus petits éléments de table

        for j in range(i+1, len(table)):
            # Invariant de boucle : table[i] contient le plus petit élément des
            # cellules comprises entre i (inclus) et j (exclus)

            if table[j] < table[i]:
                table[i], table[j] = table[j], table[i]
    return table

###############################################################################
# Tri à bulle : quadratique dans le cas le pire
###############################################################################
def bubble(table):
    last = len(table)-1

    while last > 0:
        # invariant de boucle : toutes les cellules après last (exclus) sont
        # déjà triées et contiennent les n - last plus grands éléments de table

        bubble = 0

        for i in range(0, last):
            # invariant de boucle : table[i] contient le plus grand élément de
            # toutes les cellules avant i ; bubble contient la dernière bulle,
            # c'est à dire la dernière cellule que l'on a modifiée
            if table[i] > table[i+1]:
                table[i], table[i+1] = table[i+1], table[i]
                bubble = i+1

        last = bubble

    return table

###############################################################################
# Tri rapide : quasilinéaire en moyenne, quadratique dans le cas le pire
###############################################################################
def quicksort(table):
    # Fonctions auxilliaires (le programme est après les définitions de
    # fonctions auxiliaires)
    def do_quicksort(table, first, last):
        """La fonction principale de tri : implémente la stratégie divide and
        conquer"""

        # print("---->", first, last, table[first:last+1])
        pivot = choose_pivot(table, first, last)
        pivot = partition(table, first, last, pivot)
        # print(pivot, "<--", first, last, table[first:last+1])

        if first < pivot-1:
            do_quicksort(table, first, pivot-1)
        if pivot+1 < last:
            do_quicksort(table, pivot+1, last)

    def partition(table, first, last, pivot):
        """Partitionne table en mettant au début les éléments < table[pivot], à
        la fin ceux >= table[pivot] et enfin table[pivot] entre les deux ;
        retourne la nouvelle position du pivot"""

        # On commence par mettre le pivot dans la première cellule
        table[first], table[pivot] = table[pivot], table[first]

        i, j = first+1, last
        if i > j:
            # first+1 > last : cette table a un seul élément
            return first
        elif i == j:
            # first+1 == last : cette table a deux éléments
            if table[i] < table[first]:
                table[first], table[i] = table[i], table[first]
                return i
            else:
                return first

        # Si on arrive ici c'est que i < j ; on fait une boucle a priori
        # infinie mais heureusement des sorties (par appel à return) sont
        # prévues dans le corps de boucle
        while True:
            # Invariant de boucle : les cellules avant i (exclus) contiennent
            # des valeurs <= table[first] et table[first] est le plus grand
            # d'entre eux ; les cellules après j (exclus) contiennent des
            # valeurs >= table[first]

            # On va au premier élément après i (inclus) qui est > table[first],
            # mais attention à ne pas dépasser j
            while table[i] <= table[first]:
                # Invariant de boucle : toutes les cellules avant i (inclus)
                # ont des valeurs <= table[first]
                i = i+1
                if i == j:
                    if table[i] > table[first]:
                        i = i-1
                    table[first], table[i] = table[i], table[first]
                    return i

            # Si on arrive ici c'est que on a encore i < j : on va au premier
            # élément avant j (inclus) qui est < j, mais attention à ne pas
            # passer avant i
            while table[j] >= table[first]:
                # Invariant de boucle : toutes les cellules après j (inclus)
                # ont des valeurs >= table[first]
                j = j-1
                if i == j:
                    table[first], table[i-1] = table[i-1], table[first]
                    return i-1

            # Si on arrive ici alors on a : i < j ; tous les éléments avant i
            # (exclus) sont <= table[first] mais table[i] > table[first] ; tous
            # les éléments après j (exclus) sont >= table[first] mais table[j]
            # < table[first].
            table[i], table[j] = table[j], table[i]
            i, j = i+1, j-1

            # Vérification que i et j ne se sont pas croisés
            if i > j:
                table[first], table[i-1] = table[i-1], table[first]
                return i-1
            elif i == j:
                if table[i] > table[first]:
                    i = i-1
                table[first], table[i] = table[i], table[first]
                return i

    def choose_pivot(table, first, last):
        """Choix du pivot"""

        # On se contente de retourner la première cellule
        return first

    # Lancement du programme
    do_quicksort(table, 0, len(table)-1)
    return table


###############################################################################
# Tri fusion : quasilinéaire mais contrairement aux précédents il ne s'agit pas
# d'un tri "en place" c'est à dire que les éléments triés sont placés dans une
# nouvelle liste, le tableau original n'est pas modifié
###############################################################################
def fusion(table):
    # fonction principale : encore une fois on fait du divide and conquer
    def do_fusion(table, first, length):
        if length <= 1:
            return table[first:first+length]
        else:
            half = length//2
            table1 = do_fusion(table, first, half)
            table2 = do_fusion(table, first+half, length-half)
            return merge(table1, table2)

    def merge(table1, table2):
        """table1 et table2 sont des tablees triées : retourne une nouvelle
        table contenant les éléments de table1 et table2 dans l'ordre"""

        len1 = len(table1)
        len2 = len(table2)
        i = j = 0
        table = []

        while True:
            # invariant de boucle : i < len1, j < len2, les éléments de table1
            # avant i et les éléments de table2 avant j sont triés dans table
            if table1[i] <= table2[j]:
                table.append(table1[i])
                i = i+1
                if i == len1:
                    # On est au bout de table1 ; on copie la fin de table2 dans
                    # table
                    while j < len2:
                        table.append(table2[j])
                        j = j+1
                    return table
            else:
                table.append(table2[j])
                j = j+1
                if j == len2:
                    # On est au bout de table2 ; on copie la fin de table1 dans
                    # table
                    while i < len1:
                        table.append(table1[i])
                        i = i+1
                    return table

    return do_fusion(table, 0, len(table))


def benchmarks(sort, list_size, num_iter = 10000):
    import time
    import random

    print("list size = ", list_size)
    test_list = [None] * list_size

    count = 0
    random_time = 0
    sort_time = 0

    while count < num_iter:
        before_random = time.time()
        for i in range(0, list_size):
            test_list[i] = random.randint(0, 100)
        after_random = time.time()
        random_time += after_random - before_random

        before_sort = time.time()
        sort(test_list)
        after_sort = time.time()
        sort_time += after_sort - before_sort

        count += 1
        if count % 100 == 0:
            print("random = %.4f, sort = %.4f" % (random_time, sort_time))

    return (random_time, sort_time)