Hello world,
j'aimerais vous partager des algorithmes qui permettent de ranger dans l'ordre croissant une série de nombres. En même temps, j'aimerais avoir vos conseils afin de pouvoir améliorer le temps d'exécution des fonctions pour trier les données encore plus rapidement !
(ici je teste le temps d'exécution par rapport à une liste de 1000 valeurs variant de 0 à 999)
1 - Le tri bulle :def tri_bulle(liste):
permutation = True
while permutation:
permutation = False
for x in range(0, len(liste)-1):
if liste[x] > liste[x+1]:
permutation = True
liste[x], liste[x+1] = liste[x+1], liste[x]
return liste
Temps d'exécution par tri-bulle : 2.500e-01 secondes
2 - Le tri par sélection :
def maxi(liste, n):
indice = 0
for i in range(n):
if liste[i] > liste[indice]:
indice = i
return [liste[indice], indice]
def tri_selection(liste):
i = len(liste) - 1
while i > 0:
j = maxi(liste, i + 1)[1]
if j != i:
liste[j], liste[i] = liste[i], liste[j]
i -= 1
return liste
Temps d'exécution par sélection : 7.147e-02 secondes
3 - Le tri par insertion :
def insertion(liste, n):
while liste[n] < liste[n-1] and n > 0:
liste[n], liste[n-1] = liste[n-1], liste[n]
n -= 1
return liste
def tri_insertion(liste):
n = len(liste)
for i in range(1, n):
liste = insertion(liste, i)
return liste
Temps d'exécution par insertion : 1.240e-01 secondes
4 - Le tri rapide :
def tri_rapide(liste):
if liste == []:
return []
else:
return (tri_rapide([x for x in liste[1:] if x < liste[0]])
+ [liste[0]] + tri_rapide([x for x in liste[1:] if x >= liste[0]]))
Temps d'exécution par tri-rapide : 4.888e-03 secondes
Bon je constate que le tri-rapide porte bien son nom mais j'aimerais faire mieux que ça encore ! Si vous avez des recommandations je suis preneur.