Les tris
On dispose d'une liste d'objets comparables. Par exemple des nombres. Ou des chaînes de caractères.
Il existe bien entendu des méthodes python permettant un tri efficace.
Exemple 1 : fonction créant une nouvelle liste.
from random import randint
longueur=10
# création d'une liste d'entiers au hasard
L = [ randint(1,100) for j in range(longueur) ]
print('Contenu de la liste L :\n', L)
# création d'une nouvelle liste
# même contenu que L
# mais triée :
M=sorted(L)
print('Contenu de la liste M=sorted(L) :\n ',M)
# L est inchangée :
print('Contenu de la liste L :\n', L)
ce qui donne :
Contenu de la liste L :
[40, 32, 79, 2, 63, 8, 85, 9, 76, 86]
Contenu de la liste M=sorted(L) :
[2, 8, 9, 32, 40, 63, 76, 79, 85, 86]
Contenu de la liste L :
[40, 32, 79, 2, 63, 8, 85, 9, 76, 86]
Exemple 2 : méthode agissant sur la liste initiale.
L = [ 'choucroute','barbapapa', 'tsointsoin', 'abracadabra' ]
print('Contenu de la liste L :\n', L)
L.sort()
print('Contenu de la liste L :\n', L)
L'affichage obtenu :
Contenu de la liste L :
['choucroute', 'barbapapa', 'tsointsoin', 'abracadabra']
Contenu de la liste L :
['abracadabra', 'barbapapa', 'choucroute', 'tsointsoin']
L'objectif de ce cours sera de découvrir un algorithme de tri et non d'utiliser les méthodes déjà programmées.
Le tri par sélection du minimum.
Nous exposons ci-dessous le principe du tri par sélection du minimum.
Entrée : une liste d'éléments comparables.
Sortie : la liste triée en ordre croissant.
Traitement :
1. On colore en noir tous les éléments.
2. On repère un élément de valeur minimale parmi les éléments noirs.
3. On passe cet élément en tête des éléments noirs puis on le colore en rouge.
4. On reprend au point 2 tant qu'il reste des noirs.
Illustration.
On applique cet algorithme sur la liste L=[3, 2, 1, 5, 4, 2].
On sélectionne le minimum des noirs (ici, il s'agit de L[2]=1). On le passe en tête des noirs et on le colore en rouge.
La liste est maintenant L=[ 1, 3, 2, 5, 4, 2 ].
On recommence : on sélectionne un élément de valeur minimale. On a ici deux choix, on choisit l'un des deux au hasard. Par exemple
la première occurrence de 2.
La liste est maintenant L=[ 1, 2, 3, 5, 4, 2 ].
On continue tant qu'il reste des éléments noirs, ce qui donne les étapes suivantes :
L=[ 1, 2, 2, 3, 5, 4 ]
L=[ 1, 2, 2, 3, 5, 4 ]
L=[ 1, 2, 2, 3, 4 , 5 ]
L=[ 1, 2, 2, 3, 4, 5 ]
Temps de calcul du tri par sélection.
Le tri par sélection est un tri en temps quadratique.
: pour une liste de n éléments, le temps nécessaire au tri de la liste est
donné approximativement par un polynôme du second degré en n.
Pour comprendre cette affirmation, il faut rentrer dans le détail des tâches à réaliser par la machine lors
du déroulement de cet algorithme. Ce détail sera traité dans la
page d'exercices.
Nous verrons que ce temps n'est pas un bon temps pour un tri. En d'autres termes, il existe des algorithmes de tri
réalisant de meilleurs temps (il s'agit toutefois essentiellement de comparaison pour des listes de taille n assez grandes. Pour de très
petites
listes, les comparaisons de vitesse entre les différents algorithmes de tri peuvent être parfois renversées).