(Sujet)

## 1 Somme

def est_valide(ch):
    if ch[0] == '+' or ch[-1]=='+':
        return False
    n = len(ch)
    for i in range(n):
        if ch[i]=='+':
            if ch[i+1]=='+':
                return False
        else:
            if not ch[i].isdigit():
                return False
    return True

## 2 Evaluation

def evalue(ch):
    l = ch.split('+')
    s = 0
    for x in l:
        s = s+int(x)
    return s

## 3 Liste d'additions

def plus_grande_somme(l):
    ll = [evalue(x) for x in l]
    return max(ll)

## 4 Expressions arithmétiques

def calcule(a,b,op):
    if op == '+':
        return a+b
    if op == '-':
        return a-b
    if op == '*':
        return a*b
    if op == '/':
        return a//b

## 5 Evaluation

def evaluation(l):
    if len(l)==1: return l[0]
    else:
        a,op,b = l.pop(0), l.pop(0), l.pop(0)
        l = [calcule(a,b,op)] + l
        return evaluation(l)

def evaluation2(l):
    r=l[0]
    n = len(l)
    i=1
    while i<n:
        r = calcule(r,l[i+1],l[i])
        i=i+2
    return r

## 6 Expression postfixee

def postfix(l):
    ope = ['+','-','*','/']
    pile = []
    for x in l:
        if x in ope:
            b,a = pile.pop(),pile.pop()
            pile.append(calcule(a,b,x))
        else:
            pile.append(x)
    return pile[0]

## 7 Verification d'erreur

def postfix(l):
    ope = ['+','-','*','/']
    pile = []
    for x in l:
        if x in ope:
            if len(pile) <2: return 'ERR'
            b,a = pile.pop(),pile.pop()
            if x=='/' and b==0: return 'ERR'
            pile.append(calcule(a,b,x))
        else:
            pile.append(x)
    if len(pile)!=1: return 'ERR'
    return pile[0]

(Sujet)

## 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 fusion(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 (l1!=[] and l2!=[]):
        if l1[0] > l2[0]:
            l.append(l2[0])
            del(l2[0])
        else:
            l.append(l1[0])
            del(l1[0])
    if l1==[]:
        return l + l2
    else:
        return l+l1

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()