6.41.20  Trier : sort

sort a comme argument une liste ou une expression ou une chaine de caractères.

• Pour une liste, sort renvoie la liste triée selon l’ordre croissant.
  On tape :
  sort([3,4,2])
  On obtient :
  [2,3,4]
  Remarque 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]]
  Pour trier par ordre décroissant il faut mettre en second argument une fonction de tri, par exemple on tape la fonction booléenne superoueg qui renvoie 1 si L1>=L2 et 0 sinon :
  

  superoueg(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 superoueg soit aussi valable pour les chaines de caractères. On tape :
  sort([[3,4,2],[4,2,3],[2,3,4],[2,4,3]],superoueg)
  ou on tape
  sort([[3,4,2],[4,2,3],[2,3,4],[2,4,3]],(x,y)->superoueg(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]]
  On tape :
  sort(["dac","bac","sac","asc","cab"])
  On obtient :
  ["asc","bac","cab","dac","sac"]
  On tape :
  sort(["dac","bac","sac","asc","cab"],superoueg)
  On obtient :
  ["sac","dac","cab","bac","asc"]
• Pour une expression, sort trie et collecte les termes égaux dans les sommes et produits.
  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

Remarque
sort accepte un 2-ième argument après une liste qui est la fonction de tri, par exemple (x,y)->x>y pour avoir la liste triée selon l’ordre décroissant.
Attention La fonction de tri f doit définir un ordre strict faible c’est à dire que

• f(x,y) est un fonction renvoyant 0 (faux) ou 1 (vrai) qui est toujours définie (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 (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.

Sinon l’algorithme employé risque de boucler.... Par exemple, on ne peut pas mettre comme fonction de tri : (x,y)->x[1]>=y[1]. On tape :

On obtient :

Pour trier des listes de listes
sort trie les listes de listes par ordre croissant.

On obtient :

Pour un ordre différent, il faut mettre une fonction de tri comme 2ième argument.
Par exemple :
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).
On tape :

On obtient :

Et 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 :

On obtient :

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.