Tris de listes

## Tri par Insertion

def triInsertion(l):
    ll = l[:]
    n = len(ll)
    for i in range(n):
        element = ll[i]
        j = i
        while (j>0 and ll[j-1] > element):
            ll[j] = ll[j-1]
            j = j-1
        ll[j] = element
    return ll

def triInsertionMieux(l):
    ll = l[:]
    n = len(ll)
    for i in range(n):
        element = ll[i]
        j = i
        while (j>0 and ll[j-1] > element):
            j = j-1
        ll.insert(j,element)
        del(ll[i+1])
    return ll

## Tri fusion

def divise(l):
    n=len(l)
    return l[:n//2],l[n//2:]

def fusionRec(l1,l2):
    if l1 == []: return l2
    if l2 == []: return l1
    if l1[0] <= l2[0]:
        return [l1[0]] + fusion(l1[1:],l2)
    else:
        return [l2[0]] + fusion(l1,l2[1:])

def fusion(l1,l2):
    l = []
    while True:
        if l1 == []: return l+l2
        if l2 == []: return l+l1
        if l1[0] < l2[0]:
            l.append(l1[0])
            l1.pop(0)
        else:
            l.append(l2[0])
            l2.pop(0)
    return l

def triFusion(l):
    n = len(l)
    if n<=1:
        return l
    else:
        lg,ld = divise(l)
        lg,ld = triFusion(lg),triFusion(ld)
        return fusion(lg,ld)

## Quicksort

def partition(l):
    lg = []
    ld = []
    pivot = l[0]
    for elem in l[1:]:
        if elem < pivot:
            lg.append(elem)
        else:
            ld.append(elem)
    return lg,ld,pivot

def quicksort(l):
    n = len(l)
    if n <= 1:
        return l
    else:
        lg,ld,pivot = partition(l)
        lg = quicksort(lg)
        ld = quicksort(ld)
        return lg+[pivot]+ld

## Quicksort + insertion

def sedgesort(l):
    n = len(l)
    if n<=15:
        return triInsertionMieux(l)
    else:
        lg,ld,pivot = partition(l)
        lg = sedgesort(lg)
        ld = sedgesort(ld)
        return(lg+[pivot]+ld)

## Mediane

def nth_least(l,n):
    lg,ld,pivot = partition(l)
    kg = len(lg)
    if n==kg:
        return pivot
    elif n<kg:
        return nth_least(lg,n)
    else:
        return nth_least(ld,n-(kg+1))

def mediane(l):
    n = len(l)
    return nth_least(l,n//2)

## Test
import random as rd
import time
l = [rd.randint(-499,499) for _ in range(20000)]

t = time.time()
l_insert = triInsertion(l)
print("Tri par insertion :",time.time() - t)
t = time.time()
l_insertmieux = triInsertionMieux(l)
print("Tri par insertion mieux :",time.time() - t)
t = time.time()
l_fusion = triFusion(l)
print("Tri fusion :",time.time() - t)
t = time.time()
l_qs = quicksort(l)
print("Tri rapide :",time.time() - t)
t = time.time()
l_sedge = sedgesort(l)
print("Tri Sedge :",time.time() - t)
t = time.time()
l_sort = sorted(l)
print("Tri Python :",time.time() - t)
t = time.time()

Graphes et algorithme de Dijkstra

## Exercice 1
import numpy as np

Exm1 = {
    0:[],
    1:[(2,0),(4,1),(5,3)],
    2:[(0,6),(1,2)],
    3:[],
    4:[(2,1)],
    5:[(3,2)]
    }

mat = np.array([[-1., -1., -1., -1., -1., -1.],
       [-1., -1.,  0., -1.,  1.,  3.],
       [ 6.,  2., -1., -1., -1., -1.],
       [-1., -1., -1., -1., -1., -1.],
       [-1., -1.,  1., -1., -1., -1.],
       [-1., -1., -1.,  2., -1., -1.]])

## Exercice 2

import numpy as np

def matriceVersListe(mat):
    n,_ = mat.shape
    d = dict()
    for i in range(n):
        l = []
        for j in range(n):
            if mat[i,j] != -1:
                l.append((j,mat[i,j]))
        d[i] = l
    return d

def listeVersMatrice(d):
    n = len(d)
    mat = -1*np.ones([n,n])
    for s in d:
        for (v,p) in d[s]:
            mat[s,v] = p
    return mat

## Exercice 3

def voisins(d,s):
    voisins = []
    for v,p in d[s]:
        voisins.append(v)
    return voisins

## Exercice 4

def cheminValide(d,chemin):
    n = len(chemin)
    for i in range(n-1):
        if chemin[i+1] not in voisins(d,chemin[i]):
            return False
    return True

## Exercice 5

def parcoursLargeur(d,s):
    visite = []
    file = [s]
    while file != []:
        print(file)
        sommet = file.pop(0)
        visite.append(sommet)
        for v in voisins(d,sommet):
            if v not in file and v not in visite:
                file.append(v)
    return visite

def parcoursProfondeur(d,s):
    visite = []
    file = [s]
    while file != []:
        print(file)
        sommet = file.pop()
        visite.append(sommet)
        for v in voisins(d,sommet):
            if v not in file and v not in visite:
                file.append(v)
    return visite

## Exercice 7

Exm = {
    0:[(1,7),(2,1)],
    1:[(3,4),(5,1)],
    2:[(1,5),(4,2),(5,7)],
    3:[],
    4:[(1,2),(3,5)],
    5:[(4,3)]
    }

def index_min_non_visite(l,v):
    """
    Donne l'index de l'element min dans une liste
    """
    k = -1
    min = float('inf')
    for i in range(len(l)):
        if l[i] < min and i not in v:
            k = i
            min = l[i]
    return k

def poids_arete(graphe,i,j):
    for elem in graphe[i]:
        if elem[0] == j:
            return elem[1]

def voisins(graphe,i):
    l = []
    for elem in graphe[i]:
        l.append(elem[0])
    return l

def Dijkstra_distances(graphe,sommet):
    sommets = list(range(len(graphe)))
    distances = [float('inf') for elem in graphe]
    distances[sommet] = 0
    for s,p in graphe[sommet]:
        distances[s] = p
    visites = [sommet]
    while len(sommets) > len(visites):
        k = index_min_non_visite(distances,visites)
        visites.append(k)
        for s in voisins(graphe,k):
            if s not in visites:
                if distances[s] > distances[k] + poids_arete(graphe,k,s):
                    distances[s] = distances[k] + poids_arete(graphe,k,s)
    return distances

## Exercice 9

def Dijkstra(graphe,sommet):
    sommets = list(range(len(graphe)))
    distances = [float('inf') for elem in graphe]
    origine = [None for elem in graphe]
    distances[sommet] = 0
    for s,p in graphe[sommet]:
        distances[s] = p
        origine[s] = sommet
    visites = [sommet]
    while len(sommets) > len(visites):
        print(distances)
        k = index_min_non_visite(distances,visites)
        visites.append(k)
        for s in voisins(graphe,k):
            if s not in visites:
                if distances[s] > distances[k] + poids_arete(graphe,k,s):
                    distances[s] = distances[k] + poids_arete(graphe,k,s)
                    origine[s] = k
    return distances,origine

## Exercice 10

def distance(graphe,i,j):
    tabDistances, tabOrigine = Dijkstra(graphe,i)
    k = j
    l = []
    while k!= i:
        l = [k] + l
        k = tabOrigine[k]
    l = [i] + l
    return l,tabDistances[j]

Bases de données relationnelles Correction