Como classificar um array no Bash

Eu tenho um array no Bash, por exemplo:

array=(acbf 3 5) 

Eu preciso classificar a matriz. Não apenas exibindo o conteúdo de uma maneira ordenada, mas para obter uma nova matriz com os elementos classificados. O novo array ordenado pode ser completamente novo ou antigo.

Você realmente não precisa de todo esse código:

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

Suporta espaços em branco em elementos (desde que não seja uma nova linha) e funciona no Bash 3.x.

por exemplo:

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

Nota: @sorontar apontou que é necessário cuidado se os elementos contiverem curingas como * ou ? :

A parte classificada = ($ (...)) está usando o operador "split e glob". Você deve desligar o glob: set -f ou set -o noglob ou shopt -op noglob ou um elemento do array como * será expandido para uma lista de arquivos.

O que está acontecendo:

O resultado é uma culminação de seis coisas que acontecem nesta ordem:

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

Primeiro, o IFS=$'\n'

Esta é uma parte importante da nossa operação que afeta o resultado de 2 e 5 da seguinte maneira:

Dado:

  • "${array[*]}" expande para cada elemento delimitado pelo primeiro caractere do IFS
  • sorted=() cria elementos dividindo cada caractere do IFS

IFS=$'\n' configura as coisas para que os elementos sejam expandidos usando uma nova linha como delimitador e, depois, criados de forma que cada linha se torne um elemento. (isto é, divisão em uma nova linha).

Delimitar por uma nova linha é importante porque é assim que a sort funciona (sorting por linha). Dividir por apenas uma nova linha não é tão importante, mas é necessário preservar elementos que contenham espaços ou tabulações.

O valor padrão do IFS é um espaço , uma guia , seguido por uma nova linha e seria inadequado para nossa operação.

Em seguida, o sort < <<"${array[*]}" parte

< << , chamado aqui de strings , pega a expansão de "${array[*]}" , como explicado acima, e a insere na input padrão de sort .

Com nosso exemplo, o sort é alimentado com a seguinte string:

 ac b f 3 5 

Desde sort tipos , produz:

 3 5 ac b f 

Em seguida, a parte sorted=($(...))

A parte $(...) , chamada de substituição de comando , faz com que seu conteúdo ( sort < <<"${array[*]} ) seja executado como um comando normal, enquanto se pega a saída padrão resultante como o literal que vai onde quer que $(...) foi.

Em nosso exemplo, isso produz algo semelhante a simplesmente escrever:

 sorted=(3 5 ac b f ) 

sorted seguida, torna-se uma matriz que é criada dividindo este literal em cada nova linha.

Finalmente, o unset IFS

Isso redefine o valor do IFS para o valor padrão e é apenas uma boa prática.

É para garantir que não causemos problemas com qualquer coisa que dependa do IFS posteriormente em nosso script. (Caso contrário, precisaríamos lembrar que mudamos as coisas - algo que pode ser impraticável para scripts complexos.)

Resposta Original:

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

saída:

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

Observe que esta versão lida com valores que contêm caracteres especiais ou espaço em branco ( exceto novas linhas)

Nota readarray é suportado no bash 4+.


Editar Baseado na sugestão de @Dimitre eu atualizei para:

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

que tem o benefício de entender os elementos de sorting com caracteres de nova linha incorporados corretamente. Infelizmente, como corretamente sinalizado por @ruakh isto não significa que o resultado de readarray estaria correto , porque readarray não tem nenhuma opção para usar NUL invés de novas linhas regulares como separadores de linha.

Aqui está uma implementação pura de quicksort 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[@]}" ) } 

Use como, por exemplo,

 $ 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 implementação é recursiva… então aqui está um quicksort iterativo:

 #!/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 } 

Em ambos os casos, você pode alterar a ordem que você usa: Eu usei comparações de strings, mas você pode usar comparações aritméticas, comparar o tempo de modificação do arquivo wrt, etc. apenas use o teste apropriado; você pode até torná-lo mais genérico e usar um primeiro argumento que seja o uso da function de teste, por exemplo,

 #!/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 } 

Então você pode ter esta function de comparação:

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

E use:

 $ qsort compare_mtime * $ declare -p qsort_ret 

para ter os arquivos na pasta atual classificados por hora de modificação (mais novo primeiro).

NOTA. Essas funções são pura Bash! sem utilitários externos e sem subcontas! eles estão seguros para qualquer símbolo engraçado que você possa ter (espaços, caracteres de nova linha, caracteres glob, etc.).

Se você não precisa manipular caracteres de shell especiais nos elementos da matriz:

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

Com o bash, você precisará de um programa de sorting externo.

Com o zsh, não são necessários programas externos e os caracteres de shell especiais são facilmente manipulados:

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

ksh set -s para classificar ASCIIbeticamente .

