Tableau de tri Bash selon la longueur des éléments?

Étant donné un tableau de chaînes, je voudrais trier le tableau en fonction de la longueur de chaque élément.

Par exemple...

    array=(
    "tiny string"
    "the longest string in the list"
    "middle string"
    "medium string"
    "also a medium string"
    "short string"
    )

Devrait trier pour ...

    "the longest string in the list"
    "also a medium string"
    "medium string"
    "middle string"
    "short string"
    "tiny string"

(En prime, il serait bien que la liste trie les chaînes de la même longueur, par ordre alphabétique. Dans l'exemple ci-dessus, elles ont medium stringété triées avant middle stringmême si elles sont de la même longueur. Mais ce n'est pas une exigence "difficile", si cela complique trop la Solution).

C'est OK si le tableau est trié sur place (c'est-à-dire que "tableau" est modifié) ou si un nouveau tableau trié est créé.

Si les chaînes ne contiennent pas de sauts de ligne, ce qui suit devrait fonctionner. Il trie les indices du tableau par longueur, en utilisant les chaînes elles-mêmes comme critère de tri secondaire.

#!/bin/bash
array=(
    "tiny string"
    "the longest string in the list"
    "middle string"
    "medium string"
    "also a medium string"
    "short string"
)
expected=(
    "the longest string in the list"
    "also a medium string"
    "medium string"
    "middle string"
    "short string"
    "tiny string"
)

indexes=( $(
    for i in "${!array[@]}" ; do
        printf '%s %s %s\n' $i "${#array[i]}" "${array[i]}"
    done | sort -nrk2,2 -rk3 | cut -f1 -d' '
))

for i in "${indexes[@]}" ; do
    sorted+=("${array[i]}")
done

diff <(echo "${expected[@]}") \
     <(echo "${sorted[@]}")

Notez que le passage à un vrai langage de programmation peut grandement simplifier la solution, par exemple en Perl, vous pouvez simplement

sort { length $b <=> length $a or $a cmp $b } @array

readarray -t array < <(
for str in "${array[@]}"; do
    printf '%d\t%s\n' "${#str}" "$str"
done | sort -k 1,1nr -k 2 | cut -f 2- )

Cela lit les valeurs du tableau trié à partir d'une substitution de processus.

La substitution de processus contient une boucle. La boucle affiche chaque élément du tableau précédé de la longueur de l'élément et d'un caractère de tabulation entre les deux.

La sortie de la boucle est triée numériquement du plus grand au plus petit (et par ordre alphabétique si les longueurs sont les mêmes, l' utilisation -k 2rà la place de -k 2renverser l'ordre alphabétique) et le résultat de c'est envoyé à qui supprime la colonne avec les longueurs de chaîne.cut

Tri du script de test suivi d'une exécution de test:

array=(
    "tiny string"
    "the longest string in the list"
    "middle string"
    "medium string"
    "also a medium string"
    "short string"
)

readarray -t array < <(
for str in "${array[@]}"; do
    printf '%d\t%s\n' "${#str}" "$str"
done | sort -k 1,1nr -k 2 | cut -f 2- )

printf '%s\n' "${array[@]}"

$ bash script.sh
the longest string in the list
also a medium string
medium string
middle string
short string
tiny string

Cela suppose que les chaînes ne contiennent pas de sauts de ligne. Sur les systèmes GNU avec un récent bash, vous pouvez prendre en charge les sauts de ligne intégrés dans les données en utilisant le caractère nul comme séparateur d'enregistrement au lieu du saut de ligne:

readarray -d '' -t array < <(
for str in "${array[@]}"; do
    printf '%d\t%s\0' "${#str}" "$str"
done | sort -z -k 1,1nr -k 2 | cut -z -f 2- )

Ici, les données sont imprimées avec la fin \0de la boucle au lieu des sauts de ligne, sortet cutlit les lignes délimitées par le biais de leurs -zoptions GNU et readarraylit finalement les données délimitées par -d ''.

Je ne répéterai pas complètement ce que j'ai déjà dit sur le tri dans bash , vous pouvez simplement trier dans bash, mais peut-être que vous ne devriez pas. Vous trouverez ci-dessous une implémentation bash uniquement d'un tri par insertion, qui est O (n ² ), et n'est donc tolérable que pour les petits tableaux. Il trie les éléments du tableau sur place selon leur longueur, dans l'ordre décroissant. Il ne fait pas de tri alphabétique secondaire.

array=(
    "tiny string"
    "the longest string in the list"
    "middle string"
    "medium string"
    "also a medium string"
    "short string"
    )

