☰

POSIX shで位置引数リストをソートする方法

tag-icon • tag-icon shell-script shell sort posix array
POSIX shで位置引数リストをソートする方法

POSIX shで位置引数のリストをソートする方法はありますか？各位置引数には、すべての文字（スペース、改行、タブなど）を含めることができます。ソートアルゴリズムは、プログラマーが定義した比較に基づいてリストをソートするのに十分な一般的なものでなければなりません（例えば、数値/辞書ソートを使用するなど）。expr比較、各位置引数の部分文字列のみを考慮したソートなど）。

POSIX shの位置パラメータのリストには、スタックとキューの両方の属性があるようです。 push（set -- "$x" "$@"）、pop（x="$1"; shift）、enqueue（set -- "$@" "$x"）、およびdequeue（）操作をサポートしますx="$1"; shift。ただし、リストは1つしかない可能性があるため、整列は所定の位置で実行する必要があり、マージソートやクイックソートなどの一般的なアルゴリズムは使用できません。

サンプル:

#!/bin/sh

set -- "Hello" "world" 9 8 7 "$(printf "0\n1")" "$(printf "1\t2")"

# How do I sort the positional parameters above using comparison
# `expr "$x" \< "$y"` such that the result is the list below?
#
# "$(printf "0\n1")" "$(printf "1\t2")" 9 8 7 "Hello" "world"

注1：私は、ユーザーが提供したランダムな位置引数とプログラマーによって指定されたランダム比較で動作するPOSIXソリューションを探しています。

注2：私は実際の問題を解決しようとしていません。このソートの問題に挑戦しましたが、解決策がsh見つからなかったため、Stack Exchangeに投稿しました。

答え1

おそらく最も簡単な方法は、数値比較（浮動小数点数を含む）をawk実行できるstrcoll()方法を使用することです。strcmp()

ホイールの再発明を避けるために、awkの高速ソート実装を使用することができます。https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#AWK(GPLv2).

それから（編集する：より良い、より安全な方法は追加で確認してください）：

code=$(
  awk -v q="'" -- '
    code-from-that-link-above
    BEGIN {
      delete ARGV[0]
      n = qsortArbIndByValue(ARGV, sorted)
      printf "set --"
      for (i = 1; i <= n; i++) {
        s = ARGV[sorted[i]]
        gsub(q, q "\\" q q, s)
        printf " %s", q s q
      }
    }' "$@"
) || exit
eval "$code"

位置引数にはユーザーロケールの有効なテキストが含まれており、リストはコマンドライン引数（およびawkの配列サイズの制限）に収まるほど小さいと仮定します。

オペランドが数値として認識された場合は、awk演算子を使用して数値比較を実行し、それ以外の場合は比較を実行します。比較をから強制比較に変更し（比較のためにロケールをCに固定）、数値比較を強制に変更（POSIXですが実際に移植性はありません）して、これを行うか、いつでも実行するカスタムawk関数を作成できます。あなたが望むどんな比較。<strcoll()strcoll()a < ba"" < b""strcmp()a+0 < b+0+a < +bcompare()

POSIXと互換性がある場合は、このコードを置き換える必要がありますが、gsub(q, q "\\\\" q q, s)POSIXgsub(q, q "\\" q q, s)が指定されていない動作を生成しても、後者は環境やビジボックスをgawk除いて正常に動作しないため、移植性が優れています。$POSIXLY_CORRECTawk

データがユーザーのロケールで有効なテキストであることが保証されていない場合は、ロケールを次のように設定できます。Cこれにより、文字列は、strcmp()ユーザーロケールソート順序ではなくバイト配列として処理されソートされます（ASCIIベースのシステムでは）。

不特定行為の結果かもしれないことを与えるのは多少不便ですが、もう一度考えてみるとそのようなものを出力せずに代わりに出力するならeval信頼できるようにすることが可能でしょう。awkset -- '3rd argument hoped to be quoted correctly' 'first' 'second'set -- "${3}" "${1}" "${2}"

さらに、この作業はより簡単、短く、より効率的でなければなりません。

code=$(
  awk -- '
    code-from-that-link-above
    BEGIN {
      delete ARGV[0]
      n = qsortArbIndByValue(ARGV, sorted)
      printf "set --"
      for (i = 1; i <= n; i++)
        printf " \"${%s}\"", sorted[i]
    }' "$@"
) || exit
eval "$code"

答え2

まず、シェルを使用してevalこれらの文字列を並べ替え、結果を並べ替え、並べ替えられた文字列と元のインデックス配列に同じ操作を適用する必要があります。以下に例を挙げましょう。

