Algorithms

Algorithms#

Zsh is rarely the right tool for heavy algorithmic work, but its parameter-expansion flags collapse a surprising number of algorithm chores into a single expansion. Sort, dedupe, split, join, numeric-sort, reverse all live in ${(flag)var}. The basics are still 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"

Zsh’s (M) parameter-expansion flag returns only the elements matching a pattern, turning the same search into a one-liner.

$ items=(red green blue greenfield)
$ matches=( ${(M)items:#green*} )
$ print -- $matches              # green greenfield

Membership test via an associative array (O(1) on average).

$ typeset -A in_set
$ for x in $items; do in_set[$x]=1; done
$ (( ${+in_set[green]} )) && print -- "found"

Sorting#

For anything non-trivial, delegate to sort.

$ print -l -- $items | sort

For in-memory arrays, the parameter-expansion flags do it in one step. No external process, no temp file.

Flag	Effect
`(o)`	Sort ascending
`(O)`	Sort descending
`(n)`	Numeric sort (combine with `o` / `O`)
`(i)`	Case-insensitive (combine with `o` / `O`)
`(u)`	Drop duplicates
`(a)`	Array-flatten in the right order

$ nums=(10 2 33 4 5)
$ print -l -- ${(on)nums}            # 2 4 5 10 33 (numeric)
$ print -l -- ${(On)nums}            # 33 10 5 4 2
$ print -l -- ${(ou)nums}            # sorted, unique
$ print -l -- ${(oi)mixed}           # case-insensitive

An in-shell bubble sort, for completeness.

$ bubble_sort() {
  $ local -n arr="$1"
  $ local n=${#arr[@]} i j tmp
  $ for ((i=1; i<=n-1; i++)); do
    $ for ((j=1; j<=n-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
$ }

Dedup#

Three ways, in order of preference.

$ print -l -- ${(u)items}                # parameter flag, in-shell
$ typeset -aU items                       # attribute, deduped on assign
$ print -l -- $items | sort -u            # external, when the data is huge

Recursion#

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

$ factorial 5

Zsh has no tail-call optimization any more than bash does. Deep recursion blows the stack; prefer iteration for anything above a few hundred frames.

References#

Structures for the array / hash declarations these algorithms operate on.
Overview for the parameter-expansion table that defines ${(flag)var}.
man 1 zshexpn (full parameter-expansion-flag reference).
Coreutils for sort, uniq, comm when the data exceeds what fits in shell variables.