function sort_inplace {
  local i j tmp
  for ((i=0; i <= ${#array[@]} - 2; i++))
  do
    for ((j=i + 1; j <= ${#array[@]} - 1; j++))
    do
      local ivalue jvalue
        ivalue=${#array[i]}
        jvalue=${#array[j]}
        if [[ $ivalue < $jvalue ]]
        then
                tmp=${array[i]}
                array[i]=${array[j]}
                array[j]=$tmp
        fi
    done
  done
}

echo Initial:
declare -p array

sort_inplace

echo Sorted:
declare -p array

Pour prouver qu'il s'agit d'une solution spécialisée, considérez les délais des trois réponses existantes sur des tableaux de différentes tailles:

# 6 elements
Choroba: 0m0.004s
Kusalananda: 0m0.004s
Jeff: 0m0.018s         ## already 4 times slower!

# 1000 elements
Choroba: 0m0.004s
Kusalananda: 0m0.004s
Jeff: 0m0.021s        ## up to 5 times slower, now!

5000 elements
Choroba: 0m0.004s
Kusalananda: 0m0.004s
Jeff: 0m0.019s

# 10000 elements
Choroba: 0m0.004s
Kusalananda: 0m0.006s
Jeff: 0m0.020s

# 99000 elements
Choroba: 0m0.015s
Kusalananda: 0m0.012s
Jeff: 0m0.119s

Choroba et Kusalananda ont la bonne idée: calculer les longueurs une fois et utiliser des utilitaires dédiés pour le tri et le traitement de texte.

Un hackish? (complexe) et rapide d'une ligne pour trier le tableau par longueur
( sans danger pour les nouvelles lignes et les tableaux clairsemés):

#!/bin/bash
in=(
    "tiny string"
    "the longest
        string also containing
        newlines"
    "middle string"
    "medium string"
    "also a medium string"
    "short string"
    "test * string"
    "*"
    "?"
    "[abc]"
)

readarray -td $'\0' sorted < <(
                    for i in "${in[@]}"
                    do     printf '%s %s\0' "${#i}" "$i";
                    done |
                            sort -bz -k1,1rn -k2 |
                            cut -zd " " -f2-
                    )

printf '%s\n' "${sorted[@]}"

Sur une ligne:

readarray -td $'\0' sorted < <(for i in "${in[@]}";do printf '%s %s\0' "${#i}" "$i"; done | sort -bz -k1,1rn -k2 | cut -zd " " -f2-)

À l'exécution

$ ./script
the longest
        string also containing
        newlines
also a medium string
medium string
middle string
test * string
short string
tiny string
[abc]
?
*

Cela gère également les éléments du tableau avec des retours à la ligne; il fonctionne en ne passant que par sortla longueur et l'index de chaque élément. Cela devrait fonctionner avec bashet ksh.

in=(
    "tiny string"
    "the longest
        string also containing
        newlines"
    "middle string"
    "medium string"
    "also a medium string"
    "short string"
)
out=()

unset IFS
for a in $(for i in ${!in[@]}; do echo ${#in[i]}/$i; done | sort -rn); do
        out+=("${in[${a#*/}]}")
done

printf '"%s"\n' "${out[@]}"

Si les éléments de même longueur doivent également être triés lexicographiquement, la boucle pourrait être modifiée comme ceci:

IFS='
'
for a in $(for i in ${!in[@]}; do printf '%s\n' "$i ${#in[i]} ${in[i]//$IFS/ }"; done | sort -k 2,2nr -k 3 | cut -d' ' -f1); do
        out+=("${in[$a]}")
done

Cela passera également aux sortchaînes (avec les sauts de ligne modifiés en espaces), mais ils seront toujours copiés de la source vers le tableau de destination par leurs index. Dans les deux exemples, le $(...)ne verra que les lignes contenant des nombres (et le /caractère dans le premier exemple), il ne sera donc pas déclenché par des caractères ou des espaces globaux dans les chaînes.

Dans le cas où le passage à zshest une option, un moyen hackish (pour les tableaux contenant n'importe quelle séquence d'octets):

array=('' blah $'x\ny\nz' $'x\0y' '1 2 3')
sorted_array=( /(e'{reply=("$array[@]")}'nOe'{REPLY=$#REPLY}') )

zshpermet de définir des ordres de tri pour son expansion globale via des qualificatifs glob. Donc, ici, nous le trompons pour le faire pour les tableaux arbitraires en les globulant /, mais en les remplaçant /par les éléments du tableau ( e'{reply=("$array[@]")}'), puis en nutilisant umerically o(en sens inverse en majuscules O) les éléments en fonction de leur longueur ( Oe'{REPLY=$#REPLY}').

Notez qu'il est basé sur la longueur en nombre de caractères. Pour le nombre d'octets, définissez les paramètres régionaux sur C( LC_ALL=C).

Une autre bashapproche 4.4+ (en supposant un tableau pas trop grand):

readarray -td '' sorted_array < <(
  perl -l0 -e 'print for sort {length $b <=> length $a} @ARGV
              ' -- "${array[@]}")

(c'est la longueur en octets ).

Avec les anciennes versions de bash, vous pouviez toujours faire:

eval "sorted_array=($(
    perl -l0 -e 'for (sort {length $b <=> length $a} @ARGV) {
      '"s/'/'\\\\''/g"'; printf " '\'%s\''", $_}' -- "${array[@]}"
  ))"

(qui fonctionne également avec ksh93, zsh, yash, mksh).