もちろん、シェルスクリプトで独自のソートアルゴリズムを実装することもできます。言語はそのようなデータ構造/アルゴリズムにはあまり適していないので、おそらくそれより複雑な（そして理論的には効率が悪い）ことを目指すことはあまり意味がありません。バブルソート。かなり短く、醜くて楽しいでしょう。

  1. あなたの質問に提供された元の配列です。
  2. 配列の長さを求め、それを使用してseq配列1、2、... 、Nを生成します。
  3. 同じ長さの新しい配列を作成し、シェルに元の項目の各項目を評価させます（したがって$(printf "0 \n"）0 \n。これが私たちが実際にソートする必要があることです。
  4. バブルソートを実装します。
    1. 最初の要素を2番目の要素と比較します。最初の値が大きい場合は、ソート基準に基づいて（わかりません。これについて少しあいまいです）、2つの値を交換して（一時変数を使用して）同じ位置を維持します。
    2. 2番目と3番目を比較し続けます。上記のルールを繰り返し、各ペアごとに順番に繰り返します。
    3. 2番目の要素を最後の要素と比較（交換）してから最初から再開します（前の実行より前の要素の比較を中止できます）。
    4. ある時点では、すべてが整理されました。止まる！
  5. 並べ替えられたインデックス配列を使用すると、元の（解釈されていない）値を含む並べ替えられた配列を設定できるようになりました。

答え3

アイデアは次のとおりです。

  • では、sh改行文字を区切り文字として使用できるように、各位置パラメーターのすべての改行およびバックスラッシュ文字をエスケープします。
  • 改行で区切られた位置引数をawk。
  • ではawk、クイックソートを使用して引数をソートし、改行区切りのソート引数を標準出力に書き込みます。
  • では、shソートされていない位置引数のリストを改行に分割し、改行で区切られたソート引数に置き換えます。awk
  • ソートされた位置引数リストからすべての改行とバックスラッシュ文字をエスケープ解除します。

実装する：

#!/bin/sh
# Run this shell script to sort this list of positional parameters:
set -- \
    'Hello' \
    '  0  1  ' \
    '' \
    '*' \
    '\0150\0151' \
    "$(printf '\a\b\e\f\n\r\t\v')" \
    '\a\b\e\f\n\r\t\v%%\\' \
    'qwerty
uiop' \
    '

new

lines

'

printf '====== NOT YET SORTED ======\n'
for param; do
    printf '%s' "$param" | od -ab
done

quicksort() {
    for param; do
        # * Escape newlines (newline -> "\n" [two characters]).
        #   Rationale:
        #   * To be able to use newline as AWK record separator.
        #   * To be able to use it as the shell's $IFS for separating records.
        # * Escape backslashes (backslash -> "\\" [two characters]).
        #   Rationale:
        #   * To distinguish between escaped newlines and the two-character
        #     string "\n" (escaped version: "\\n" [three-character string]).
        #   * To avoid special interpretation of backslashes when passed to
        #     `printf '%b' ...`.
        #
        # `sed` solution adapted from:
        # https://unix.stackexchange.com/questions/761885/how-to-convert-all-newlines-to-n-in-posix-sh-strings
        printf '%s\n' "$param" | LC_ALL=C sed '
            :1
            $ ! {
                N
                b1
            }
            s/\\/\\\\/g
            s/\n/\\n/g'
    done | awk -f ./quicksort.awk
}

# Create temporary file.
tmpfile="$(printf 'mkstemp(template)' \
    | m4 -D template="${TMPDIR:-/tmp}/XXXXXX")" || exit 1
exec 3>"$tmpfile" 4<"$tmpfile"  # Open tmpfile for writing and reading.
rm -f -- "$tmpfile"

quicksort "$@" >&3 3>&-

set --
while IFS= read -r line; do
    # Unescape backslashes and newlines.
    # To preserve trailing newlines (if any), insert a trailing character 'x'
    # and later remove it.
    elem="$(printf '%bx' "$line")"
    set -- "$@" "${elem%x}"
done <&4 4<&-

printf '\n====== SORTED RESULTS ======\n'
for param; do
    printf '%s' "$param" | od -ab
done

これはquicksort.awk：

# Takes newline-separated records from standard input and sorts them according
# to the `compare` function. Outputs the sorted newline-separated records to
# standard output.
#
# Backslash and newline characters supplied within each input record must be
# escaped like this:
# * backslash character -> "\\" (two backslash characters)
# * newline character -> "\n" (backslash character followed by the "n" character)
#
# Backslash and newline characters within each output record will be escaped in
# the same manner.
#
# Usage: awk -f quicksort.awk
#
# Attribution:
# Functions `quicksort` and `quicksort_swap` are adapted from the public domain
# quicksort implementation by Arnold Robbins retrieved from
# https://git.savannah.gnu.org/cgit/gawk.git/tree/awklib/eg/lib/quicksort.awk?h=gawk-5.3.0

function compare(a, b) {
    # Unescape backslashes and newlines.
    gsub(/\\/, "\\", a)
    gsub(/\\/, "\\", b)
    gsub(/\\n/, "\n", a)
    gsub(/\\n/, "\n", b)

    # For sorting in ascending lexicographic order.
    return a < b
}

function quicksort(data, left, right,    i, last) {
    if (left >= right)  # Do nothing if array contains fewer than two elements.
        return

    quicksort_swap(data, left, int((left + right) / 2))
    last = left
    for (i = left + 1; i <= right; i++)
        if (compare(data[i], data[left]))
            quicksort_swap(data, ++last, i)
    quicksort_swap(data, left, last)
    quicksort(data, left, last - 1, less_than)
    quicksort(data, last + 1, right, less_than)
}

function quicksort_swap(data, i, j,    temp) {
    temp = data[i]
    data[i] = data[j]
    data[j] = temp
}

{
    lines[counter++] = $0
}

END {
    quicksort(lines, 0, counter - 1)
    for (k = 0; k < counter; k++)
        print lines[k]
}

テスト対象：

  • Debian 12、ダッシュ 0.5.12、GNU sed 4.9、Gawk 5.2.1
  • Debian 12、ダッシュ 0.5.12、Busybox 1.35.0 sed、およびawk
  • FreeBSD 13.2shとsedawk

答え4

これは POSIX sh の挿入ソートです。

sort ()
{
    f=false
    for x
    do
        if ! $f
        then
            set -- "$1"
            f=true
        else
            q=false
            # marginally faster than while + "$1" in my tests
            for y
            do
                if $q || "$cmp" "$x" "$y"
                then
                    set -- "$@" "$y"
                else
                    set -- "$@" "$x" "$y"
                    q=true
                fi
                shift
            done
            $q || set -- "$@" "$x"
        fi
    done
    "$cont" "$@"
}

islonger ()
{
    [ ${#1} -gt ${#2} ]
}

puts ()
{
    printf %s\\n "$@"
}

cmp=islonger
cont=puts
sort "$@"

効率の頂点ではありませんが、bashは非常に小さな入力に役立つほど、私のコンピュータで十分速く実行されます。

$ shuf /usr/share/dict/words | head -n 50 | xargs -d '\n' sh -c 'time sh sort.sh "$@"' sh
sic
alto
Biko
needs
Capet
scuba
bowed
sicks
waxier
Kodaly
Tuvalu
hubbub
Gide's
panache
Joann's
peeling
mermaid
wingnut
savvies
crybaby
Python's
nitwit's
junction
tailored
tussocks
rotaries
Brandi's
leafiest
banknote
Spence's
Heriberto
prepaying
telephony
indelible
addendum's
stampeding
hatchway's
pathogenic
Englishman
escarole's
outstaying
synonymous
Youngstown
rebroadcast
overstuffed
interweaves
deliquescent
grandmothers
Cryptozoic's
mammography's

real    0m0.039s
user    0m0.038s
sys     0m0.001s

私は多くのソートアルゴリズムがPOSIXシェルで非常に簡単に実装できると信じています。最大の問題は、スワップ操作がないことです。もちろん、シリアライゼーションなどの操作を喜んで実行したい場合は、eval何でも可能です。

以下は、同じ原理を使用するマージソートです。

sort ()
{
    n=1
    while [ $n -lt $# ]
    do
        h=0
        k=$n
        l=$n
        while [ $h -lt $# ]
        do
            i=0
            j=0
            if [ $(($# - h)) -lt $((n << 1)) ]
            then
                if [ $(($# - h)) -le $n ]
                then
                    k=$(($# - h))
                    l=0
                else
                    l=$(($# % n))
                fi
            fi
            for x
            do
                [ $i -eq 0 ] && shift $k
                while [ $j -lt $l ]
                do
                    if [ $i -eq $k ] || "$cmp" "$x" "$1"
                    then
                        set -- "$@" "$1"
                        shift
                        j=$((j + 1))
                    else
                        break
                    fi
                done
                [ $i -eq $k ] && break
                set -- "$@" "$x"
                i=$((i + 1))
            done
            h=$((h + (n << 1)))
        done
        n=$((n << 1))
    done
    "$cont" "$@"
}

$ shuf /usr/share/dict/words | head -n 1000 | xargs -d '\n' sh -c 'time sh sort.sh "$@"' sh >/dev/null
 
real    0m19.918s
user    0m19.917s
sys     0m0.001s

関連情報