11

Given an array of strings, I would like to sort the array according to the length of each element.

For example...

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

Should sort to...

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

(As a bonus, it would be nice if the list sorted strings of the same length, alphabetically. In the above example medium string was sorted before middle string even though they are the same length. But that's not a "hard" requirement, if it over complicates the solution).

It is OK if the array is sorted in-place (i.e. "array" is modified) or if a new sorted array is created.

Enterprise
  • 249
  • 1
    some interesting answers over here, you should be able to adapt one to test for string length as well https://stackoverflow.com/a/30576368/2876682 – frostschutz Nov 17 '18 at 20:20

6 Answers6

13

If the strings don't contain newlines, the following should work. It sorts the indices of the array by the length, using the strings themselves as the secondary sort criterion.

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

Note that moving to a real programming language can greatly simplify the solution, e.g. in Perl, you can just

sort { length $b <=> length $a or $a cmp $b } @array
choroba
  • 47,233
11
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- )

This reads the values of the sorted array from a process substitution.

The process substitution contains a loop. The loop output each element of the array prepended by the element's length and a tab character in-between.

The output of the loop is sorted numerically from largest to smallest (and alphabetically if the lengths are the same; use -k 2r in place of -k 2 to reverse the alphabetical order) and the result of that is sent to cut which deletes the column with the string lengths.

Sort test script followed by a test run:

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

This assumes that the strings do not contain newlines. On GNU systems with a recent bash, you can support embedded newlines in the data by using the nul-character as the record separator instead of newline:

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

Here, the data is printed with trailing \0 in the loop instead of newlines, the sort and cut reads nul-delimited lines through their -z GNU options and readarray finally reads the nul-delimited data with -d ''.

Kusalananda
  • 333,661
  • 3
    Note that -d '\0' is in fact -d '' as bash can't pass NUL characters to commands, even its builtins. But it does understand -d '' as meaning delimit on NUL. Note that you need bash 4.4+ for that. – Stéphane Chazelas Nov 18 '18 at 08:29
  • @StéphaneChazelas No, it is not '\0', it is $'\0'. And yes, it converts (almost exactly) to ''. But that is a way to comunicate to other readers the actual intent of using a NUL delimiter. –  Nov 18 '18 at 15:11
4

I won't completely repeat what I've already said about sorting in bash, just you can sort within bash, but maybe you shouldn't. Below is a bash-only implementation of an insertion sort, which is O(n2), and so is only tolerable for small arrays. It sorts the array elements in-place by their length, in decreasing order. It does not do a secondary alphabetical sort.

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

As evidence that this is a specialized solution, consider the timings of the existing three answers on various size arrays:

# 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 and Kusalananda have the right idea: compute the lengths once and use dedicated utilities for sorting and text processing.

Jeff Schaller
  • 67,283
  • 35
  • 116
  • 255
4

This also handles array elements with newlines in them; it works by passing through sort only the length and the index of each element. It should work with bash and 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[@]}"

If the elements of the same length also have to be sorted lexicographically, the loop could be changed like this:

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

This will also pass to sort the strings (with newlines changed to spaces), but they would still be copied from the source to the destination array by their indexes. In both examples, the $(...) will see only lines containing numbers (and the / character in the first example), so it won't be tripped by globbing characters or spaces in the strings.

  • Cannot reproduce. In the second example, the $(...) command substitution sees only the indexes (a list of numbers separated by newlines), because of the cut -d' ' -f1 after the sort. This could be easily demonstrated by a tee /dev/tty at the end of the $(...). –  Nov 19 '18 at 12:19
  • Sorry, my bad, I missed the cut. – Stéphane Chazelas Nov 19 '18 at 13:19
  • @Isaac There's no need to quote the ${!in[@]} or ${#in[i]}/$i variable expansions because they only contain digits which are not subject to glob expansion and the unset IFS will reset the IFS to space, tab, newline. In fact, quoting them would be harmful, because it will give the false impression that such quoting is useful and effective, and that the setting of IFS and/or filtering the output of sort in the second example could be safely done away with. –  Nov 21 '18 at 15:41
  • @Isaac It does NOT break if in contains "testing * here" and shopt -s nullglob is set before the loop. –  Nov 21 '18 at 15:45
4

A hackish? (complex) and fast one line way to sort the array by length
(safe for newlines and sparse arrays):

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

On one line:

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

On execution

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

In case switching to zsh is an option, a hackish way there (for arrays containing any sequence of bytes):

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

zsh allows defining sort orders for its glob expansion via glob qualifiers. So here, we're tricking it to do it for arbitrary arrays by globbing on /, but replacing / with the elements of the array (e'{reply=("$array[@]")}') and then numerically order (in reverse with uppercase O) the elements based on their length (Oe'{REPLY=$#REPLY}').

Note that it's based on the length in number of characters. For number of bytes, set the locale to C (LC_ALL=C).

Another bash 4.4+ approach (assuming not too big an array):

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

(that's length in bytes).

With older versions of bash, you could always do:

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

(which would also work with ksh93, zsh, yash, mksh).

Stéphane Chazelas
  • 544,893