Algorithmes de tri

Algorithmes de tri

exm = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

## Tri par Selection

def minimum(l):
    n = len(l)
    indicemin = 0
    for i in range(n):
        if l[i] < l[indicemin]:
            indicemin = i
    return indicemin

def triSelection(l):
    n = len(l)
    for i in range(n):
        k = minimum(l[i:])+i
        l[i],l[k] = l[k],l[i]

## Tri par Insertion

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

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

## Tri à Bulles
def triBullesEtape(l):
    n = len(l)
    b=False
    for i in range(n-1):
        if l[i]>l[i+1]:
            l[i],l[i+1] = l[i+1],l[i]
            b = True
    return b

def triBulles(l):
    b = False
    while not b:
        b = not triBullesEtape(l)
## Comparaisons des tris

from random import randint
from time import process_time
from copy import deepcopy

l=[]
for i in range(10000):
    l.append(randint(0,100))

m=deepcopy(l)
# Selection
t1=process_time()
triSelection(m)
t2=process_time()
print("Tri par selection :",t2-t1)

m=deepcopy(l)
#Insertion
t1=process_time()
triInsertion(m)
t2=process_time()
print("Tri par insertion :",t2-t1)

m=deepcopy(l)
#Insertion
t1=process_time()
triInsertionMieux(m)
t2=process_time()
print("Tri par insertion amélioré :",t2-t1)

m=deepcopy(l)
#Bulles
t1=process_time()
triBulles(m)
t2=process_time()
print("Tri à bulles :",t2-t1)

m=deepcopy(l)
#Python
t1=process_time()
m.sort()
t2=process_time()
print("Tri Python :",t2-t1)    

## Recherche par dichotomie

def recherchedicho(l,x,u,v):
    if u<v:
        n = (u+v)//2
        print(u,v,":",n)
        if l[n]==x:
            return(n)
        elif l[n]>x:
            return(recherchedicho(l,x,u,n))
        else:
            return(recherchedicho(l,x,n,v))
    else:
        return(-1)

## Médiane
def mediane(l,b=False):
    if not b:
        l.sort()
        return(mediane(l,True))
    else:
        n=len(n)
        if n%2==0:
            return((l[n//2-1]+l[n//2])/2)
        else:
            return(l[n//2])

#Pour eviter les cas :
def mediane_bis(l,b=False):
    if not b:
        l.sort()
        return(mediane(l,True))
    else:
        n=len(n)
        return((l[n//2]+l[(n-1)//2])/2)