Algos de tris ♻️⚓︎
Comparaison des Tris⚓︎
Tri par insertion⚓︎
Tri par insertion
Fonction qui prend comme paramètre une liste et trie cette liste en place (c'est-à-dire que la liste initiale est modifiée) en utilisant l'algorithme de tri par insertion. Plusieurs versions proposées .
Tri en place, itératif
🐍 Script Python
def insere(donnees, indice):
"""insere la donnee d'indice indice à sa bonne place dans la liste formée des
éléments d'indice inférieur ou égaux à indice.
Le début de la liste est sensé être trié.
LA MODIFICATION SE FAIT EN PLACE
param :
donnees : list
indice : int
exemple :
>>> a = [3, 9, 5, 6, 4, 1]
>>> insere(a, 2)
>>> a
[3, 5, 9, 6, 4, 1]
"""
while indice>0 and donnees[indice]<donnees[indice-1]:
donnees[indice-1], donnees[indice] = donnees[indice], donnees[indice-1]
indice = indice -1
def tri_insertion(donnees):
"""tri la liste données en place, avec l'algorithme de tri par insertion
LE TRI SE FAIT EN PLACE.
param :
donnees : list
exemple :
>>> liste3 = [ "ruby", "python", "logo", "elan", "rust"]
>>> tri_insertion(liste3)
>>> liste3
['elan', 'logo', 'python', 'ruby', 'rust']
"""
for ind in range(len(donnees)):
insere(donnees,ind)
Tri itératif qui renvoie une nouvelle liste
🐍 Script Python
def insere2(liste, valeur):
"""Insère la valeur dans la liste, supposée triée. la modification est en place
param :
liste : list : liste de nombres
valeur : float/int
return :
list : nouvelle liste avec la valeur insérée
Exemple:
>>> liste1 = [3,5.2,6]
>>> insere2(liste1, 4)
>>> liste1
[3, 4, 5.2, 6]
"""
liste.append(valeur)
indice = len(liste)-1
while indice>0 and liste[indice-1] > liste[indice]:
liste[indice],liste[indice-1] = liste[indice-1],liste[indice]
indice = indice - 1
def tri_insertion2(liste):
"""renvoie une nouvelle liste qui est une version triée de liste
param :
liste : list
return :
liste
Exemple :
>>> tri_insertion2([8,2,6,5])
[2, 5, 6, 8]
"""
liste_triee = []
for element in liste:
insere2(liste_triee, element)
return liste_triee
Tri récursif qui renvoie une nouvelle liste
🐍 Script Python
def insere3(liste, valeur):
"""Insère la valeur dans la liste, supposée triée
param :
liste : list : liste de nombres
valeur : float/int
return :
list : nouvelle liste avec la valeur insérée
Exemple:
>>> liste1 = [3,5.2,6]
>>> liste2 = insere3(liste1, 4)
>>> liste2
[3, 4, 5.2, 6]
"""
if liste == []:
return [valeur]
elif liste[-1]>valeur:
return insere3(liste[:-1],valeur) + [liste[-1]]
else:
return liste + [valeur]
def tri_recursif_insertion3(liste):
"""renvoie une nouvelle liste qui est une version triée de liste. Méthode récursive.
param :
liste : list
return :
liste
Exemple :
>>> tri_recursif_insertion3([8,2,6,5])
[2, 5, 6, 8]
"""
if liste == []:
return []
else:
return insere3(tri_recursif_insertion3(liste[:-1]),liste[-1])
Tri par sélection⚓︎
Tri par sélection
Fonction qui renvoie la liste triée par ordre croissant.
🐍 Script Python
def index_min(donnees, indice):
"""retourne l'indice du plus petit élément d'une liste, à partir d'un indice donné
Exemple:
>>> index_min(["curl", "bash", "python", "cilk", "nesl"], 0)
1
>>> index_min(["curl", "bash", "python", "cilk", "nesl"], 2)
3
"""
pos = indice
for i in range(indice, len(donnees)):
if donnees[i]<donnees[pos] :
pos = i
return pos
def tri_selection(donnees):
"""tri la liste donnees en place, avec l'algorithme de tri par sélection
>>> liste3 = [ "ruby", "python", "logo", "elan", "rust"]
>>> tri_selection(liste3)
>>> liste3
['elan', 'logo', 'python', 'ruby', 'rust']
"""
for i in range(len(donnees)-1):
j = index_min(donnees,i)
donnees[i], donnees[j] = donnees[j], donnees[i]
Tri fusion⚓︎
Algorithme de tri fusion (merge sort) 
🐍 Script Python
def interclassement(lst1, lst2):
lst_totale = []
n1, n2 = len(lst1), len(lst2)
i1, i2 = 0, 0
while i1 < n1 and i2 < n2:
if lst1[i1] < lst2[i2]:
lst_totale.append(lst1[i1])
i1 += 1
else:
lst_totale.append(lst2[i2])
i2 += 1
return lst_totale + lst1[i1:] + lst2[i2:]
def tri_fusion(lst):
if len(lst) <= 1:
return lst
else:
m = len(lst) // 2
return interclassement(tri_fusion(lst[:m]), tri_fusion(lst[m:]))