# ==========================================================================
#
#  Ce programme permet de mesurer et de tester la complexité temporelle
#  de 14 algorithmes de tri différents :
#     - tri par sélection
#     - tri par insertion
#     - tri à bulles
#     - tri à bulles bidirectionnel (tri "shaker", ou tri "Cocktail", ou tri "Shuttle")
#     - tri à peigne
#     - tri à peigne bidirectionnel (tri "oyelami" : mélange de tri à peigne et tri shaker)
#     - tri shell (une variante du tri par insertion : on trie séparément des sous-suites)
#     - tri gnome (tri par insertion avec des permutations comme dans le tri à bulles)
#     - tri fusion (diviser pour mieux régner)
#     - tri rapide (utilise un pivot)
#     - tri avec la fonction sorted() de Python
#     - tri natif avec la méthode sort() des listes de Python
#     - tri par extraction du parcourt en profondeur dans l'ordre infixe d'un arbre binaire de recherche
#     - tri maximier ou "tri par tas" (création d'un arbre binaire dont le parcourt en largeur donne les noeuds dans l'ordre croissant)
#
# ==========================================================================
#  Programme réalisé par Jean-Christophe MICHEL
#  Novembre 2024
#  www.gecif.net
# ==========================================================================

import random
import math
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 tri_peigne(tableau):
    permutation = True
    gap = len(tableau)
    while (permutation == True) or  (gap>1):
        permutation = False
        gap = math.floor(gap / 1.3)
        if gap<1: gap = 1
        for en_cours in range(0, len(tableau) - gap):
            if tableau[en_cours] > tableau[en_cours + gap]:
                permutation = True
                # On echange les deux elements
                tableau[en_cours], tableau[en_cours + gap] = \
                tableau[en_cours + gap],tableau[en_cours]
    return tableau

#---------------------------------------------------------------------------

def tri_shaker(tableau):
    permutation,sens,en_cours = True,1,0
    debut,fin = 0,len(tableau)-2
    while permutation == True:
        permutation = False
        while (en_cours<fin and sens==1) or \
        (en_cours>debut and sens==-1) :
            # Test si echange
            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]
            en_cours = en_cours + sens
        # On change le sens du parcours
        if sens==1:
            fin = fin - 1
        else:
            debut = debut + 1
        sens = -sens
    return tableau

#---------------------------------------------------------------------------

def tri_oyelami(tableau):
    fin = len(tableau)
    for i in range(fin // 2):
        if tableau[i] > tableau[fin - i - 1]:
            tableau[i], tableau[fin - i - 1] = tableau[fin - i - 1],tableau[i]
    permutation,sens,en_cours = True,1,0
    debut,fin = 0,len(tableau)-2
    while permutation == True:
        permutation = False
        while (en_cours<fin and sens==1) or \
        (en_cours>debut and sens==-1) :
            # Test si echange
            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]
            en_cours = en_cours + sens
        # On change le sens du parcours
        if sens==1:
            fin = fin - 1
        else:
            debut = debut + 1
        sens = -sens
    return tableau

#---------------------------------------------------------------------------

def tri_insertion_2(tableau, gap, debut):
    # cette fonction tri_insertion_2 est utiloisée par la fonction tri_shell
    for i in range(gap + debut,len(tableau),gap):
        en_cours = tableau[i]
        j = i
        #décalage des éléments du tableau }
        while j>0 and tableau[j-gap]>en_cours:
            tableau[j]=tableau[j-gap]
            j = j-gap
        #on insère l'élément à sa place
        tableau[j]=en_cours

def tri_shell(tableau):
    for gap in [6,4,3,2,1]:
        # Pour chaque sous-tableau ...
        for debut in range(0,gap):
            #... on fait un tri par insertion
            tri_insertion_2(tableau,gap,debut)

#---------------------------------------------------------------------------

def tri_gnome(tableau):
    i_b,i_i,taille = 1,2,len(tableau)
    while i_b < taille:
        if tableau[i_b-1] <= tableau[i_b]:
            i_b,i_i = i_i, i_i+1
        else:
            tableau[i_b-1],tableau[i_b] = tableau[i_b],tableau[i_b-1]
            i_b -= 1
            if i_b == 0:
                i_b,i_i = i_i, i_i+1
    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)

