☰

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. 그러나 목록은 하나만 있을 수 있으므로 정렬이 제자리에서 수행되어야 하며 병합 정렬 및 빠른 정렬과 같은 일반적인 알고리즘을 사용할 수 없습니다.

견본:

#!/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)하지만 gsub(q, q "\\" q q, s)POSIX가 지정되지 않은 동작을 생성하더라도 후자는 환경이나 비지박스를 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. 두 번째와 세 번째를 계속 비교하십시오. 위의 규칙을 반복하고 각 값 쌍에 대해 순서대로 반복하십시오.
    3. 두 번째 요소를 마지막 요소와 비교(교체)한 후 처음부터 다시 시작합니다(이전 실행보다 이전 요소 비교를 중지할 수 있음).
    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]
}

테스트 대상:

  • 데비안 12, 대시 0.5.12, GNU sed 4.9, Gawk 5.2.1
  • 데비안 12, 대시 0.5.12, Busybox 1.35.0 sed및awk
  • FreeBSD 13.2 sh및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

관련 정보