Trier : sort

6.42.23 Trier : sort

sort a comme argument une liste de nombres ou une matrice ou une liste de chaines de caractères ou une expression.
lorsque le 1ier argument est une liste, sort accepte comme 2-ième argument une fonction de tri f qui doit définir un ordre strict faible ( par exemple (x,y)->x>y pour avoir la liste triée selon l’ordre décroissant).

Avec 1 argument
- Pour une liste, sort renvoie les éléments de la liste triés selon l’ordre croissant.
  On tape :
  sort([1,3,4,3,2])
  On obtient :
  [1,2,3,3,4]
- Pour une matrice ou une liste de chaines de caractères
  Si la liste est une matrice (resp une liste de chaines de caractères), sort renvoie la matrice dont les lignes sont triées selon l’ordre croissant en triant les lignes selon l’ordre [a₀,a₁,..a_n]<[b₀,b₁,..b_n] si a₀<b₀ ou si il existe k≤ n tel que a₀=b₀,...a_k−1<b_k−1 et a_k<b_k (resp la liste de chaines de caractères triées par l’ordre lexicographique).
  On tape :
  sort([[3,4,2],[4,2,3],[2,3,4],[2,4,3]])
  On obtient :
  [[2,3,4],[2,4,3],[3,4,2],[4,2,3]]
  On tape :
  sort(["assertion","aberrant","arret"])
  On obtient :
  ["aberrant","arret","assertion"]
  On tape :
  sort(["dac","bac","sac","asc","cab"])
  On obtient :
  ["asc","bac","cab","dac","sac"]
- Pour une expression, sort trie et collecte les termes égaux dans les sommes et produits.
  On tape :
  sort(y*2*x+x*y+y*x)
  On obtient :
  4*x*y
  On tape :
  sort(exp(2*ln(x))+x*y-x+y*x+2*x)
  On obtient :
  2*x*y+exp(2*ln(x))+x
  On tape :
  simplifier(exp(2*ln(x))+x*y-x+y*x+2*x)
  On obtient :
  x^2+2*x*y+x
Avec 2 arguments
Le deuxième argument doit être une fonction de tri f qui doit définir un ordre strict faible sinon l’algorithme employé risque de boucler.... c’est à dire que :
f(x,y) est un fonction toujours définie renvoyant 0 (faux) ou 1 (vrai) .
f doit renvoyer 0 si 2 éléments ne sont pas comparables et doit vérifier :
- f doit définir une relation transitive (si f(x,y) et f(y,z) sont vrais alors f(x,z) est vrai)
- on ne peut pas avoir f(x,y) et f(y,x) vrai en même temps et f(x,x) est faux (ce que l’on appelle une antisymétrie non réflexive)
- f ne définit pas forcément une relation d’ordre total, on peut avoir f(x,y) et f(y,x) simultanément faux.
  Si on définit la relation E par x E y est vrai lorsque f(x,y) et f(y,x) sont simultanément faux alors E doit être une relation d’équivalence.
Par exemple, on ne peut pas mettre comme fonction de tri : (x,y)->x[1]>=y[1]. On tape :
sort([3,4,2],(x,y)->x>y)
On obtient :
[4,3,2]
Exemples pour trier des listes de listes
Avec un seul argument, sort trie les listes de listes par ordre croissant.
sort([[1,3],[2,4],[2,3],[1,4]])
On obtient :
[[1,3],[1,4],[2,3],[2,4]]
Pour un ordre différent, il faut mettre une fonction de tri comme 2ième argument.
Par exemple :
1. Si on veut trier par ordre décroissant la première colonne ou en cas d’égalité par ordre décroissant la 2ième colonne (ordre lexicographique pour les 2 premières colonnes).
  On tape :
  sort([[1,3],[2,4],[2,3],[1,4]],
  (x,y)->when(x[0]==y[0],x[1]>y[1],x[0]>y[0]))
  On obtient :
  [[2,4],[2,3],[1,4],[1,3]]
