Cómo ordenar una matriz en Bash

Tengo una matriz en Bash, por ejemplo:

array=(acbf 3 5) 

Necesito ordenar la matriz. No solo muestra el contenido de una manera ordenada, sino que obtiene una nueva matriz con los elementos ordenados. La nueva matriz ordenada puede ser completamente nueva o antigua.

Realmente no necesitas todo ese código:

 IFS=$'\n' sorted=($(sort <<<"${array[*]}")) unset IFS 

Admite espacio en blanco en elementos (siempre que no sea una nueva línea) y funciona en Bash 3.x.

p.ej:

 $ array=("ac" bf "3 5") $ IFS=$'\n' sorted=($(sort <<<"${array[*]}")) $ printf "[%s]\n" "${sorted[@]}" [3 5] [ac] [b] [f] 

Nota: @sorontar ha señalado que se requiere cuidado si los elementos contienen comodines como * o ? :

La parte ordenada = ($ (...)) usa el operador "dividir y agrupar". Debe desactivar glob: set -f o set -o noglob o shopt -op noglob o un elemento de la matriz como * se ampliará a una lista de archivos.

Qué esta pasando:

El resultado es una culminación de seis cosas que suceden en este orden:

  1. IFS=$'\n'
  2. "${array[*]}"
  3. <<<
  4. sort
  5. sorted=($(...))
  6. unset IFS

Primero, el IFS=$'\n'

Esta es una parte importante de nuestra operación que afecta el resultado de 2 y 5 de la siguiente manera:

Dado:

  • "${array[*]}" expande a cada elemento delimitado por el primer carácter de IFS
  • sorted=() crea elementos dividiendo en cada carácter de IFS

IFS=$'\n' configura las cosas para que los elementos se expandan usando una nueva línea como el delimitador, y luego se crean de manera que cada línea se convierte en un elemento. (es decir, división en una nueva línea)

La delimitación por una nueva línea es importante porque así es como funciona sort (clasificación por línea). Dividir solo una nueva línea no es tan importante, pero es necesario conservar los elementos que contienen espacios o tabs.

El valor predeterminado de IFS es un espacio , una pestaña , seguido de una nueva línea , y no sería apto para nuestra operación.

Luego, la parte de sort <<<"${array[*]}"

<<< , llamado aquí strings , toma la expansión de "${array[*]}" , como se explicó anteriormente, y lo introduce en la entrada estándar de sort .

Con nuestro ejemplo, sort se alimenta con la siguiente cadena:

 ac b f 3 5 

Dado que ordena , produce:

 3 5 ac b f 

A continuación, la parte sorted=($(...))

