[arrays] Bash에서 배열을 정렬하는 방법

순수한 Bash 퀵 정렬 구현은 다음과 같습니다.

#!/bin/bash

# quicksorts positional arguments
# return is in array qsort_ret
qsort() {
   local pivot i smaller=() larger=()
   qsort_ret=()
   (($#==0)) && return 0
   pivot=$1
   shift
   for i; do
      if (( i < pivot )); then
         smaller+=( "$i" )
      else
         larger+=( "$i" )
      fi
   done
   qsort "${smaller[@]}"
   smaller=( "${qsort_ret[@]}" )
   qsort "${larger[@]}"
   larger=( "${qsort_ret[@]}" )
   qsort_ret=( "${smaller[@]}" "$pivot" "${larger[@]}" )
}

예를 들어,

$ array=(a c b f 3 5)
$ qsort "${array[@]}"
$ declare -p qsort_ret
declare -a qsort_ret='([0]="3" [1]="5" [2]="a" [3]="b" [4]="c" [5]="f")'

이 구현은 재귀 적입니다. 따라서 반복적 인 퀵 정렬이 있습니다 :

#!/bin/bash

# quicksorts positional arguments
# return is in array qsort_ret
# Note: iterative, NOT recursive! :)
qsort() {
   (($#==0)) && return 0
   local stack=( 0 $(($#-1)) ) beg end i pivot smaller larger
   qsort_ret=("$@")
   while ((${#stack[@]})); do
      beg=${stack[0]}
      end=${stack[1]}
      stack=( "${stack[@]:2}" )
      smaller=() larger=()
      pivot=${qsort_ret[beg]}
      for ((i=beg+1;i<=end;++i)); do
         if [[ "${qsort_ret[i]}" < "$pivot" ]]; then
            smaller+=( "${qsort_ret[i]}" )
         else
            larger+=( "${qsort_ret[i]}" )
         fi
      done
      qsort_ret=( "${qsort_ret[@]:0:beg}" "${smaller[@]}" "$pivot" "${larger[@]}" "${qsort_ret[@]:end+1}" )
      if ((${#smaller[@]}>=2)); then stack+=( "$beg" "$((beg+${#smaller[@]}-1))" ); fi
      if ((${#larger[@]}>=2)); then stack+=( "$((end-${#larger[@]}+1))" "$end" ); fi
   done
}

두 경우 모두 사용 순서를 변경할 수 있습니다. 문자열 비교를 사용했지만 산술 비교, wrt 파일 수정 시간 비교 등을 수행 할 수 있습니다. 적절한 테스트 만 사용하십시오. 좀 더 일반적인 것으로 만들 수도 있고 테스트 함수가 사용하는 첫 번째 인수를 사용할 수도 있습니다.

#!/bin/bash

# quicksorts positional arguments
# return is in array qsort_ret
# Note: iterative, NOT recursive! :)
# First argument is a function name that takes two arguments and compares them
qsort() {
   (($#<=1)) && return 0
   local compare_fun=$1
   shift
   local stack=( 0 $(($#-1)) ) beg end i pivot smaller larger
   qsort_ret=("$@")
   while ((${#stack[@]})); do
      beg=${stack[0]}
      end=${stack[1]}
      stack=( "${stack[@]:2}" )
      smaller=() larger=()
      pivot=${qsort_ret[beg]}
      for ((i=beg+1;i<=end;++i)); do
         if "$compare_fun" "${qsort_ret[i]}" "$pivot"; then
            smaller+=( "${qsort_ret[i]}" )
         else
            larger+=( "${qsort_ret[i]}" )
         fi
      done
      qsort_ret=( "${qsort_ret[@]:0:beg}" "${smaller[@]}" "$pivot" "${larger[@]}" "${qsort_ret[@]:end+1}" )
      if ((${#smaller[@]}>=2)); then stack+=( "$beg" "$((beg+${#smaller[@]}-1))" ); fi
      if ((${#larger[@]}>=2)); then stack+=( "$((end-${#larger[@]}+1))" "$end" ); fi
   done
}

그런 다음이 비교 기능을 가질 수 있습니다.

compare_mtime() { [[ $1 -nt $2 ]]; }

그리고 사용 :

$ qsort compare_mtime *
$ declare -p qsort_ret

현재 폴더의 파일을 수정 시간순으로 정렬합니다 (가장 먼저).

노트. 이 기능은 순수한 배쉬입니다! 외부 유틸리티도없고 서브 쉘도 없습니다! 그것들은 당신이 가질 수있는 재미있는 기호 (공백, 줄 바꿈 문자, 글로브 문자 등)로 안전합니다.

답변

array=(a c b f 3 5)
sorted=($(printf '%s\n' "${array[@]}"|sort))

% array=('a a' c b f 3 5); printf '%s\n' "${(o)array[@]}"
3
5
a a
b
c
f

readarray -t a_out < <(printf '%s\n' "${a_in[@]}" | sort)

IFS=$'\n' read -d '' -r -a a_out < <(printf '%s\n' "${a_in[@]}" | sort)

#!/usr/bin/env bash

# Define input array `a_in`:
# Note the element with embedded whitespace ('a c')and the element that looks like
# a glob ('*'), chosen to demonstrate that elements with line-internal whitespace
# and glob-like contents are correctly preserved.
a_in=( 'a c' b f 5 '*' 10 )

# Sort and store output in array `a_out`
# Saving back into `a_in` is also an option.
IFS=$'\n' read -d '' -r -a a_out < <(printf '%s\n' "${a_in[@]}" | sort)
# Bash 4.x: use the simpler `readarray -t`:
# readarray -t a_out < <(printf '%s\n' "${a_in[@]}" | sort)

# Print sorted output array, line by line:
printf '%s\n' "${a_out[@]}"

*
10
5
a c
b
f

*
a c
b
f
5
10

declare BSORT=()
function bubble_sort()
{   #
    # @param [ARGUMENTS]...
    #
    # Sort all positional arguments and store them in global array BSORT.
    # Without arguments sort this array. Return the number of iterations made.
    #
    # Bubble sorting lets the heaviest element sink to the bottom.
    #
    (($# > 0)) && BSORT=("$@")
    local j=0 ubound=$((${#BSORT[*]} - 1))
    while ((ubound > 0))
    do
        local i=0
        while ((i < ubound))
        do
            if [ "${BSORT[$i]}" \> "${BSORT[$((i + 1))]}" ]
            then
                local t="${BSORT[$i]}"
                BSORT[$i]="${BSORT[$((i + 1))]}"
                BSORT[$((i + 1))]="$t"
            fi
            ((++i))
        done
        ((++j))
        ((--ubound))
    done
    echo $j
}

bubble_sort a c b 'z y' 3 5
echo ${BSORT[@]}

3 5 a b c z y

BSORT=(a c b 'z y' 3 5)
bubble_sort
echo ${BSORT[@]}

local e new_array=()
while IFS= read -r -d '' e; do
    new_array+=( "${e}" )
done < <(printf "%s\0" "${array[@]}" | LC_ALL=C sort -z)

for e in "${array[@]}"; do
    printf "%s\0" "${e}"
done