#---------------------------------------------------------------------------
# tri maximier ou tri par tas : arbre binaire dont le parcourt en largeur donne les noeuds dans l'ordre croissant
def faire_tas(tab, debut, n):
# transforme le tableau "tab" en un tas
    racine = debut
    while racine*2 + 1 < n:
        fils = racine*2 + 1
        if fils < n-1 and tab[fils] < tab[fils+1]:
            fils += 1
        if tab[racine] < tab[fils]:
            tab[racine], tab[fils] = tab[fils], tab[racine]
            racine = fils
        else:
            return

def tri_par_tas(tab):
    n = len(tab)
    debut = n//2 - 1
    fin = n - 1
    while debut >= 0:
        faire_tas(tab, debut, n)
        debut -= 1
    while fin > 0:
        tab[fin], tab[0] = tab[0], tab[fin]
        faire_tas(tab, 0, fin)
        fin -= 1
    return tab

#---------------------------------------------------------------------------
# Tri d'une liste par extraction du parcourt en profondeur dans l'ordre infixe d'un arbre binaire de recherche :

def inserer(x,t):
    # ajoute la feuille x dans l'ABR t (renvoie un nouvel ABR sans modifier t)
    if t==None:
        return (x,None,None)
    else:
        y,u,v=t[0],t[1],t[2]
        if x<=y:
            return (y,inserer(x,u),v)
        else:
            return (y,u,inserer(x,v))

def parcours_infixe(t): # G, R, D
    if t==None:
        return []
    else:
        x,u,v=t[0],t[1],t[2]
        return parcours_infixe(u)+[x]+parcours_infixe(v)

def liste_vers_arbre(s):
    t=None # crée un arbre vide
    for x in s:
        t=inserer(x,t) # ajoute chaque élément de la liste s dans l'ABR t
    return t

def tri_par_abr(s):
    return parcours_infixe(liste_vers_arbre(s)) # retourne le parcours infixe de l'ABR

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

taille=10000

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 à bulles bidirectionnel (shaker) en cours ...")
debut=time()
liste_triee=tri_shaker(liste_malangee)
fin=time()
print("Tri à bulles bidirectionnel (shaker) fini en %.2f secondes\n" % (fin-debut))

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

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

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

# tri en place :
liste_malangee=liste[:]
print("Tri gnome en cours ...")
debut=time()
tri_gnome(liste_malangee)
fin=time()
print("Tri gnome 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))

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

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

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

# retourne une nouvelle liste triée :
liste_malangee=liste[:]
print("Extraction du parcourt en profondeur infixe d'un ABR en cours ...")
debut=time()
liste_triee=tri_par_abr(liste_malangee)
fin=time()
print("Extraction du parcourt en profondeur infixe d'un ABR fini en %.2f secondes\n" % (fin-debut))

"""
Exemples de résultats obtenus :

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

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

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

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

Tri à bulles bidirectionnel (shaker) en cours ...
Tri à bulles bidirectionnel (shaker) fini en 49.83 secondes

Tri à peigne en cours ...
Tri à peigne fini en 0.20 secondes

Tri oyelami en cours ...
Tri oyelami fini en 35.47 secondes

Tri shell en cours ...
Tri shell fini en 4.02 secondes

Tri gnome en cours ...
Tri gnome fini en 36.94 secondes

Tri fusion en cours ...
Tri fusion fini en 0.23 secondes

Tri rapide en cours ...
Tri rapide fini en 0.11 secondes

Tri avec la fonction sorted() de Python en cours ...
Tri avec la fonction sorted() de Python fini en 0.00 secondes

Tri avec la méthode sort() de Python en cours ...
Tri avec la méthode sort() de Python fini en 0.02 secondes

Tri par tas en cours ...
Tri par tas fini en 0.27 secondes

Extraction du parcourt en profondeur infixe d'un ABR en cours ...
Extraction du parcourt en profondeur infixe d'un ABR fini en 0.22 secondes

=============================================================================

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

=============================================================================

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

Tri par sélection en cours ...
Tri par sélection fini en 1890.72 secondes (31 minutes)

Tri par insertion en cours ...
Tri par insertion fini en 2174.35 secondes (36 minutes)

Tri à bulles en cours ...
Tri à bulles fini en 3908.55 secondes (1 heure 05 minutes)

Tri fusion en cours ...
Tri fusion fini en 1.39 secondes

Tri rapide en cours ...
Tri rapide fini en 0.65 secondes

Tri Python en cours ...
Tri Python fini en 0.08 secondes

"""