Trier une liste
Algorithmes de tri
La principale motivation de pouvoir rechercher rapidement un élément dans une
séquence. Quoi de plus rapide si cette même séquence est triée ?
Activité (par groupe de 2-3 élèves ou seul en utilisant CECI)
Vous disposez de 10 cartes.
» Objectif final
Votre objectif est de déterminer une stratégie claire, précise et explicitée à
l’écrit, c’est à dire le déroulé écrit des actions élémentaires à réaliser,
afin d’obtenir des cartes triées suivant leur valeur faciale (par exemple
\(\text{As}<2 \text{ et Valet} >5 \)) à la fin du processus.
» Actions possibles
Les seules actions élémentaires autorisées sont :
- choisir deux cartes;
- comparer deux cartes;
- échanger la position de deux cartes;
- compter le nombre de comparaisons effectuées.
» Début des hostilités:
Le processus débute par:
- la mise en place de la stratégie que vous affinerez au fur et à mesure de vos
tests;
- la désignation du rôle de chacun dans le groupe lors de l’exécution de la
stratégie définie préalablement;
- puis le mélange des cartes retournées.
Dans chaque groupe, à chaque tour:
- la personne préposée désigne les deux cartes à comparer: il a interdiction de
les retourner et a fortiori de connaître les valeurs des cartes;
- une personne est préposée à comparer les deux cartes qu’on lui désigne: lui
seul à le droit de les retourner et de connaître les valeurs des cartes;
- un dernière personne décompte le nombre de comparaisons effectuées tout en
veillant à vérifier le bon respect du rôle de chacun.
Quelques algorithmes de tri à maîtriser
Pour fixer, tous les algorithmes de tri décrits ci-dessous prennent en :
- Entrée : alignement de \(N\) cartes repérées par leur position à partir de
la gauche de \(0\) à \(N-1\).
- Sortie : les mêmes cartes alignées de la plus petite valeur faciale à la
plus grande.
Le tri par sélection:
En français
Pour i allant de la première position (0) à l'avant-dernière (N-2):
Trouver la carte de plus valeur parmi les cartes aux positions i à N-1.
Echanger la carte en position i avec cette carte.
Fin Pour
Il est nécessaire de définir une méthode pour déterminer la position de la carte
de plus petite valeur parmi les positions \(i\) à \(N-1\).
Entrées : les cartes, la position i de départ.
Sortie : la position de la carte de plus petite valeur.
Je repère la position de la première carte.
De la deuxième carte jusqu'à la dernière:
Si la carte courante est une valeur moindre que la carte repérée,
Alors la position de la carte courante est repérée.
Fin Pour
Renvoie la position de la carte repérée.
Impémentation en Python
def tri_selection(liste):
"""
:param liste: (list) une liste d'éléments comparables
:return: None
:Effet de bord: trie les éléments de la liste dans l'ordre croissant
>>> liste = [3, 1, 4, 9, 5, 1, 2]
>>> tri_selection(liste)
>>> liste == [1, 1, 2, 3, 4, 5, 9]
True
>>> from random import randint
>>> liste1 = [randint(0,1000) for k in range(randint(0,100))]
>>> liste2 = liste1.copy()
>>> tri_selection(liste1)
>>> all(liste1.count(elt) == liste2.count(elt) for elt in liste1)
True
>>> all(liste1.count(elt) == liste2.count(elt) for elt in liste2)
True
"""
for i in range(len(liste)-1):
i_min = indice_min(liste, i)
liste[i] , liste[i_min] = liste[i_min], liste[i]
def indice_min(liste, i):
"""
:param i: (int) un indice
:param liste: (list) une liste d'éléments comparables
:CU: 0 <= i < len(l)
:return: l'indice du minimum de la liste l[i:]
>>> liste = [3, 1, 4, 9, 5, 1, 2]
>>> indice_min(liste, 2)
5
"""
i_min = i
for j in range(i, len(liste)):
if liste[j] < liste[i_min]:
i_min = j
return i_min
Validité des algorithmes
-
La terminaison : elle est immédiate puisqu’on a recours à la boucle POUR.
-
La correction des boucles:
- Pour la fonction
tri_selection():
Soit \(0 \leqslant i \leqslant N-1\).
À l’étape \(i\), les premières cartes (de \(0\) à \(i\)) sont triées
et les cartes de la partie non triées (de \(i+1\) à \(N-1\)) sont toutes
d’une valeur supérieure à celles triées.
- Pour la fonction
indice_min():
Soit \(j \geqslant i\).
À l’étape \(j\), la carte repérée est celle avec la plus petite valeur
parmi celles rangées aux positions comprises entre \(i\) et \(j\).
Complexité de l'algorithme
Soit \(n\) la longueur de la liste donnée en paramètre.
Évaluons le nombre de comparaisons.
Dans la fonction tri_selection(), dans la boucle FOR, pour \(i\) fixé avec
\(0 \leqslant i \leqslant n-1\), il y a \(n-i-1\) comparaisons effectuées
par indice_min(liste, i).
Finalement, il y a \((n-1) + (n-2) + \ldots{} + 0 = \dfrac{n(n-1)}{2} =
\dfrac{n^2-n}{2}\) comparaisons.
La complexité du tri par sélection est quadratique
\(\mathscr{O}(n^2)\) et ce quelque soit la liste donnée.
Le tri par insertion:
En français
Pour i allant de la deuxième position (1) à la dernière (N-1):
Insèrer la carte i dans les cartes aux positions 1 à i-1 en respectant l'ordre désiré.
Fin Pour
Ici, il est nécessaire de définir une méthode pour insérer la carte dans sa
bonne position parmi les \(i\) premières cartes.
Entrées : les cartes, la position i de départ.
Sortie : rien
Effet de bord: les i+1 premières cartes sont triées.
j = i-1
Garder en mémoire la valeur de la carte en position i.
Tant que la carte en position j a une valeur supérieure à la carte en position i:
Déplacer la carte j vers la droite
j = j - 1
Fin TantQue
Insérer la carte gardée en mémoire dans l'espace libre (en position j+1)
Impémentation en Python
def tri_insertion(liste):
"""
:param liste: (list) une liste d'éléments comparables
:return: None
:Effet de Bord: trie les éléments de la liste selon l'ordre passé en paramètre
>>> liste = [3, 1, 4, 9, 5, 1, 2]
>>> tri_insertion(liste)
>>> liste == [1, 1, 2, 3, 4, 5, 9]
True
>>> from random import randint
>>> liste1 = [randint(0,1000) for k in range(randint(0,100))]
>>> liste2 = liste1.copy()
>>> tri_insertion(liste1)
>>> all(liste1.count(elt) == liste2.count(elt) for elt in liste1)
True
>>> all(liste1.count(elt) == liste2.count(elt) for elt in liste2)
True
"""
for i in range(1, len(liste)):
inserer(liste, i)
def inserer(liste, i):
"""
:param i: (int) un indice
:param liste: (list) une liste d'éléments comparables
:CU: 0 <= i < len(l)
:return: None
:Effet de bord: trie les i+1 premiers éléments de la liste dans l'ordre croissant
>>> liste = [1, 2, 4, 5, 3, 7, 6]
>>> inserer(liste, 4)
>>> liste == [1, 2, 3, 4, 5, 7, 6]
True
>>> inserer(liste, 5)
>>> liste == [1, 2, 3, 4, 5, 7, 6]
True
>>> inserer(liste, 6)
>>> liste == [1, 2, 3, 4, 5, 6, 7]
True
"""
mem = liste[i]
j = i - 1
while j>=0 and liste[j] > mem:
liste[j+1] = liste[j]
j = j - 1
liste[j+1] = mem
Validité des algorithmes
-
La terminaison : elle est immédiate puisqu’on a recours à la boucle POUR.
-
La correction des boucles:
- Pour la fonction
tri_insertion():
Soit \(1 \leqslant i \leqslant N-1\).
À l’étape \(i\), les \(i\) premières cartes (de \(0\) à \(i-1\))
sont triées.
- Pour la fonction
inserer():
Soit \(j < i\).
À l’étape \(j\), les cartes dont la position est entre \(j\) et \(i\)
ont une valeur supérieure à la carte mémorisée.
Complexité de l'algorithme
Soit \(n\) la longueur de la liste donnée en paramètre.
Évaluons le nombre de comparaisons.
Dans la fonction tri_insertion(), dans la boucle FOR, pour i fixé avec
\(1 \leqslant i \leqslant n-1\), il y a:
- dans le pire des cas, \(i\) comparaisons effectuées dans
inserer(liste, i);
- dans le meilleur des cas (la liste est déjà ordonnée dans le bon ordre),
\(1\) comparaison uniquement dans
inserer(liste,i).
Finalement, il y a :
- dans le pire des cas, \(1 + 2 + \ldots{} + (n-1) = \dfrac{n(n-1)}{2} =
\dfrac{n^2-n}{2} \) comparaisons.
- dans le meilleur des cas, \(1 + 1 + \ldots{} + 1 = n-1\) comparaisons.
La complexité du tri par insertion est quadratique
\(\mathscr{O}(n^2)\). Il est plus efficace que le tri précédent lorsque la
liste est déjà partiellement rangée dans l’ordre souhaitée.
Remarques:
-
On peut ordonner des chaînes de caractères. L’ordre est donné par l’ordre
alphabétique défini par le tableau d’encodage (voir
2.1).
Les caractères numériques sont placés avant les caractères aphabétiques, les
majuscules avant les minuscules, …
Pour en comparer deux, on compare en premier lieu leur premier caractère, en cas
d’égalité le suivant, ect …
Exemple:
>>> liste = ["NSI", "Nsi", "nsi", "3", str(12)]
>>> tri_selection(liste)
>>> liste
['12', '3', 'NSI', 'Nsi', 'nsi']
-
Dans Python, sont intégrées une fonction de tri sorted() (qui retourne une
nouvelle liste triée), ainsi que la méthode sort() (où le tri est un effet
de bord).
Exemple d’usage:
>>> liste = ["NSI", "Nsi", "nsi", "3", str(12)]
>>> sorted(liste)
['12', '3', 'NSI', 'Nsi', 'nsi']
>>> liste
["NSI", "Nsi", "nsi", "3", str(12)]
>>> liste.sort()
>>> liste
['12', '3', 'NSI', 'Nsi', 'nsi']
Notes de bas de page:
