6

I'm trying to figure out how to make a function that can take an array as a parameter and sort it. I think it is done with positional variables, but I'm not sure.

7
  • An array of what, sorted by which condition? Did you try anything yourself? Do you want to output the result? Sort in place? Dec 6, 2015 at 3:49
  • It will sort an array of 20 numbers between a range of 1 and 100. Yes I would like the result echoed. The sorted result does not have to be stored just outputted I guess "in place". Dec 6, 2015 at 3:51
  • If you output the result, you don't sort in place. In place means, that the original array is modified which will influence other usages of the array. Dec 6, 2015 at 3:53
  • It really doesn't need to do anything else besides be sorted, and echoed. Dec 6, 2015 at 3:57
  • Here's a function, written in bash, that sorts arrays: stackoverflow.com/a/30576368/3979290
    – Aloha
    Dec 6, 2015 at 4:18

6 Answers 6

11

bash

I don't think bash has any builtin support for that yet. Options would be to implement a sort algorithm by hand or to invoke sort to do the sorting.

If we consider that array elements can contain any byte value but 0 in bash, to do it reliably, we'd need to pass the list of elements NUL-delimited and use the -z option to sort (non-standard but available in GNU sort or FreeBSD sort).

bash-4.4 (released September 2016) makes it easier as it introduced a -d option to its readarray builtin to specify the delimiter.

To sort array a into array b:

readarray -td '' b < <(printf '%s\0' "${a[@]}" | sort -z)

would sort the array reliably. Use the -n, -r options to sort to sort numerically or in reverse (or any sort criteria supported by sort).

To implement your sortarray function (sorts all the arrays passed by-name as arguments):

sortarray() for array do
  eval '((${#'"$array"'[@]} <= 1))' || readarray -td '' "$array" < <(
    eval "printf '%s\0' \"\${$array[@]}\" | sort -z")
done

With earlier versions of bash, you can use read -d in a loop to achieve the same:

b=()
while IFS= read -rd '' item; do b+=("$item"); done < <(
  printf '%s\0' "${a[@]}" | sort -z)

For the sortarray function:

sortarray() for array do eval '
  tmp=()
  while IFS= read -rd "" item; do tmp+=("$item"); done < <(
    printf "%s\0" "${'"$array"'[@]}" | sort -z)
  '"$array"'=("${tmp[@]}")'
done

zsh

Zsh has builtin support to sort arrays.

you can use the o parameter expansion flag to sort lexically (O for reverse order). You can add the n flag to sort numerically:

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

In locales that don't already sort case-independently, you can also add the i flag for that.

To assign to an array:

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

So a sortarray function would be like:

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

AT&T ksh (ksh88 or ksh93, both of which can be found as sh on some systems)

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

set -s sorts the list of arguments and stores it in the positional parameters. The order is lexical.

A sortarray function could be:

sortarray() for array do
  eval 'set -s -- "${'"$array"'[@]}"; '"$array"'=("$@")'
done
1
  • 1
    For zsh the option n does a numeric sort of numbers in a string. It will do a lexicographical sort of the strings prefixing the number, followed by a numeric sort. This is handy for stuff like foo1 foo02 foo3. However, for a pure numeric string, this will fail when negative numbers are in use. a=( 10 8 -20 100 ); echo "${(@n)a}" this returns 8 10 100 -20. Be aware that the sorting of floats is just mimicked. It just does a numeric sort on the fractional part. You can see this with this example a=(1 1.11 1.2); echo ${(n)a} this returns 1 1.2 1.11 because 2 < 11
    – kvantour
    Feb 5, 2021 at 11:29
6

Sort the easy way with sort, tr:

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

Into a new array:

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

Without help by tr/sort, for example 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[@]}

For 20 numbers, bubblesort might be sufficient.

5
  • I think your answers helped me the best thank you. Dec 6, 2015 at 19:35
  • And your solution unfortunately depends on seq. For bash just use arith for loops…… Dec 8, 2015 at 16:34
  • @userunknown right. Dec 8, 2015 at 17:03
  • 2
    @StéphaneChazelas: Please provide your own answer, if you have a better solution. I'm working fine most of the time with 'echo', not 'printf' and tr, not paste. I don't like to answer questions for code which I woulnd't have written. Dec 8, 2015 at 18:04
  • A tr-less solution: IFS=$'\n'; echo "${arr[*]}". Dec 9, 2015 at 4:34