Na viagem de trem de 3 horas de Munique a Frankfurt (que tive problemas em alcançar porque a Oktoberfest começa amanhã), eu estava pensando em meu primeiro post. Empregar uma matriz global é uma ideia muito melhor para uma function de sorting geral. A function a seguir manipula cadeias arbitrárias (novas linhas, espaços em branco, 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[@]} 

Isso imprime:

 3 5 abczy 

A mesma saída é criada a partir de

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

Note que, provavelmente, o Bash usa internamente os smart-pointers, então a operação de swap pode ser barata (embora eu duvide). No entanto, bubble_sort demonstra que funções mais avançadas como merge_sort também estão ao alcance da linguagem shell.

tl; dr :

Classifique a matriz a_in e armazene o resultado em a_out (os elementos não devem ter novas linhas incorporadas [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) 

Vantagens sobre a solução da antak :

  • Você não precisa se preocupar com globbing acidental (interpretação acidental dos elementos da matriz como padrões de nome de arquivo), portanto, nenhum comando extra é necessário para desabilitar o globbing ( set -f e set +f para restaurá-lo posteriormente).

  • Você não precisa se preocupar em redefinir o IFS com o unset IFS . [2]


Leitura opcional: explicação e código de amostra

O código acima combina o código Bash com a sort utilitário externo para uma solução que funcione com elementos arbitrários de linha única e sorting lexical ou numérica (opcionalmente por campo) :

  • Desempenho : para cerca de 20 elementos ou mais , isso será mais rápido do que uma solução Bash pura - de forma significativa e cada vez mais, assim que você ultrapassar os 100 elementos.
    (Os limites exatos dependerão da sua input, máquina e plataforma específicas.)

    • A razão é que é rápido, evita loops Bash .
  • printf '%s\n' "${a_in[@]}" | sort printf '%s\n' "${a_in[@]}" | sort realiza a ordenação (lexicalmente, por padrão - veja a especificação POSIX do sort ):

    • "${a_in[@]}" expande-se com segurança para os elementos de array a_in como argumentos individuais , sejam eles quais forem (incluindo espaços em branco).

    • printf '%s\n' , em seguida, imprime cada argumento - ou seja, cada elemento da matriz - em sua própria linha, como está.

  • Observe o uso de uma substituição de processo ( < (...) ) para fornecer a saída classificada como input para read / readarray (por meio de redirecionamento para stdin, < ), porque read / readarray deve ser executado no shell atual (não deve ser executado um subshell ) para que a variável de saída a_out seja visível para o shell atual (para a variável permanecer definida no restante do script).

  • Lendo a saída da sorting em uma variável de matriz :

    • Bash v4 +: readarray -t a_out lê as linhas individuais readarray -t a_out por sort nos elementos da variável de array a_out , sem include o trailing \n em cada elemento ( -t ).

    • Bash v3: readarray não existe, então read deve ser usado:
      IFS=$'\n' read -d '' -r -a a_out diz para ler na variável do array ( -a ) a_out , lendo toda a input, através das linhas ( -d '' ), mas dividindo-a em elementos do array by newlines ( IFS=$'\n' . $'\n' , que produz uma nova linha literal (LF), é uma chamada cadeia de caracteres ANSI C ).
      ( -r , uma opção que deve ser sempre usada com read , desativa o tratamento inesperado de \ caracteres).

Código de amostra 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[@]}" 

Devido ao uso de sort sem opções, isto produz ordenação léxica (digita ordenar antes de letras, e seqüências de dígitos são tratadas lexicalmente, não como números):

 * 10 5 ac b f 

Se você quisesse ordenação numérica no primeiro campo, você usaria o sort -k1,1n invés de apenas sort , o que produz (não-numerais antes dos números e os números ordenados corretamente):

 * ac b f 5 10 

[1] Para manipular elementos com novas linhas incorporadas, use a seguinte variante (Bash v4 +, com sort GNU ):
readarray -d '' -t a_out < <(printf '%s\0' "${a_in[@]}" | sort -z) .
A resposta útil de Michał Górny tem uma solução Bash v3.

[2] Enquanto o IFS é configurado na variante Bash v3, a alteração é definida para o comando .
Por outro lado, o que segue IFS=$'\n' na resposta do antak é uma atribuição em vez de um comando, caso em que a alteração do IFS é global .

Outra solução que usa sort externa e lida com qualquer caractere especial (exceto para NULs :)). Deve funcionar com bash-3.2 e GNU ou BSD (infelizmente, POSIX não inclui -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) 

Primeiro, observe o redirecionamento de input no final. Estamos usando printf built-in para gravar os elementos da matriz, com terminação zero. As citações garantem que os elementos do array sejam passados ​​como estão, e os detalhes do printf do shell fazem com que reutilize a última parte da string de formatação para cada parâmetro restante. Isto é, é equivalente a algo como:

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