2. Si on veut trier par ordre décroissant la 2ième colonne ou en cas d’égalité par ordre décroissant la première colonne.
  On tape :
  sort([[1,3],[2,4],[2,3],[1,4]],
  (x,y)->when(x[1]==y[1],x[0]>y[0],x[1]>y[1]))
  On obtient :
  [[2,4],[1,4],[2,3],[1,3]]
  Attention Dans l’exemple précédent,
  - on ne peut pas mettre comme fonction de tri (x,y)->x[1]>=y[1] car l’ordre n’est pas strict
  - on peut mettre comme fonction de tri f:=(x,y)->x[1]>y[1] bien que l’ordre ne soit pas total.
  Soient :
  L1:=[[1,2],[2,3],[4,3]]
  L2:=[[1,2],[4,3],[2,3]]
  Dans ce cas :
  sort(L1,(x,y)->x[1]>y[1]) et
  sort(L2,(x,y)->x[1]>y[1])
  renvoient des réponses différentes parce que l’ordre n’est pas total et que [2,3] et [4,3] sont considérés comme équivalents.
Exemple pour trier par ordre lexicographique des matrices ou des chaines de caractères
Pour trier par ordre lexicographique des matrices ou des chaines de caractères, il faut mettre en second argument comme fonction de tri, par exemple, la fonction booléenne super ci-dessous :
Si L1 et L2 sont 2 listes ou 2 chaines de caractères alors super(L1,L2) renvoie 1 si L1>L2 et 0 sinon.
On tape :
```
super(L1,L2):={
  local s,j;
  s:=min(size(L1),size(L2))-1;
  j:=0;
  tantque L1[j]==L2[j] and j<s faire
    j:=j+1;
  ftantque;
  //si L2[j]>=L1[j] alors return 0 sinon return 1; fsi;
  si [sort(L1[j],L2[j])]==[L1[j],L2[j]] alors 
     return 0 
    sinon 
     return 1;
  fsi;
}:; 
```
On a remplacé L2[j]>=L1[j] par [sort(L1[j],L2[j])]==[L1[j],L2[j]] pour que super soit aussi valable pour les chaines de caractères.
On tape :
sort(["dac","bac","sac","asc","cab"],super)
ou on tape
sort(["dac","bac","sac","asc","cab"],(x,y)->super(x,y))
On obtient :
["sac","dac","cab","bac","asc"]
On tape :
sort([[3,4,2],[4,2,3],[2,3,4],[2,4,3]],super)
ou on tape
sort([[3,4,2],[4,2,3],[2,3,4],[2,4,3]],(x,y)->super(x,y))
On obtient :
[[2,3,4],[2,4,3],[3,4,2],[4,2,3]][[2,3,4],[2,4,3],[3,4,2],[4,2,3]]

Remarque Si on veut trier la liste L:=[1,3,4,3,2] et mettre le résultat dans L, on a 2 façon de le faire. On tape :

L:=[1,3,4,3,2]

L:=sort(L)

Ou on tape :

L:=[1,3,4,3,2]

L.sort()

On obtient comme nouvelle valeur de L :

L:=[1,2,3,3,4]

Ou encore
Si on veut trier la liste L:=[[1,3],[2,4],[2,3],[1,4]] avec (x,y)->when(x[0]==y[0],x[1]>y[1],x[0]>y[0]) et mettre le résultat dans L, on a 2 façon de le faire. On définit L, on tape :

L:=[[1,3],[2,4],[2,3],[1,4]]

L:=sort(L,(x,y)->when(x[0]==y[0],x[1]>y[1],x[0]>y[0]))

Ou on tape :

L:=[[1,3],[2,4],[2,3],[1,4]]

L.sort((x,y)->when(x[0]==y[0],x[1]>y[1],x[0]>y[0]))

On obtient comme nouvelle valeur de L :

[[2,4],[2,3],[1,4],[1,3]]