Les notebooks du répertoire documents sont maintenant en lecture seule :

  • Vous pouvez tester/exécuter le code comme vous voulez (Shift-Entrée ou Ctrl-Entrée)
  • Mais vous ne pouvez pas enregistrer directement : utilisez le menu Fichier > Créer une copie... ou Fichier > Save as...
  • Rappel : si le noyau Python/Ocaml "plante" : menu Noyau > Redémarrer
  • En général, pensez à évaluer la ou les premières cellules (modules, types, définitions pratiques...) : sinon vous aurez des erreurs (... not defined, unbound value ...)

N'hésitez pas à me poser des questions en cas de problème !

Algorithmes de Tri

In [2]:
# Juste pour l'affichage ; pas à connaître

from IPython.display import display, HTML

def table(t, rouge=(), vert=(), bleu=()):
    # Couleurs : <https://clrs.cc/>
    s = ["<table style='font-size:130%'>", "<tr>"]
    for i, x in enumerate(t):
        couleur = "#2ECC40" if i in vert else ""
        if i in rouge: couleur = "#FF4136"
        if i in bleu: couleur = "#0074D9"
        s.extend(['<td bgcolor="{}">'.format(couleur), str(x), '</td>'])
    s.extend(["</tr>", "</table>"])
    return s

def affiche(*args, **kwargs):
    display(HTML(''.join(table(*args, **kwargs))))

Tri par insertion

  • Complexité : $O(n^2)$
  • en place, adaptatif, stable
In [3]:
def tri_insertion(t):
    for i in range(len(t)):
        j = i
        while j > 0 and t[j]<t[j-1]:
            t[j], t[j-1] = t[j-1], t[j]
            j = j-1
            
def tri_insertion_affiche(t):
    """
    Vert/Bleu : zone déjà triée (invariant)
    Bleu : éléments comparés/échangés
    Rouge : prochain élément à insérer
    """
    affiche(t, [0], [])
    for i in range(len(t)):
        j = i
        while j > 0 and t[j]<t[j-1]:
            t[j], t[j-1] = t[j-1], t[j]
            j = j-1
        affiche(t, [i+1], range(i+1), range(j, i+1))
In [4]:
u = [2, 7, 3, 1, 4, 6, 5]
tri_insertion_affiche(u)
2731465
2731465
2731465
2371465
1237465
1234765
1234675
1234567
In [5]:
import random
v = [random.randrange(0, 100) for i in range(10)]
tri_insertion_affiche(v)
v
33719797996889995732
33719797996889995732
33719797996889995732
33719797996889995732
33719797996889995732
33719797996889995732
33687197979989995732
33687189979799995732
33687189979799995732
33576871899797999932
32335768718997979999
Out[5]:
[32, 33, 57, 68, 71, 89, 97, 97, 99, 99]

Tri sélection

In [6]:
def pos_maxi(t, n):
    pos = 0
    for i in range(n):
        if t[i] > t[pos]:
            pos = i
    return pos

def tri_selection(t):
    for j in range(len(t), 0, -1):
        p = pos_maxi(t, j)
        t[j-1], t[p] = t[p], t[j-1]
        
def tri_selection_affiche(t):
    """
    Vert/Bleu : zone déjà triée (invariant)
    Bleu : éléments comparés/échangés
    Rouge : prochain élément à insérer
    """
    affiche(t, rouge=[len(t)-1])
    for j in range(len(t), 0, -1):
        p = pos_maxi(t, j)
        t[j-1], t[p] = t[p], t[j-1]
        affiche(t, [j-2], range(j, len(t)), [j-1, p])
In [7]:
v = [random.randrange(0, 100) for i in range(10)]
tri_selection_affiche(v)
067977824320327458
067977584320327482
067477584320327982
067432584320777982
062032584374777982
062032435874777982
062032435874777982
062032435874777982
062032435874777982
062032435874777982
062032435874777982
In [15]:
w = [(random.randrange(0, 10), random.choice('ABCDE')) for i in range(10)]
print(w)
tri_selection_affiche(w)
print(w)
[(6, 'B'), (0, 'E'), (4, 'C'), (0, 'D'), (7, 'E'), (9, 'A'), (9, 'B'), (6, 'E'), (3, 'D'), (2, 'A')]
(6, 'B')(0, 'E')(4, 'C')(0, 'D')(7, 'E')(9, 'A')(9, 'B')(6, 'E')(3, 'D')(2, 'A')
(6, 'B')(0, 'E')(4, 'C')(0, 'D')(7, 'E')(9, 'A')(2, 'A')(6, 'E')(3, 'D')(9, 'B')
(6, 'B')(0, 'E')(4, 'C')(0, 'D')(7, 'E')(3, 'D')(2, 'A')(6, 'E')(9, 'A')(9, 'B')
(6, 'B')(0, 'E')(4, 'C')(0, 'D')(6, 'E')(3, 'D')(2, 'A')(7, 'E')(9, 'A')(9, 'B')
(6, 'B')(0, 'E')(4, 'C')(0, 'D')(2, 'A')(3, 'D')(6, 'E')(7, 'E')(9, 'A')(9, 'B')
(3, 'D')(0, 'E')(4, 'C')(0, 'D')(2, 'A')(6, 'B')(6, 'E')(7, 'E')(9, 'A')(9, 'B')
(3, 'D')(0, 'E')(2, 'A')(0, 'D')(4, 'C')(6, 'B')(6, 'E')(7, 'E')(9, 'A')(9, 'B')
(0, 'D')(0, 'E')(2, 'A')(3, 'D')(4, 'C')(6, 'B')(6, 'E')(7, 'E')(9, 'A')(9, 'B')
(0, 'D')(0, 'E')(2, 'A')(3, 'D')(4, 'C')(6, 'B')(6, 'E')(7, 'E')(9, 'A')(9, 'B')
(0, 'D')(0, 'E')(2, 'A')(3, 'D')(4, 'C')(6, 'B')(6, 'E')(7, 'E')(9, 'A')(9, 'B')
(0, 'D')(0, 'E')(2, 'A')(3, 'D')(4, 'C')(6, 'B')(6, 'E')(7, 'E')(9, 'A')(9, 'B')
[(0, 'D'), (0, 'E'), (2, 'A'), (3, 'D'), (4, 'C'), (6, 'B'), (6, 'E'), (7, 'E'), (9, 'A'), (9, 'B')]

