A matriz de ordenação de acordo com o comprimento dos elementos?

Question

Dado um array de strings, eu gostaria de ordenar o array de acordo com o tamanho de cada elemento.

Por exemplo ...

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

Deverá classificar para ...

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

(Como um bônus, seria bom se a lista ordenasse sequências do mesmo tamanho, em ordem alfabética. No exemplo acima, medium string foi classificado antes de middle string , mesmo que tenham o mesmo comprimento. Mas isso não é um " exigência "difícil, se complicar mais a solução).

Não há problema se a matriz for classificada no local (ou seja, "matriz" for modificada) ou se uma nova matriz classificada for criada.

    

Answer 1

Se as strings não contiverem novas linhas, o seguinte deverá funcionar. Ele classifica os índices do array pelo comprimento, usando as próprias strings como critério secundário de classificação.

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

Observe que a mudança para uma linguagem de programação real pode simplificar bastante a solução, por exemplo, em Perl, você pode apenas

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

    

Answer 2

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

Isso lê os valores da matriz classificada de uma substituição de processo.

A substituição do processo contém um loop. O loop produz cada elemento do array prefixado pelo comprimento do elemento e um caractere de tabulação entre eles.

A saída do loop é classificada numericamente de maior para menor (e alfabeticamente se os comprimentos forem os mesmos; use -k 2r no lugar de -k 2 para inverter a ordem alfabética) e o resultado de que é enviado para cut , que exclui a coluna com os comprimentos de string.

Classifique o script de teste seguido de uma execução de teste:

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

Isso pressupõe que as seqüências de caracteres não contêm novas linhas. Em sistemas GNU com um bash recente, você pode suportar novas linhas incorporadas nos dados usando o caractere nul como separador de registro em vez de nova linha:

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

Aqui, os dados são impressos com sort no loop em vez de novas linhas, cut e -z lê linhas delimitadas por nul através de suas opções readarray GNU e -d '' finalmente lê as nul- dados delimitados com %code% .

    

Answer 3

Eu não vou repetir completamente o que eu já disse sobre classificação no bash , só você can classifica dentro do bash, mas talvez você não devesse. Abaixo está uma implementação apenas bash de uma ordenação de inserção, que é O (n <2>), e portanto é tolerável apenas para matrizes pequenas. Ele classifica os elementos da matriz no local pelo seu comprimento, em ordem decrescente. Não faz um tipo alfabético secundário.

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 evidência de que esta é uma solução especializada, considere os tempos das três respostas existentes em vários tamanhos de matrizes:

# 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 e Kusalananda tem a idéia certa: calcular os comprimentos uma vez e usar utilitários dedicados para classificação e processamento de texto.

    

Answer 4

Um hackish? (complexa) e rápida maneira de uma linha para classificar a matriz por tamanho
( seguro para novas linhas e matrizes esparsas):

#!/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 $'
readarray -td $'
$ ./script
the longest
        string also containing
        newlines
also a medium string
medium string
middle string
test * string
short string
tiny string
[abc]
?
*
' sorted < <(for i in "${in[@]}";do printf '%s %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 $'
readarray -td $'
$ ./script
the longest
        string also containing
        newlines
also a medium string
medium string
middle string
test * string
short string
tiny string
[abc]
?
*
' sorted < <(for i in "${in[@]}";do printf '%s %s%pre%' "${#i}" "$i"; done | sort -bz -k1,1rn -k2 | cut -zd " " -f2-)
' sorted < <(
                    for i in "${in[@]}"
                    do     printf '%s %s%pre%' "${#i}" "$i";
                    done |
                            sort -bz -k1,1rn -k2 |
                            cut -zd " " -f2-
                    )

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

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

Em uma linha:

%pre%

Em execução

%pre%     

Answer 5

Isso também lida com elementos de matriz com novas linhas neles; funciona passando por sort apenas o comprimento e o índice de cada elemento. Deve funcionar com bash e 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

for a in "${out[@]}"; do printf '"%s"\n' "$a"; done

Se os elementos do mesmo tamanho também tiverem que ser classificados lexicograficamente, o loop pode ser alterado assim:

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

Isso também passará para sort das strings (com novas linhas alteradas para espaços), mas elas ainda serão copiadas da matriz para a matriz de destino por seus índices. Nos dois exemplos, o $(...) verá apenas as linhas que contêm números (e o caractere / no primeiro exemplo), portanto, ele não será desarmado pela presença de caracteres ou espaços nas cadeias de caracteres.

    

Answer 6

No caso de mudar para zsh é uma opção, uma maneira hackish lá (para matrizes contendo qualquer seqüência de bytes):

array=('' blah $'x\ny\nz' $'x
readarray -td '' sorted_array < <(
  perl -l0 -e 'print for sort {length $b <=> length $a} @ARGV
              ' -- "${array[@]}")
y' '1 2 3')
sorted_array=( /(e'{reply=("$array[@]")}'nOe'{REPLY=$#REPLY}') )

zsh permite definir ordens de classificação para sua expansão glob por meio de qualificadores glob. Então, aqui, estamos enganando-o para fazer isso por arrays arbitrários, globbing em / , mas substituindo / pelos elementos da matriz ( e'{reply=("$array[@]")}' ) e, em seguida, n umerically o rder com maiúscula O ) os elementos com base em seu comprimento ( Oe'{REPLY=$#REPLY}' ).

Note que é baseado no comprimento em número de caracteres. Para o número de bytes, defina a localidade como C ( LC_ALL=C ).

Outra abordagem bash 4.4+ (assumindo que não é um array muito grande):

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

(esse comprimento é em bytes ).

Com versões mais antigas de bash , você sempre pode fazer:

array=('' blah $'x\ny\nz' $'x
readarray -td '' sorted_array < <(
  perl -l0 -e 'print for sort {length $b <=> length $a} @ARGV
              ' -- "${array[@]}")
y' '1 2 3')
sorted_array=( /(e'{reply=("$array[@]")}'nOe'{REPLY=$#REPLY}') )

(que também funciona com ksh93 , zsh , yash , mksh ).