La parte $(...) , llamada sustitución de comando , hace que su contenido ( sort <<<"${array[*]} ) se ejecute como un comando normal, mientras toma el resultado estándar resultante como el literal que va donde sea $(...) fue

En nuestro ejemplo, esto produce algo similar a simplemente escribir:

 sorted=(3 5 ac b f ) 

sorted se convierte en una matriz que se crea al dividir este literal en cada línea nueva.

Finalmente, el unset IFS

Esto restablece el valor de IFS al valor predeterminado, y es solo una buena práctica.

Es para garantizar que no cause problemas con todo lo que dependa de IFS más adelante en nuestro script. (De lo contrario, tendríamos que recordar que hemos cambiado las cosas, algo que podría ser poco práctico para los scripts complejos).

Respuesta original:

 array=(acb "ff" 3 5) readarray -t sorted < <(for a in "${array[@]}"; do echo "$a"; done | sort) 

salida:

 $ for a in "${sorted[@]}"; do echo "$a"; done 3 5 a b c ff 

Tenga en cuenta que esta versión hace frente a valores que contienen caracteres especiales o espacios en blanco ( excepto líneas nuevas)

Nota: Readarray es compatible con bash 4+.


Editar Basado en la sugerencia de @Dimitre, lo había actualizado a:

 readarray -t sorted < <(printf '%s\0' "${array[@]}" | sort -z | xargs -0n1) 

que tiene el beneficio de incluso entender elementos de clasificación con caracteres de línea nueva incrustados correctamente. Desafortunadamente, como @ruakh indicó correctamente, esto no significaba que el resultado de readarray fuera correcto , porque readarray no tiene opción de usar NUL lugar de nuevas líneas regulares como separadores de línea.

Aquí hay una implementación pura de FastSort Bash:

 #!/bin/bash # quicksorts positional arguments # return is in array qsort_ret qsort() { local pivot i smaller=() larger=() qsort_ret=() (($#==0)) && return 0 pivot=$1 shift for i; do if [[ $i < $pivot ]]; then smaller+=( "$i" ) else larger+=( "$i" ) fi done qsort "${smaller[@]}" smaller=( "${qsort_ret[@]}" ) qsort "${larger[@]}" larger=( "${qsort_ret[@]}" ) qsort_ret=( "${smaller[@]}" "$pivot" "${larger[@]}" ) } 

Usar como, por ejemplo,

 $ array=(acbf 3 5) $ qsort "${array[@]}" $ declare -p qsort_ret declare -a qsort_ret='([0]="3" [1]="5" [2]="a" [3]="b" [4]="c" [5]="f")' 

Esta implementación es recursiva ... así que aquí hay una solución rápida iterativa:

 #!/bin/bash # quicksorts positional arguments # return is in array qsort_ret # Note: iterative, NOT recursive! :) qsort() { (($#==0)) && return 0 local stack=( 0 $(($#-1)) ) beg end i pivot smaller larger qsort_ret=("$@") while ((${#stack[@]})); do beg=${stack[0]} end=${stack[1]} stack=( "${stack[@]:2}" ) smaller=() larger=() pivot=${qsort_ret[beg]} for ((i=beg+1;i<=end;++i)); do if [[ "${qsort_ret[i]}" < "$pivot" ]]; then smaller+=( "${qsort_ret[i]}" ) else larger+=( "${qsort_ret[i]}" ) fi done qsort_ret=( "${qsort_ret[@]:0:beg}" "${smaller[@]}" "$pivot" "${larger[@]}" "${qsort_ret[@]:end+1}" ) if ((${#smaller[@]}>=2)); then stack+=( "$beg" "$((beg+${#smaller[@]}-1))" ); fi if ((${#larger[@]}>=2)); then stack+=( "$((end-${#larger[@]}+1))" "$end" ); fi done } 

En ambos casos, puede cambiar el orden que usa: utilicé comparaciones de cadenas, pero puede usar comparaciones aritméticas, comparar el tiempo de modificación del archivo wrt, etc. simplemente use la prueba adecuada; incluso puede hacerlo más genérico y hacer que use un primer argumento que es el uso de la función de prueba, por ejemplo,

 #!/bin/bash # quicksorts positional arguments # return is in array qsort_ret # Note: iterative, NOT recursive! :) # First argument is a function name that takes two arguments and compares them qsort() { (($#<=1)) && return 0 local compare_fun=$1 shift local stack=( 0 $(($#-1)) ) beg end i pivot smaller larger qsort_ret=("$@") while ((${#stack[@]})); do beg=${stack[0]} end=${stack[1]} stack=( "${stack[@]:2}" ) smaller=() larger=() pivot=${qsort_ret[beg]} for ((i=beg+1;i<=end;++i)); do if "$compare_fun" "${qsort_ret[i]}" "$pivot"; then smaller+=( "${qsort_ret[i]}" ) else larger+=( "${qsort_ret[i]}" ) fi done qsort_ret=( "${qsort_ret[@]:0:beg}" "${smaller[@]}" "$pivot" "${larger[@]}" "${qsort_ret[@]:end+1}" ) if ((${#smaller[@]}>=2)); then stack+=( "$beg" "$((beg+${#smaller[@]}-1))" ); fi if ((${#larger[@]}>=2)); then stack+=( "$((end-${#larger[@]}+1))" "$end" ); fi done } 

Entonces puedes tener esta función de comparación:

 compare_mtime() { [[ $1 -nt $2 ]]; } 

y use:

 $ qsort compare_mtime * $ declare -p qsort_ret 

tener los archivos en la carpeta actual ordenados por hora de modificación (los más nuevos primero).

NOTA. Estas funciones son pura Bash! ¡sin utilidades externas ni subcapas! están seguros de cualquier símbolo divertido que pueda tener (espacios, caracteres de nueva línea, caracteres glob, etc.).

Si no necesita manejar caracteres de shell especiales en los elementos de la matriz:

 array=(acbf 3 5) sorted=($(printf '%s\n' "${array[@]}"|sort)) 

Con bash necesitarás un progtwig de clasificación externo de todos modos.

Con zsh no se necesitan progtwigs externos y los caracteres de shell especiales se manejan fácilmente:

 % array=('aa' cbf 3 5); printf '%s\n' "${(o)array[@]}" 3 5 aa b c f 

ksh ha set -s para ordenar ASCIIbetically .

En el viaje de 3 horas en tren desde Munich a Frankfurt (que tuve problemas para llegar porque Oktoberfest comienza mañana) estaba pensando en mi primera publicación. Emplear una matriz global es una idea mucho mejor para una función de clasificación general. La siguiente función maneja cadenas arbitrarias (líneas nuevas, espacios en blanco, etc.):

 declare BSORT=() function bubble_sort() { # # @param [ARGUMENTS]... # # Sort all positional arguments and store them in global array BSORT. # Without arguments sort this array. Return the number of iterations made. # # Bubble sorting lets the heaviest element sink to the bottom. # (($# > 0)) && BSORT=("$@") local j=0 ubound=$((${#BSORT[*]} - 1)) while ((ubound > 0)) do local i=0 while ((i < ubound)) do if [ "${BSORT[$i]}" \> "${BSORT[$((i + 1))]}" ] then local t="${BSORT[$i]}" BSORT[$i]="${BSORT[$((i + 1))]}" BSORT[$((i + 1))]="$t" fi ((++i)) done ((++j)) ((--ubound)) done echo $j } bubble_sort acb 'zy' 3 5 echo ${BSORT[@]} 

Esto imprime:

 3 5 abczy 

El mismo resultado se crea a partir de

 BSORT=(acb 'zy' 3 5) bubble_sort echo ${BSORT[@]} 

Tenga en cuenta que probablemente Bash utiliza internamente punteros inteligentes, por lo que la operación de intercambio podría ser barata (aunque lo dudo). Sin embargo, bubble_sort demuestra que funciones más avanzadas como merge_sort también están al scope del lenguaje de shell.

tl; dr :

Ordenar matriz a_in y almacenar el resultado en a_out (los elementos no deben tener líneas nuevas incrustadas [1] ):

Bash v4 +:

 readarray -t a_out < <(printf '%s\n' "${a_in[@]}" | sort) 

Bash v3:

 IFS=$'\n' read -d '' -r -a a_out < <(printf '%s\n' "${a_in[@]}" | sort) 

Ventajas sobre la solución de antak :

  • No necesita preocuparse por los globbing accidentales (interpretación accidental de los elementos de la matriz como patrones de nombre de archivo), por lo que no es necesario ningún comando adicional para desactivar globbing ( set -f , y set +f para restaurarlo más tarde).

  • No necesita preocuparse por reiniciar IFS con IFS sin unset IFS . [2]


Lectura opcional: explicación y código de muestra

Lo anterior combina el código Bash con sort utilidad externa para una solución que funciona con elementos arbitrarios de línea única y clasificación léxica o numérica (opcionalmente por campo) :

  • Rendimiento : por alrededor de 20 elementos o más , esto será más rápido que una solución Bash pura , de manera significativa y cada vez mayor, una vez que supere los 100 elementos.
    (Los umbrales exactos dependerán de su entrada, máquina y plataforma específicas).

    • La razón por la que es rápido es que evita los bucles Bash .
  • printf '%s\n' "${a_in[@]}" | sort printf '%s\n' "${a_in[@]}" | sort la ordenación (léxicamente, de forma predeterminada, consulte la especificación POSIX de sort ):

    • "${a_in[@]}" expande con seguridad a los elementos de la matriz a_in como argumentos individuales , independientemente de lo que contengan (incluido el espacio en blanco).

    • printf '%s\n' luego imprime cada argumento, es decir, cada elemento de la matriz, en su propia línea, tal como está.

  • Tenga en cuenta el uso de una sustitución de proceso ( <(...) ) para proporcionar la salida ordenada como entrada para read / readarray (a través de la redirección a stdin, < ), porque read / readarray debe ejecutarse en el shell actual (no debe ejecutarse una subshell ) para que la variable de salida a_out sea ​​visible para el shell actual (para que la variable permanezca definida en el rest del script).

  • Lectura del resultado de sort en una variable de matriz :

    • Bash v4 +: readarray -t a_out lee las líneas individuales de salida readarray -t a_out en los elementos de la variable de matriz a_out , sin incluir el trailing \n en cada elemento ( -t ).

    • Bash v3: readarray no existe, por lo que se debe read :
      IFS=$'\n' read -d '' -r -a a_out dice read to read en la variable array ( -a ) a_out , leyendo toda la entrada, a través de las líneas ( -d '' ), pero dividiéndola en elementos de la matriz por líneas nuevas ( IFS=$'\n' . $'\n' , que produce una nueva línea literal (LF), es una cadena denominada ANSI C-quote ).
      ( -r , una opción que debe usarse casi siempre con read , deshabilita el manejo inesperado de \ characters).

Código de muestra anotado:

 #!/usr/bin/env bash # Define input array `a_in`: # Note the element with embedded whitespace ('a c')and the element that looks like # a glob ('*'), chosen to demonstrate that elements with line-internal whitespace # and glob-like contents are correctly preserved. a_in=( 'ac' bf 5 '*' 10 ) # Sort and store output in array `a_out` # Saving back into `a_in` is also an option. IFS=$'\n' read -d '' -r -a a_out < <(printf '%s\n' "${a_in[@]}" | sort) # Bash 4.x: use the simpler `readarray -t`: # readarray -t a_out < <(printf '%s\n' "${a_in[@]}" | sort) # Print sorted output array, line by line: printf '%s\n' "${a_out[@]}" 

Debido al uso de sort sin opciones, esto produce clasificación léxica (los dígitos se clasifican antes que las letras, y las secuencias de dígitos se tratan léxicamente, no como números):

 * 10 5 ac b f 

Si quisieras ordenar por orden numérico en el primer campo, sort -k1,1n lugar de solo sort , lo que da como resultado (los números no se ordenan antes que los números, y los números se ordenan correctamente):

 * ac b f 5 10 

[1] Para manejar elementos con líneas nuevas incrustadas, use la siguiente variante (Bash v4 +, con sort GNU ):
readarray -d '' -t a_out < <(printf '%s\0' "${a_in[@]}" | sort -z) .
La útil respuesta de Michał Górny tiene una solución Bash v3.

[2] Mientras que IFS se establece en la variante de Bash v3, el cambio tiene el scope del comando .
Por el contrario, lo que sigue a IFS=$'\n' en la respuesta de antak es una asignación en lugar de un comando, en cuyo caso el cambio de IFS es global .

Otra solución que utiliza sort externa y se adapta a cualquier carácter especial (excepto NULs :)). Debería funcionar con bash-3.2 y GNU o BSD sort (tristemente, POSIX no incluye -z ).

 local e new_array=() while IFS= read -r -d '' e; do new_array+=( "${e}" ) done < <(printf "%s\0" "${array[@]}" | LC_ALL=C sort -z) 

Primero mira la redirección de entrada al final. Estamos utilizando printf incorporado para escribir los elementos de la matriz, terminados en cero. El presupuesto asegura que los elementos de la matriz se pasen tal cual, y los detalles de shell printf hacen que reutilice la última parte de la cadena de formato para cada parámetro restante. Es decir, es equivalente a algo así como:

 for e in "${array[@]}"; do printf "%s\0" "${e}" done 

La lista de elementos terminados en nulo se pasa a sort . La opción -z hace que lea elementos terminados en nulo, los clasifique y dé como resultado también terminados en nulo. Si necesita obtener solo los elementos únicos, puede pasar -u ya que es más portátil que uniq -z . El LC_ALL=C garantiza un orden de clasificación estable independientemente de la configuración regional, a veces útil para los scripts. Si desea que el sort respete la configuración regional, elimínelo.

La construcción <() obtiene el descriptor para leer desde la tubería generada, y < redirecciona la entrada estándar del ciclo while a ella. Si necesita acceder a la entrada estándar dentro de la tubería, puede usar otro descriptor: ejercicio para el lector :).

