# -*- coding: utf-8 *-*

###############################################################################
#                    Tri sélection
###############################################################################

def bad_sort(l):
    """
Très mauvais algorithme de tri (en place) : quadratique dans tous les cas
    """
    for i in range(0, len(l)):
        i_min = i
        for j in range(i+1, len(l)):
            if l[j] < l[i_min]:
                i_min = j
        (l[i], l[i_min]) = (l[i_min], l[i])


###############################################################################
#                    Tri à bulles
###############################################################################

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 fusion
###############################################################################

def fusion(l):
    """
Tri fusion : nlog n dans tous les cas
"""
    if len(l) <= 1:
        return l
    else:
        middle = len(l)/2
        # On trie les deux moitiés de la liste
        l1 = fusion(l[0:middle])
        l2 = fusion(l[middle:])
        # Et on fusionne
        return merge(l1, l2)

def merge(l1, l2):
    """
Fusion de deux listes triées
"""
    # Préallocation de la liste fusionnée
    merged = [None] * (len(l1)+len(l2))
    i = 0 # indice dans la liste l1
    j = 0 # indice dans la liste l2
    k = 0 # indice dans la liste fusionnée

    while i < len(l1) and j < len(l2):
        if l1[i] < l2[j]:
            merged[k] = l1[i]
            i += 1
        else:
            merged[k] = l2[j]
            j += 1
        k += 1
    if i < len(l1):
        while i < len(l1):
            merged[k] = l1[i]
            i += 1
            k += 1
    else:
        while j < len(l2):
            merged[k] = l2[j]
            j += 1
            k += 1
    return l


###############################################################################
#                    Tri rapide
###############################################################################

def quicksort(table):
    """
Tri rapide: nlog n en moyenne, quadratique dans le cas le pire. Tri en place:
c'est le tableau table passé en argument qui est trié et retourné.
    """
    do_quicksort(table, 0, len(table)-1)
    return table

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 = first
    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


###############################################################################
#                    Temps d'exécution
###############################################################################

# Fonction qui prend en argument une fonction de tri (paramètre sort)
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 # Temps consacré au tirage d'une liste au hasard
    sort_time = 0   # Temps de tri (fonction sort())

    while count < num_iter:
        # D'abord on tire une liste au hasard
        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

        # Ensuite on la tri
        before_sort = time.time()
        sort(test_list)
        after_sort = time.time()
        sort_time += after_sort - before_sort

        count += 1

        # Toutes les 100 itérations on affiche un petit compte-rendu
        if count % 100 == 0:
            print "random = %.4f, sort = %.4f" % (random_time, sort_time)

    return (random_time, sort_time)