Como criar uma função que pode classificar uma matriz no bash?

Question

Estou tentando descobrir como criar uma função que possa usar um array como parâmetro e classificá-lo. Eu acho que é feito com variáveis posicionais, mas não tenho certeza.

    

Answer 1

Classifique o caminho fácil com sort , tr :

arr=($(for i in {0..9}; do echo $((RANDOM%100)); done))
echo ${arr[*]}| tr " " "\n" | sort -n | tr "\n" " "

Em uma nova matriz:

arr2=($(echo ${arr[*]}| tr " " "\n" | sort -n))

Sem ajuda de tr / sort , por exemplo bubblesort:

#!/bin/bash    
sort () {
    for ((i=0; i <= $((${#arr[@]} - 2)); ++i))
    do
        for ((j=((i + 1)); j <= ((${#arr[@]} - 1)); ++j))
        do
            if [[ ${arr[i]} -gt ${arr[j]} ]]
            then
                # echo $i $j ${arr[i]} ${arr[j]}
                tmp=${arr[i]}
                arr[i]=${arr[j]}
                arr[j]=$tmp         
            fi
        done
    done
}
# arr=(6 5 68 43 82 60 45 19 78 95)
arr=($(for i in {0..9}; do echo $((RANDOM%100)); done))
echo ${arr[@]}
sort ${arr[@]}
echo ${arr[@]}

Para 20 números, o bubblesort pode ser suficiente.

    

Answer 2

bash

Eu não acho que o bash tenha suporte interno para isso ainda. As opções seriam implementar manualmente um algoritmo de classificação ou invocar sort para fazer a classificação.

Se considerarmos que os elementos da matriz podem conter qualquer valor de byte, mas 0 em bash , para fazer isso de forma confiável, precisaríamos passar a lista de elementos delimitados por NUL e usar a opção -z para sort (fora do padrão, mas disponível no tipo GNU ou no tipo FreeBSD).

O

bash-4.4 (lançado em setembro de 2016) facilita a introdução de uma opção -d em seu readarray builtin para especificar o delimitador.

Para classificar a matriz a na matriz b :

readarray -td '' b < <(printf '%s
sortarray() for array do
  readarray -tf '' "$array" < <(
    eval "printf '%s
b=()
while IFS= read -rd '' item; do b+=("$item"); done < <(
  printf '%s
sortarray() for array do eval '
  tmp=()
  while IFS= read -rd "" item; do tmp+=("$item"); done < <(
    printf "%s
$ a=('' 12 2 d é f $'a\nb')
$ printf '<%s>\n' "${(@o)a}"
<>
<12>
<2>
<a
b>
<d>
<é>
<f>
$ printf '<%s>\n' "${(@no)a}"
<>
<2>
<12>
<a
b>
<d>
<é>
<f>
" "${'"$array"'[@]}" | sort -z)
  '"$array"'=("${tmp[@]}")'
done
' "${a[@]}" | sort -z)
' \"\${$array[@]}\" | sort -z")
done
' "${a[@]}" | sort -z)

classificaria o array de forma confiável. Use as opções -n , -r para sort para classificar numericamente ou em ordem inversa (ou qualquer critério de classificação suportado por sort ).

Para implementar sua função sortarray (classifica todos os arrays passados por nome como argumentos):

b=("${(@o)a}")

Com versões anteriores de bash , você pode usar read -d em um loop para obter o mesmo:

sortarray() for array do eval "$array=(\"\${(@o)$array}\")"; done

Para a função sortarray :

set -s -- "${a[@]}"
b=("$@")

zsh

O Zsh tem suporte embutido para classificar matrizes.

você pode usar o sinalizador de expansão do parâmetro o para classificar lexicalmente ( O para ordem inversa). Você pode adicionar o sinalizador n para ordenar numericamente:

sortarray() for array do
  eval 'set -s -- "${'"$array"'[@]}"; '"$array"'=("$@")'
done

Em localidades que ainda não classificam caso de forma independente, você também pode adicionar o sinalizador i para isso.

Para atribuir a uma matriz:

readarray -td '' b < <(printf '%s
sortarray() for array do
  readarray -tf '' "$array" < <(
    eval "printf '%s
b=()
while IFS= read -rd '' item; do b+=("$item"); done < <(
  printf '%s
sortarray() for array do eval '
  tmp=()
  while IFS= read -rd "" item; do tmp+=("$item"); done < <(
    printf "%s
$ a=('' 12 2 d é f $'a\nb')
$ printf '<%s>\n' "${(@o)a}"
<>
<12>
<2>
<a
b>
<d>
<é>
<f>
$ printf '<%s>\n' "${(@no)a}"
<>
<2>
<12>
<a
b>
<d>
<é>
<f>
" "${'"$array"'[@]}" | sort -z)
  '"$array"'=("${tmp[@]}")'
done
' "${a[@]}" | sort -z)
' \"\${$array[@]}\" | sort -z")
done
' "${a[@]}" | sort -z)

Portanto, uma função sortarray seria como:

b=("${(@o)a}")

AT & T ksh (ksh88 ou ksh93, ambos podem ser encontrados em alguns sistemas)

sortarray() for array do eval "$array=(\"\${(@o)$array}\")"; done

set -s ordena a lista de argumentos e os armazena nos parâmetros posicionais. A ordem é lexical.

Uma função sortarray poderia ser:

set -s -- "${a[@]}"
b=("$@")

    

Answer 3

sortnums(){
    local OLDPWD IFS=' /'
    cd -- "$(mktemp -d)" || return
    touch -- $*;  ls -A
    cd - >/dev/null &&
    rm -rf -- "$OLDPWD"
}

Aqui está uma versão um pouco mais complicada e um pouco mais lenta que não compacta duplicatas e classifica os números decimais (tamanho razoável) em ordem numérica - embora (espaço-divisão) outras strings ainda são classificadas, o tamanho da string é considerado primeiro. E para lidar com cadeias genéricas, você quase deseja definir o g=[0-9] glob de maneira diferente.

Eu serei honesto - eu (talvez) considere classificar uma lista de palavras ou números assim, mas não seria Caso contrário, ocorra-me para criar um arquivo com um nome que não seria, pelo menos, caber confortavelmente dentro de um parágrafo. E assim se divide em espaços. Na maioria das vezes, essa é a coisa certa a fazer. É, no entanto, também dificultada por um requisito de sanidade para tratar / como um nulo. Mas foi apenas por diversão, de qualquer maneira, realmente.

fs_sort(){
        local OLDPWD IFS=' /' opt="$-" g
        cd -- "$(mktemp -d)" || return
        set     -C                         ### noClobber for testable >
        for     g in    $*                 ### disallow any / reference
        do      until   command >" $g"     ### who needs dot glob?
                do      g=" $g"            ### '   1' lex== ' 1'
        done;   done    2>&1               ### -C is bitchy
                g=[0-9]                    ### now glob the array
        while   set -f *\ $g   &&          ### set it  &&
                <"$1" g+=? arr+=( $* )     ### <chk && (clean) it
        do      set +f;    done 2>&1       ### clear it
        set +fC "-${opts:--}"              ### put stuff where we found it
        cd - && rm  -rf -- "$OLDPWD"       ### don't leave our trash out
}       >/dev/null                         ### cd - is chatty

Se há alguma lição nisso, talvez deva ser o que uma coisa suja bash arrasys são em primeiro lugar. Se os dados fossem simplesmente mantidos em arquivos , nunca teríamos nenhum problema sort ing em primeiro lugar. Imagine como seria mais fácil manter um importante estado de shell quando necessário se suas shells de login simplesmente pegassem um pequeno pedaço de tmpfs na inicialização, copiassem um diretório ~/.sh para ele, e então copiassem qualquer arquivos que você pode ter marcado como pega no momento do desligamento. Todos do seu estado nomes classificariam como set * , e seu conteúdo estaria acessível a qualquer utilitário que você quisesse chamar como qualquer outro arquivo.

    

Answer 4

Duas soluções estranhas em memória simples. A referência para muitas respostas dadas nesta pergunta está disponível em gists , com os resultados disponíveis na área de comentários . Eu posso atualizar essas coisas com copypastes de novas respostas de forma irregular.

Todos os cálculos de complexidade ignoram o tamanho das strings no bash. Para index_sort , pode haver muito atol e seu reverso, linear para strlen e log para o valor int; para alias_sort , strcmp é linear.

index_sort para int64 não assinado

Bash sempre imprime uma matriz indexada em ordem numérica.

Versão mínima de bash : 2.0
Tipo de algoritmo : classificação de inserção em uma lista vinculada, não-inplace
Complexidade de tempo : O ( n ^ 2), melhor O ( k * n ) (adaptável via lastref desde 4.3)
Complexidade do espaço : O ( n )
Referência da fonte : array.c:[email protected]

# index_sort <source_arr> [target_arr:-source_arr]
index_sort() {
  # Not that surprising: using indirect expansions in a 'for' loop is slow.
  local _tmp=() _src="$1[@]" _sorted_nodup _sorted; _src=("${!_src}")
  for i in "${_src[@]}"; do (( _tmp[i]++ )); done
  # This eats duplicates.
  _sorted_nodup=( "${!_tmp[@]}" )
  # The numeric values in _sorted_nodup<int, int> gives us the occurrence of 
  # the element in the original sequence.. takes extra 1~4x time to expand.
  # The extra time decreases as elems decreases, -> ~1.2x.
  # CONSIDER SKIPPING THIS and use '_sorted_nodup' for the final eval instead.
  for i in "${_sorted_nodup[@]}"; do
    j=${_tmp[i]}
    while ((j--)); do _sorted+=("$i"); done
  done
  # Assign it back..
  eval "${2:-$1}=(" '"${_sorted[@]}" )'
}
index_sort arr out
declare -p out

Como a maioria das pessoas acredita que os procedimentos executados como código nativo cuidadosamente otimizado devem ser muito mais rápidos do que os scripts interpretados, o coeficiente n ^ 2 deve ser bem baixo comparado ao resto da expressão .

alias_sort para strings (byte-lexicographical)

Bash sempre imprime pseudônimos em ordem lexicográfica. Essa idéia veio do mikeserv, eu só coloquei em uma função. Este contém um subshell como substituição de comando (necessário para o alias env scoping).

Versão mínima de bash : 1.14.7 (qualquer versão com uma classificação alias )
Tipo de algoritmo : qsort com strcmp
Complexidade do Tempo : O ( n log n )
Complexidade do Espaço : O ( n log n )
Referência da fonte : alias.c:[email protected] , alias.c:[email protected]

# alias_sort <source_arr> [target_arr:-source_arr]
# modified to fit in a function.
alias_sort(){
  local _s=() _e="$1[@]" IFS=$'\n' # does bash 1 support indirect expansion?
  _s=($(
    unalias -a &&                  # clear all aliases
    alias "${!_e/%/=}" &&          # (exp: map append '=') pass to alias
    alias                          # sort (see src) and print the aliases
  )) || return
  _s=("${_s[@]#alias }")           # strip off the 'alias '
  # strip the shortest trailing =* and assign back.
  eval "${2:-$1}=("'"${_s[@]%=*}")'
}

Notas:

1. Esta implementação come duplicatas. Procurando por uma solução não muito desajeitada. Além disso, isso diminui muito com duplicatas no bash, talvez o hash do alias interno seja infeliz.
2. Desde o bash 3.0, alias verifica os nomes dos aliases, e isso quebra tudo com coisas que não são aliasáveis. Usando uma matriz intermediária temporária, por exemplo, _g para fazer _g=("${_e/some/replace}") _g="${_g[@]/more/...}" para escape ainda deve ser rápido o suficiente, mas estou com preguiça de listar todos esses caracteres ruins agora. %código%