Ahora, de vuelta al principio. La read incorporada lee el resultado del stdin redireccionado. Establecer IFS vacío deshabilita la división de palabras que aquí no es necesaria; como resultado, read lee toda la 'línea' de entrada a la única variable proporcionada. -r opción deshabilita el procesamiento de escape que no se desea aquí también. Finalmente, -d '' establece el delimitador de línea en NUL, es decir, le dice a read para leer cadenas terminadas en cero.

Como resultado, el ciclo se ejecuta una vez por cada elemento de matriz terminado en cero sucesivo, con el valor almacenado en e . El ejemplo simplemente coloca los elementos en otra matriz, pero es posible que prefiera procesarlos directamente :).

Por supuesto, esa es solo una de las muchas maneras de lograr el mismo objective. Tal como lo veo, es más simple que implementar un algoritmo de clasificación completo en bash y en algunos casos será más rápido. Maneja todos los caracteres especiales, incluidas las líneas nuevas, y debería funcionar en la mayoría de los sistemas comunes. Lo que es más importante, puede enseñarte algo nuevo e increíble sobre bash :).

prueba esto:

 echo ${array[@]} | awk 'BEGIN{RS=" ";} {print $1}' | sort 

La salida será:

 3
 5
 un
 segundo
 do
 F

Problema resuelto.

Si puede calcular un número entero único para cada elemento en la matriz, así:

 tab='0123456789abcdefghijklmnopqrstuvwxyz' # build the reversed ordinal map for ((i = 0; i < ${#tab}; i++)); do declare -g ord_${tab:i:1}=$i done function sexy_int() { local sum=0 local i ch ref for ((i = 0; i < ${#1}; i++)); do ch="${1:i:1}" ref="ord_$ch" (( sum += ${!ref} )) done return $sum } sexy_int hello echo "hello -> $?" sexy_int world echo "world -> $?" 

luego, puede usar estos enteros como índices de matriz, porque Bash siempre usa una matriz dispersa, por lo que no debe preocuparse por los índices no utilizados:

 array=(acbf 3 5) for el in "${array[@]}"; do sexy_int "$el" sorted[$?]="$el" done echo "${sorted[@]}" 
  • Pros. Rápido.
  • Contras. Los elementos duplicados se combinan y puede ser imposible mapear contenidos en enteros únicos de 32 bits.
 array=(acbf 3 5) new_array=($(echo "${array[@]}" | sed 's/ /\n/g' | sort)) echo ${new_array[@]} 

El contenido de eco de new_array será:

 3 5 abcf 

tipo min:

 #!/bin/bash array=(.....) index_of_element1=0 while (( ${index_of_element1} < ${#array[@]} )); do element_1="${array[${index_of_element1}]}" index_of_element2=$((index_of_element1 + 1)) index_of_min=${index_of_element1} min_element="${element_1}" for element_2 in "${array[@]:$((index_of_element1 + 1))}"; do min_element="`printf "%s\n%s" "${min_element}" "${element_2}" | sort | head -n+1`" if [[ "${min_element}" == "${element_2}" ]]; then index_of_min=${index_of_element2} fi let index_of_element2++ done array[${index_of_element1}]="${min_element}" array[${index_of_min}]="${element_1}" let index_of_element1++ done 

