Bash sort array según la longitud de los elementos?

Dada una matriz de cadenas, me gustaría ordenar la matriz de acuerdo con la longitud de cada elemento.

Por ejemplo...

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

Debería ordenar a ...

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

(Como beneficio adicional, sería bueno si la lista ordenara las cadenas de la misma longitud, alfabéticamente. En el ejemplo anterior medium stringse ordenó antes middle stringaunque sean de la misma longitud. Pero eso no es un requisito "difícil", si complica demasiado solución).

Está bien si la matriz se ordena in situ (es decir, se modifica "matriz") o si se crea una nueva matriz ordenada.

Si las cadenas no contienen nuevas líneas, lo siguiente debería funcionar. Ordena los índices de la matriz por la longitud, utilizando las propias cadenas como criterio secundario de clasificación.

#!/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[@]}")

Tenga en cuenta que pasar a un lenguaje de programación real puede simplificar enormemente la solución, por ejemplo, en Perl, puede simplemente

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- )

Esto lee los valores de la matriz ordenada de una sustitución de proceso.

La sustitución del proceso contiene un bucle. El bucle genera cada elemento de la matriz antepuesto por la longitud del elemento y un carácter de tabulación intermedio.

La salida del bucle se ordena numéricamente de mayor a menor (y alfabéticamente si las longitudes son las mismas; úselas -k 2ren lugar de -k 2revertir el orden alfabético) y el resultado de eso se envía y cutelimina la columna con las longitudes de cadena.

Ordenar script de prueba seguido de una ejecución de prueba:

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

Esto supone que las cadenas no contienen nuevas líneas. En los sistemas GNU con un reciente bash, puede admitir nuevas líneas incrustadas en los datos utilizando el carácter nul como separador de registros en lugar de nueva línea:

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- )

Aquí, los datos se imprimen con un seguimiento \0en el bucle en lugar de líneas nuevas, sorty cutlee líneas delimitadas por nul a través de sus -zopciones GNU y readarrayfinalmente lee los datos delimitados por nul con -d ''.

No voy a repetir por completo lo que ya he dicho acerca de la clasificación en bash , simplemente se puede clasificar dentro de fiesta, pero tal vez no deberías. A continuación se muestra una implementación solo de bash de un tipo de inserción, que es O (n ² ), por lo que solo es tolerable para matrices pequeñas. Ordena los elementos de la matriz en su lugar por su longitud, en orden decreciente. No hace un orden alfabético secundario.

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

Como evidencia de que esta es una solución especializada, considere los tiempos de las tres respuestas existentes en varias matrices de tamaños:

# 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 y Kusalananda tienen la idea correcta: calcular las longitudes una vez y usar utilidades dedicadas para la clasificación y el procesamiento de texto.

Un hackish? (complejo) y una forma rápida de una línea para ordenar la matriz por longitud
( seguro para líneas nuevas y matrices dispersas):

#!/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[@]}"

En una línea:

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

En ejecución

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

Esto también maneja elementos de matriz con nuevas líneas en ellos; funciona pasando sortsolo por la longitud y el índice de cada elemento. Debería funcionar con bashy 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 los elementos de la misma longitud también tienen que clasificarse lexicográficamente, el bucle podría cambiarse así:

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

Esto también pasará a sortlas cadenas (con las nuevas líneas cambiadas a espacios), pero sus índices seguirán copiando de la matriz de origen a la de destino. En ambos ejemplos, $(...)verá solo líneas que contengan números (y el /carácter en el primer ejemplo), por lo que no se disparará mediante caracteres globales o espacios en las cadenas.

En caso de que cambiar a zshsea ​​una opción, una forma hackea allí (para matrices que contienen cualquier secuencia de bytes):

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

zshpermite definir órdenes de clasificación para su expansión global mediante calificadores globales. Así que aquí, nos estamos engañando a hacerlo por las matrices arbitrarias por parte de comodines en /, pero sustituyendo /con los elementos de la matriz ( e'{reply=("$array[@]")}') y luego numerically order (a la inversa, con mayúscula O) los elementos en función de su longitud ( Oe'{REPLY=$#REPLY}').

Tenga en cuenta que se basa en la longitud en número de caracteres. Para el número de bytes, establezca la configuración regional en C( LC_ALL=C).

Otro bashenfoque 4.4+ (suponiendo una matriz no demasiado grande):

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

(eso es longitud en bytes ).

Con versiones anteriores de bash, siempre puedes hacer:

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

(que también funcionaría con ksh93, zsh, yash, mksh).