Tri fusion

In [8]:
# Juste pour l'affichage ! Pas à connaître

def trace(f):   
    from IPython.display import display, SVG
    import graphviz
    
    def show_trace():
        s = ['digraph Trace {', 'node [shape=rectangle]', 'None [style=invis]']
        nodes = []
        for caller, current, label in trace.graph:
            s.append('{}  [label="{}"]'.format(current, label))
            s.append('{}->{}'.format(caller, current))
        s.extend('}')
        trace.graph[:]=[]
        trace.compteur=0
        display(SVG(graphviz.Source('\n'.join(s), engine='dot')._repr_svg_()))
        
    def g(*args):
        caller = None if trace.stack==[] else trace.stack[-1]
        trace.compteur += 1
        callee = trace.compteur
        trace.stack.append(callee)
        res = f(*args)
        trace.graph.append((caller, callee, "{}{} = {}".format(f.__name__, args, res)))
        trace.stack.pop()
        if trace.stack==[]:
            show_trace()
        return res
    
    trace.stack = []
    trace.graph = []
    trace.compteur = 0
    return g
In [9]:
#@trace
def fusion(u, v):
    res, i, j = [], 0, 0
    while i < len(u) and j < len(v):
        if u[i] < v[j]:
            res.append(u[i])
            i += 1
        else:
            res.append(v[j])
            j += 1
    return res+u[i:]+v[j:]

@trace
def tri_fusion(t):
    n = len(t)
    if n < 2:
        return t
    return fusion(tri_fusion(t[:n//2]), tri_fusion(t[n//2:]))
In [10]:
import random
v = [random.randrange(0, 100) for _ in range(6)]
print(v)
tri_fusion(v)
[76, 0, 72, 24, 6, 47]
Trace 1 tri_fusion([76, 0, 72, 24, 6, 47],) = [0, 6, 24, 47, 72, 76] None->1 3 tri_fusion([76],) = [76] 2 tri_fusion([76, 0, 72],) = [0, 72, 76] 2->3 4 tri_fusion([0, 72],) = [0, 72] 2->4 5 tri_fusion([0],) = [0] 4->5 6 tri_fusion([72],) = [72] 4->6 1->2 7 tri_fusion([24, 6, 47],) = [6, 24, 47] 1->7 8 tri_fusion([24],) = [24] 7->8 9 tri_fusion([6, 47],) = [6, 47] 7->9 10 tri_fusion([6],) = [6] 9->10 11 tri_fusion([47],) = [47] 9->11
Out[10]:
[0, 6, 24, 47, 72, 76]

Tri rapide

In [11]:
import random

@trace
def tri_rapide(t):
    if len(t) < 2:
        return t
    valeur_pivot = t[0] # au hasard : t[random.randrange(len(t))]
    petits, egaux, grands = [], [], []
    for x in t:
        if x < valeur_pivot:
            petits.append(x)
        elif x == valeur_pivot:
            egaux.append(x)
        else:
            grands.append(x)
    return tri_rapide(petits)+egaux+tri_rapide(grands)
In [12]:
import random
v = [random.randrange(0, 100) for _ in range(6)]
print(v)
tri_rapide(v)
[68, 78, 1, 77, 59, 9]
Trace 1 tri_rapide([68, 78, 1, 77, 59, 9],) = [1, 9, 59, 68, 77, 78] None->1 3 tri_rapide([],) = [] 2 tri_rapide([1, 59, 9],) = [1, 9, 59] 2->3 4 tri_rapide([59, 9],) = [9, 59] 2->4 5 tri_rapide([9],) = [9] 4->5 6 tri_rapide([],) = [] 4->6 1->2 7 tri_rapide([78, 77],) = [77, 78] 1->7 8 tri_rapide([77],) = [77] 7->8 9 tri_rapide([],) = [] 7->9
Out[12]:
[1, 9, 59, 68, 77, 78]
In [ ]: