# ==========================================================================
#
#  Ce programme permet de mesurer et de tester la complexité temporelle
#  de différents algorithmes de tri :
#     - tri par sélection
#     - tri par insertion
#     - tri à bulles
#     - tri fusion
#     - tri rapide
#     - tri natif dans les méthodes des listes de Python
#
# ==========================================================================
#  Programme réalisé par Jean-Christophe MICHEL
#  Novembre 2022
#  www.gecif.net
# ==========================================================================

import random
from time import time

# ==========================================================================
#  Définition des fonctions :
# ==========================================================================

def tri_insertion(tableau):
    for i in range(1,len(tableau)):
        en_cours = tableau[i]
        j = i
        #décalage des éléments du tableau }
        while j>0 and tableau[j-1]>en_cours:
            tableau[j]=tableau[j-1]
            j = j-1
        #on insère l'élément à sa place
        tableau[j]=en_cours

def tri_selection(tableau):
    nb = len(tableau)
    for en_cours in range(0,nb):
        plus_petit = en_cours
        for j in range(en_cours+1,nb) :
            if tableau[j] < tableau[plus_petit] :
                plus_petit = j
        if min is not en_cours :
            temp = tableau[en_cours]
            tableau[en_cours] = tableau[plus_petit]
            tableau[plus_petit] = temp

def tri_bulle(tableau):
    permutation = True
    passage = 0
    while permutation == True:
        permutation = False
        passage = passage + 1
        for en_cours in range(0, len(tableau) - passage):
            if tableau[en_cours] > tableau[en_cours + 1]:
                permutation = True
                # On echange les deux elements
                tableau[en_cours], tableau[en_cours + 1] = \
                tableau[en_cours + 1],tableau[en_cours]
    return tableau

def fusion(gauche,droite):
    resultat = []
    index_gauche, index_droite = 0, 0
    while index_gauche < len(gauche) and index_droite < len(droite):
        if gauche[index_gauche] <= droite[index_droite]:
            resultat.append(gauche[index_gauche])
            index_gauche += 1
        else:
            resultat.append(droite[index_droite])
            index_droite += 1
    if gauche:
        resultat.extend(gauche[index_gauche:])
    if droite:
        resultat.extend(droite[index_droite:])
    return resultat

def tri_fusion(m):
    if len(m) <= 1:
        return m
    milieu = len(m) // 2
    gauche = m[:milieu]
    droite = m[milieu:]
    gauche = tri_fusion(gauche)
    droite = tri_fusion(droite)
    return list(fusion(gauche, droite))

def tri_rapide(tableau):
    if not tableau:
        return []
    else:
        pivot = tableau[-1]
        plus_petit = [x for x in tableau     if x <  pivot]
        plus_grand = [x for x in tableau[:-1] if x >= pivot]
        return tri_rapide(plus_petit) + [pivot] + tri_rapide(plus_grand)

# ==========================================================================
#  Programme principal
# ==========================================================================

taille=500

print("\nCréation d'une liste mélangée contenant %d éléments ...\n" % taille)

liste=list(range(taille))
random.shuffle(liste)

# tri en place :
liste_malangee=liste[:]
print("Tri par sélection en cours ...")
debut=time()
tri_selection(liste_malangee)
fin=time()
print("Tri par sélection fini en %.2f secondes\n" % (fin-debut))

# tri en place :
liste_malangee=liste[:]
print("Tri par insertion en cours ...")
debut=time()
tri_insertion(liste_malangee)
fin=time()
print("Tri par insertion fini en %.2f secondes\n" % (fin-debut))


# retourne une nouvelle liste triée :
liste_malangee=liste[:]
print("Tri à bulles en cours ...")
debut=time()
liste_triee=tri_bulle(liste_malangee)
fin=time()
print("Tri à bulles fini en %.2f secondes\n" % (fin-debut))

# retourne une nouvelle liste triée :
liste_malangee=liste[:]
print("Tri fusion en cours ...")
debut=time()
liste_triee=tri_fusion(liste_malangee)
fin=time()
print("Tri fusion fini en %.2f secondes\n" % (fin-debut))

# retourne une nouvelle liste triée :
liste_malangee=liste[:]
print("Tri rapide en cours ...")
debut=time()
liste_triee=tri_rapide(liste_malangee)
fin=time()
print("Tri rapide fini en %.2f secondes\n" % (fin-debut))

# tri en place :
liste_malangee=liste[:]
print("Tri Python en cours ...")
debut=time()
liste_malangee.sort()
fin=time()
print("Tri Python fini en %.2f secondes\n" % (fin-debut))


"""
Exemple de résultat obtenu :

Création d'une liste mélangée contenant 50000 éléments ...

Tri par sélection en cours ...
Tri par sélection fini en 373.52 secondes

Tri par insertion en cours ...
Tri par insertion fini en 495.81 secondes

Tri à bulles en cours ...
Tri à bulles fini en 947.08 secondes

Tri fusion en cours ...
Tri fusion fini en 0.83 secondes

Tri rapide en cours ...
Tri rapide fini en 0.38 secondes

Tri Python en cours ...
Tri Python fini en 0.03 secondes
"""