Algorithms

Bash is rarely the right tool for heavy algorithmic work, but the basics are useful for shell utilities.

Search

Linear search over an array:

$ contains() {
  $ local needle="$1"; shift
  $ for x in "$@"; do
    $ [[ "$x" == "$needle" ]] && return 0
  $ done
  $ return 1
$ }

$ items=(red green blue)
$ contains green "${items[@]}" && echo "found"

Sorting

For anything non-trivial, delegate to sort:

$ printf '%s\n' "${items[@]}" | sort

An in-shell bubble sort, for completeness:

$ bubble_sort() {
  $ local -n arr="$1"
  $ local n=${#arr[@]} i j tmp
  $ for ((i=0; i<n-1; i++)); do
    $ for ((j=0; j<n-1-i; j++)); do
      $ if (( arr[j] > arr[j+1] )); then
        $ tmp=${arr[j]}; arr[j]=${arr[j+1]}; arr[j+1]=$tmp
      $ fi
    $ done
  $ done
$ }

Recursion

$ factorial() {
  $ (( $1 <= 1 )) && { echo 1; return; }
  $ echo $(( $1 * $(factorial $(( $1 - 1 ))) ))
$ }