47 lines
1.1 KiB
Bash
Executable File
47 lines
1.1 KiB
Bash
Executable File
#!/bin/sh
|
|
|
|
set -e
|
|
|
|
usage() { echo "usage: shsort [-r] <comparator> [<list>]" >&2 && exit 0; }
|
|
|
|
[ "$1" ] || usage
|
|
|
|
[ "$1" != "-r" ] || { rev="yes" && shift; }
|
|
|
|
cmpfn="$1"
|
|
shift
|
|
|
|
quicksort() {
|
|
len="$(printf "$@\n" | wc -l)"
|
|
[ "$len" -gt 1 ] || { echo "$@" && return 0; }
|
|
|
|
pvtidx="$(expr $len / 2)"
|
|
pvt="$(printf "$@\n" | head -n$pvtidx | tail -n1)"
|
|
|
|
parted="$(printf "$@\n" | while read elem; do
|
|
{ [ "$elem" ] && [ "$elem" != "$pvt" ]; } || continue
|
|
[ "$($cmpfn "$elem < $pvt")" = "yes" ] \
|
|
&& printf "<\t$elem\n" \
|
|
|| printf ">\t$elem\n"
|
|
done)"
|
|
lesser="$(printf "$parted\n" | grep "^<" | cut -f2)"
|
|
greater="$(printf "$parted\n" | grep "^>" | cut -f2)"
|
|
|
|
if [ "$rev" ]; then
|
|
printf "%s\n%s\n%s\n" "$(quicksort "$lesser")" "$pvt" "$(quicksort "$greater")"
|
|
else
|
|
printf "%s\n%s\n%s\n" "$(quicksort "$greater")" "$pvt" "$(quicksort "$lesser")"
|
|
fi
|
|
}
|
|
|
|
if [ "$@" ]; then
|
|
elems="$@"
|
|
else
|
|
while read input; do
|
|
elems="$elems$input\n"
|
|
done
|
|
fi
|
|
[ "$elems" ] || usage
|
|
|
|
quicksort "$elems" | sed '/^$/d'
|