A lista de elementos terminados em nulo é então passada para sort . A opção -z faz com que ele leia elementos terminados em nulo, ordene-os e também imprima com terminação nula. Se você precisasse obter apenas os elementos únicos, você pode passar -u pois é mais portátil que uniq -z . O LC_ALL=C assegura uma ordem de sorting estável independentemente do local - por vezes, útil para scripts. Se você quiser que a sort respeite a localidade, remova-a.

A construção < () obtém o descritor para ler do pipeline gerado e < redireciona a input padrão do loop while para ele. Se você precisar acessar a input padrão dentro do pipe, você pode usar outro descritor - exercício para o leitor :).

Agora, de volta ao começo. A read interna lê a saída do stdin redirecionado. Definir o IFS vazio desativa a divisão de palavras, que é desnecessária aqui - como resultado, read lê toda a 'linha' de input para a única variável fornecida. -r opção -r desativa o processamento de escape que é indesejado aqui também. Finalmente, -d '' configura o delimitador de linha para NUL - isto é, diz para ler para ler cadeias terminadas em zero.

Como resultado, o loop é executado uma vez para cada elemento de matriz com terminação zero sucessiva, com o valor sendo armazenado em e . O exemplo apenas coloca os itens em outra matriz, mas você pode preferir processá-los diretamente :).

Claro, essa é apenas uma das muitas maneiras de alcançar o mesmo objective. A meu ver, é mais simples do que implementar o algoritmo de sorting completo no bash e, em alguns casos, será mais rápido. Ele lida com todos os caracteres especiais, incluindo novas linhas e deve funcionar na maioria dos sistemas comuns. Mais importante, pode ensinar algo novo e impressionante sobre o bash :).

tente isto:

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

Saída será:

 3
 5
 uma
 b
 c
 f

Problema resolvido.

Se você puder calcular um inteiro único para cada elemento na matriz, assim:

 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 -> $?" 

então, você pode usar esses inteiros como índices de array, porque Bash sempre usa array esparso, então não precisa se preocupar com índices não utilizados:

 array=(acbf 3 5) for el in "${array[@]}"; do sexy_int "$el" sorted[$?]="$el" done echo "${sorted[@]}" 
  • Prós. Rápido.
  • Cons. Elementos duplicados são mesclados e pode ser impossível mapear o conteúdo para inteiros exclusivos de 32 bits.
 array=(acbf 3 5) new_array=($(echo "${array[@]}" | sed 's/ /\n/g' | sort)) echo ${new_array[@]} 

O conteúdo do eco de new_array será:

 3 5 abcf 

min classificar:

 #!/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 

Não estou convencido de que você precisará de um programa de sorting externo no Bash.

Aqui está minha implementação para o algoritmo simples bubble-sort.

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

Isso deve imprimir:

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

Existe uma solução alternativa para o problema usual de espaços e novas linhas:

Use um caractere que não esteja na matriz original (como $'\1' ou $'\4' ou similar).

Esta function faz o trabalho:

 # 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 } 

Isso irá classificar a matriz:

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

Isso irá reclamar que a matriz de origem contém o caractere de solução alternativa:

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

descrição

  • Nós definimos duas variables ​​locais wa (workaround char) e um IFS nulo
  • Então (com ifs null) testamos toda a array $* .
  • Não contém nenhum char de woraround [[ $* =~ [$wa] ]] .
  • Em caso afirmativo, levante uma mensagem e sinalize um erro: exit 1
  • Evite expansões de nome de arquivo: set -f
  • Defina um novo valor de IFS ( IFS=$'\n' ) uma variável de loop x e uma nova linha var ( nl=$'\n' ).
  • Imprimimos todos os valores dos argumentos recebidos (a matriz de input $@ ).
  • mas substituímos qualquer nova linha pela alternativa "${@//$nl/$wa}" .
  • envie esses valores para serem ordenados sort -n .
  • e coloque de volta todos os valores classificados no set -- argumentos set -- .
  • Em seguida, atribuímos cada argumento um por um (para preservar as novas linhas).
  • em um loop for x
  • para um novo array: sorted+=(…)
  • citações internas para preservar qualquer nova linha existente.
  • restaurar a solução alternativa para uma nova linha "${x//$wa/$nl}" .
  • feito

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

No espírito do bash / linux, eu enviaria a melhor ferramenta de linha de comando para cada etapa. sort faz o job principal mas precisa de input separada por newline ao invés de espaço, então o pipeline muito simples acima simplesmente faz:

Conteúdo da matriz de eco -> replace espaço por nova linha -> classificar

$() é fazer eco do resultado

($()) é colocar o “resultado ecoado” em uma matriz

Nota : como @sorontar mencionado em um comentário para uma pergunta diferente:

A parte classificada = ($ (…)) está usando o operador “split e glob”. Você deve desligar o glob: set -f ou set -o noglob ou shopt -op noglob ou um elemento do array como * será expandido para uma lista de arquivos.