5
sortnums(){
    local OLDPWD IFS=' /'
    cd -- "$(mktemp -d)" || return
    touch -- $*;  ls -A
    cd - >/dev/null &&
    rm -rf -- "$OLDPWD"
}

Here's a slightly more complicated, and somewhat slower version which nevertheless does not squeeze duplicates and which sorts (reasonably sized) decimal numbers in numeric order - though (space-split) other strings are still sorted, string length is considered first. And to handle generic strings you'd almost definitely want to set the g=[0-9] glob differently.

I'll be honest - I would (maybe) consider sorting a list of words or numbers like this, but it wouldn't otherwise occur to me to create a file with a name that wouldn't at least fit comfortably within a paragraph. And so it splits on spaces. Most often, that's the right thing to do. It is, however, also hampered by a sanity requirement of treating / like a null. But it was just for fun, anyway, really.

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

If there's any lesson in this, maybe it should be what a filthy thing bash arrays are in the first place. If data was simply kept in files we'd never have any issue sorting it in the first place. Imagine how much easier it would be to maintain important shell state when necessary if your login shells just grabbed themselves a tiny chunk of tmpfs at startup, copied a ~/.sh directory into it, and then copied back any files you may have marked sticky since at shutdown. All of your state names would sort as simply as set *, and their contents would be accessible to any utility you wanted to call on them as is any other file.

1
  • 1
    @don_crissti - yes, it will sort in lexicographic order. oh - i thought the default was -d. i'll fix that - good thing i stuck in the || return in the first place. the asker doesnt specify a numeric sort, just that he has numbers which should be sorted (and im aware of how stupid that sounds). the only issues any of that should cause is 1 10 2 3 4 and so on. that is very easily handled with ls -A|sort -n, of course (and would likely be a quicker way to do it than just printf %s\n "$@"|sort -n for any sizeable set *(maybe?). anyway, making them filenames means you can do a=(*)
    – mikeserv
    Dec 6, 2015 at 18:07
5

Two weird, in-memory plain-bash solutions. Benchmark for many answers given in this question is available on gists, with results available in the comment area. I may update those things with copypastes from new answers irregularly.

All the complexity calculations ignore the length of strings in bash. For index_sort there may be a lot of atol and its reverse, linear to strlen and log to int value; for alias_sort, strcmp is linear.

index_sort for unsigned int64

Bash always prints an indexed array in numerical order.

Minimum Bash Version: 2.0
Algorithm Type: Insertion Sort on a Linked List, non-inplace
Time Complexity: O(n^2), best O(k*n) (adaptive via lastref since 4.3)
Space Complexity: O(n)
Source Reference: array.c:array_insert@4.3

# 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

Since most people believe that procedures running as carefully-optimized native code should be much faster than those as interpreted scripts, the coefficient for n^2 should be quite low compared to the rest of the expression.

alias_sort for strings (byte-lexicographical)

Bash always prints aliases in lexicographical order. This idea came from mikeserv, I only wrapped it into a function. This one contains a subshell as command substitution (necessary for alias env scoping).

Minimum Bash Version: 1.14.7 (any version with a sorting alias)
Algorithm Type: qsort with strcmp
Time Complexity: O(n log n)
Space Complexity: O(n log n)
Source Reference: alias.c:all_aliases@1.14.7, alias.c:legal_alias_name@3.0

# 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[@]%=*}")'
}

Notes:

  1. This implementation eats duplicates. Looking for a not-too-clumsy solution. Additionally, this slows down a lot with duplicates on bash, perhaps the internal alias hashtable is unhappy.
  2. Since bash 3.0, alias checks the alias names, and this breaks everything with non-aliasable things. Using a temporary intermediate array, say, _g for doing _g=("${_e/some/replace}") _g="${_g[@]/more/...}" for escaping should still be fast enough, but I am too lazy to list out all those bad characters now. /* [\\'"`$<>[:space:]] */