No estoy convencido de que necesites un progtwig de clasificación externo en Bash.

Aquí está mi implementación para el algoritmo simple de sortear burbujas.

 function bubble_sort() { # # Sorts all positional arguments and echoes them back. # # Bubble sorting lets the heaviest (longest) element sink to the bottom. # local array=($@) max=$(($# - 1)) while ((max > 0)) do local i=0 while ((i < max)) do if [ ${array[$i]} \> ${array[$((i + 1))]} ] then local t=${array[$i]} array[$i]=${array[$((i + 1))]} array[$((i + 1))]=$t fi ((i += 1)) done ((max -= 1)) done echo ${array[@]} } array=(acbf 3 5) echo " input: ${array[@]}" echo "output: $(bubble_sort ${array[@]})" 

Esto imprimirá:

  input: acbf 3 5 output: 3 5 abcf 
 a=(eb 'c d') shuf -e "${a[@]}" | sort >/tmp/f mapfile -tg  

Hay una solución para el problema habitual de espacios y nuevas líneas:

Use un carácter que no esté en la matriz original (como $'\1' o $'\4' o similar).

Esta función hace el trabajo:

 # Sort an Array may have spaces or newlines with a workaround (wa=$'\4') sortarray(){ local wa=$'\4' IFS='' if [[ $* =~ [$wa] ]]; then echo "$0: error: array contains the workaround char" >&2 exit 1 fi set -f; local IFS=$'\n' x nl=$'\n' set -- $(printf '%s\n' "${@//$nl/$wa}" | sort -n) for x do sorted+=("${x//$wa/$nl}") done } 

Esto ordenará la matriz:

 $ array=( ab 'cd' $'e\nf' $'g\1h') $ sortarray "${array[@]}" $ printf '<%s>\n' "${sorted[@]}"      

Esto se quejará de que la matriz de origen contiene el carácter de solución temporal:

 $ array=( ab 'cd' $'e\nf' $'g\4h') $ sortarray "${array[@]}" ./script: error: array contains the workaround char 

descripción

  • Establecemos dos variables locales wa (solución temporal char) y un IFS nulo
  • Luego (con ifs null) probamos que toda la matriz $* .
  • No contiene ningún char de woraround [[ $* =~ [$wa] ]] .
  • Si es así, genera un mensaje y señala un error: exit 1
  • Evite expansiones de nombre de archivo: set -f
  • Establezca un nuevo valor de IFS ( IFS=$'\n' ) una variable de bucle x una nueva línea var ( nl=$'\n' ).
  • Imprimimos todos los valores de los argumentos recibidos (la matriz de entrada $@ ).
  • pero reemplazamos cualquier línea nueva por la solución alternativa char "${@//$nl/$wa}" .
  • envíe esos valores para sort -n .
  • y colocar todos los valores ordenados en los argumentos posicionales set -- .
  • Luego asignamos cada argumento uno por uno (para preservar las nuevas líneas).
  • en un bucle for x
  • a una nueva matriz: sorted+=(…)
  • cotizaciones internas para preservar cualquier nueva línea existente.
  • restaurar la solución a una nueva línea "${x//$wa/$nl}" .
  • hecho

sorted=($(echo ${array[@]} | tr " " "\n" | sort))

En el espíritu de bash / linux, utilizaría la mejor herramienta de línea de comandos para cada paso. sort hace el trabajo principal pero necesita entradas separadas por línea nueva en lugar de espacio, por lo que la tubería más simple arriba simplemente lo hace:

Contenido de matriz de eco -> reemplazar espacio por línea nueva -> ordenar

$() es repetir el resultado

($()) es poner el “resultado repetido” en una matriz

Nota : como @sorontar mencionó en un comentario a una pregunta diferente:

La parte ordenada = ($ (…)) usa el operador “dividir y agrupar”. Debe desactivar glob: configure -f o establezca -o noglob o shopt -op noglob o un elemento de la matriz como * se ampliará a una lista de archivos.