Algorithmes de tri

2 :

Tri par insertion :

def tri_insertion(tableau):
    for i in range(1,len(tableau)):
        en_cours = tableau[i]
        j = i
        while j>0 and tableau[j-1]>en_cours:
            tableau[j]=tableau[j-1]
            j = j-1
        tableau[j]=en_cours
        
tab=[15,12,18,3,19]
tri_insertion(tab)
print(tab)

Tri par selection :

def tri_selection(tableau):
    for i in range(len(tableau)):
        min = i
        for j in range(i+1, len(tab)):
            if tab[min] > tab[j]:
                min = j
        tmp = tab[i]
        tab[i] = tab[min]
        tab[min] = tmp
    return tab
            
tab=[15,12,18,3,19]
tri_selection(tab)
print(tab)

Mesure temps d’exécution des tris :

import time
import random

n=10
tab=[]

for i in range(n):
    tab.append(random.randint(0,n))
print(tab)

debut=time.time()
tab.sort()
duree=time.time()-debut

print('durée = ',duree ,'s')
print(tab)

Avec 10, 100, 1000, 10000 nombres cela est instantané. A partir de 100 000 il y a un peu de temps entre 0.01s et 0.03s. Avec 1millions de valeurs, cela prend entre 0.2s et 0.3s.

C’est la fonction sort qui est la plus rapide des trois.