11
  • kind of all of the stuff is. i thought about that too - export -p and set and alias. but it involved a lot of parsing i didnt want to do, and so i just made a blank directory. i dont use bash arrays though and so it didnt occur to me - its a pretty good answer - a lot less parsing than i would have wound up doing with that other stuff.
    – mikeserv
    Dec 8, 2015 at 16:37
  • @StéphaneChazelas It appears it's my fault.. My memory got wrong. Let me try some indexed array though -- perhaps with number-indexed ones I can still get sorted output. Dec 8, 2015 at 17:21
  • 1
    yeah! sortnums is slow. yours is pretty good. i figured out how to do it with alias like eval "unalias -a; alias $(printf "%d= " "$@" 2>/dev/null); alias" | cut -d= -f1 - i think that should work (but in bash you might need set -o posix first) - it will eat dups, though, of course.
    – mikeserv
    Dec 9, 2015 at 5:09
  • 1
    oh! i didnt notice the Cygwin thing - i dont think it works as a good control system for benching anything but native shell apps. cygwin does this weird file-system abstraction layer, and doesn't have a true analog for a unix fork. i'll try it too.
    – mikeserv
    Dec 9, 2015 at 6:05
  • 1
    your gist has gone 404...
    – derobert
    Oct 20, 2017 at 17:35
1
#! /bin/bash

array=('2' '7' '5' '9' '0')
sort=0
echo ${array[@]}
len=${#array[@]}
echo $len


for ((i=0; i<$len; i++))
do
    for((j=i+1; j<$len; j++))
    do
        if [ ${array[i]} -le ${array[j]} ]
        then
            continue
        else
            sort=${array[i]}
            array[i]=${array[j]}
            array[j]=$sort
        fi
    done
done
echo ${array[@]}
0

This question looks closely related.

Here's a plain old mergesort, without external processes, variable namespace tricks or aliasing tricks:

mergesort() {
  local -n -r input_reference="$1"
  local -n output_reference="$2"
  local -r -i size="${#input_reference[@]}"
  local merge previous
  local -a -i runs indices
  local -i index previous_idx merged_idx \
           run_a_idx run_a_stop \
           run_b_idx run_b_stop

  output_reference=("${input_reference[@]}")
  if ((size == 0)); then return; fi

  previous="${output_reference[0]}"
  runs=(0)
  for ((index = 0;;)) do
    for ((++index;; ++index)); do
      if ((index >= size)); then break 2; fi
      if [[ "${output_reference[index]}" < "$previous" ]]; then break; fi
      previous="${output_reference[index]}"
    done
    previous="${output_reference[index]}"
    runs+=(index)
  done
  runs+=(size)

  while (("${#runs[@]}" > 2)); do
    indices=("${!runs[@]}")
    merge=("${output_reference[@]}")
    for ((index = 0; index < "${#indices[@]}" - 2; index += 2)); do
      merged_idx=runs[indices[index]]
      run_a_idx=merged_idx
      previous_idx=indices[$((index + 1))]
      run_a_stop=runs[previous_idx]
      run_b_idx=runs[previous_idx]
      run_b_stop=runs[indices[$((index + 2))]]
      unset runs[previous_idx]
      while ((run_a_idx < run_a_stop && run_b_idx < run_b_stop)); do
        if [[ "${merge[run_a_idx]}" < "${merge[run_b_idx]}" ]]; then
          output_reference[merged_idx++]="${merge[run_a_idx++]}"
        else
          output_reference[merged_idx++]="${merge[run_b_idx++]}"
        fi
      done
      while ((run_a_idx < run_a_stop)); do
        output_reference[merged_idx++]="${merge[run_a_idx++]}"
      done
      while ((run_b_idx < run_b_stop)); do
        output_reference[merged_idx++]="${merge[run_b_idx++]}"
      done
    done
  done
}

declare -ar input=({z..a}{z..a})
declare -a output

mergesort input output

echo "${input[@]}"
echo "${output[@]}"

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.