Déjà avoir des données dans l'ordre croissant ou décroissant est un plus pour l'utilisateur, il est intéressant de savoir qui est en tête de classe par exemple.
Même sans chercher les extrêmes, quand des données sont triées la recherche d'un élément est très rapide à l'aide de la recherche dichotomique (on rappelle que le coût pour trouver un élément dans n données est de l'ordre de ln(n) pour des données triées contre n pour des données non triées). Imaginez un dictionnaire où les mots sont rangés de manière aléatoire ! Pour revenir sur la vitesse de l'algorithme dichotomique : si chercher une donnée dans un tableau de taille 1000 se fait en une seconde, alors chercher une donnée dans un tableau de taille 1000000 se fait en 1000 s si l'algorithme de recherche est naïf et en 2s avec l'algorithme dichotomique !
Un grand nombre d'algorithmes.
Il existe un grand nombre d'algorithmes de tri (et on en cherche encore), car souvent les problématiques peuvent légèrement différées :
Quel est le nombre de donnés (une dizaine ou des milliards ) ?
Les données sont elles déjà presque rangées ?
A t on beaucoup de mémoire ? Veut on trier en place ?
Veut on conserver conserver la stabilité, c'est à dire que si deux élèments sont égaux et si le premier est situé avant le second alors il doit en être de même à la fin(voir plus bas pour un exemple).
Le programme propose deux algortihmes de tri, ils ne sont pas efficaces pour des grandes valeurs mais sont classiques et simples à comprendre.
Tri par sélection.
Le principe de la méthode est le suivant : on trouve le plus grand nombre puis on le met à la fin puis le deuxième plus grand que l'on met en avant dernière position et ainsi de suite.
Tri par insertion.
Le tri par insertion prend le principe du tri du joueur de carte, on prend une carte puis la suivante et on l'insert (c'est à dire on la met à sa place), puis la suivante et on l'insert,... ainsi de suite jusqu'à la derniére.
Le tri par insertion est très efficace pour des petits tableaux.
Il existe une meilleure implémentation de l'algorithme qui fait gagner des échanges (grosso modo une division par 2 ce qui ne change pas le theta de complexité) mais pas des comparaisons, celle qui est dans l'épreuve pratique :
def tri_insertion(L):
n = len(L)
# cas du tableau vide
if n == 0 :
return L
for j in range(1,n):
e = L[j]
i = j
# A l'étape j, le sous-tableau L[0,j-1] est trié
# et on insère L[j] dans ce sous-tableau en déterminant3 / 3
# le plus petit i tel que 0 <= i <= j et L[i-1] > L[j].
while i > 0 and L[i-1] > e :
i = i - 1
# si i != j, on décale le sous tableau L[i,j-1] d’un cran
# vers la droite et on place L[j] en position i
if i != j:
for k in range(j,i,-1):
L[k] = L[k-1]
L[i] = e
return L
Regardons le déroulement sur un exemple :
L
n
e
j
i
k
4
2
7
1
5
6
3
?
?
?
?
?
n = len(L)
n contient la longueur du tableau.
Tri par bulles.
Le tri par bulle est très simple et rapide à programmer. Pour des petits tableaux (taille 4 ou 5) il est acceptable.
Dans des cas particuliers : Tri casier.
Si on veut classer des nombres sur un ensemble fini est limité (par exemple des notes sur 10) alors il existe un tri casier (ou comptage) qui le fait en \(\Theta(n) \).Il n'y a pas de contradiction avec le fait que les meilleurs tris par comparaisons sont en nln(n) car le tri casier n'est pas un tri par comparaisons !
5
0
3
7
10
9
7
6
5
2
8
9
10
2
0
10
8
6
5
4
6
3
2
3
10
0
1
2
3
4
5
6
7
8
9
10
0
0
0
0
0
0
0
0
0
0
0
Les tris de python.
Python offre la possibilité de classer des tableaux de deux manières différentes (et avec des performances meilleures sur des grands tableaux).
Cependant Les tris par insertion et sélection sont au programme, alors habituez vous à les utiliser !
La fonction sorted retourne une nouvelle liste triée, la liste d'origine n'est pas modifiée.
Sorted classe des nombres, des chaines de caractères et des tableaux.
Si on veut classer selon les prénoms (ou selon d'autre critères) il faut lui indiquer clairement. De même on peut indiquer croissant ou décroissant.
Le tri utilisé par Python est stable ce qui est très pratique, par exemple si on veut classer selon les notes puis selon les noms. :
Enfin python permet de trier directement le tableau lui même sans créer un autre tableau (avec les mêmes options que sorted) :