Как отсортировать массив в Bash

У меня есть массив в Bash, например:

array=(a c b f 3 5)

Мне нужно отсортировать массив. Не просто показ содержимого сортированным способом, но и получение нового массива с отсортированными элементами. Новый отсортированный массив может быть совершенно новым или старым.

Ответы

Ответ 1

Вам не нужно много кода:

IFS=$'\n' sorted=($(sort <<<"${array[*]}"))
unset IFS

Поддерживает пробелы в элементах (если только это не перевод строки) и работает в Bash 3.x.

например.:

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

Примечание. @sorontar указал, что необходимо соблюдать осторожность, если элементы содержат символы подстановки, такие как * или ?:

Часть sorted = ($ (...)) использует оператор "split и glob". Вы должны выключить glob: set -f или set -o noglob или shopt -op noglob, или элемент массива, например *, будет расширен до списка файлов.

Что происходит:

В результате получается шесть вещей, которые происходят в следующем порядке:

  1. IFS=$'\n'
  2. "${array[*]}"
  3. <<<
  4. sort
  5. sorted=($(...))
  6. unset IFS

Во-первых, IFS=$'\n'

Это важная часть нашей операции, которая влияет на результаты 2 и 5 следующим образом:

Дано:

  • "${array[*]}" расширяется до каждого элемента, ограниченного первым символом IFS
  • sorted=() создает элементы путем разделения на каждый символ IFS

IFS=$'\n' настраивает так, чтобы элементы расширялись с использованием новой строки в качестве разделителя, а затем создавались таким образом, чтобы каждая строка становилась элементом. (то есть разделение на новую строку.)

Разделение новой строкой важно, потому что так работает sort (сортировка по строке). Разделение только новой строкой не так важно, но необходимо сохранить элементы, содержащие пробелы или табуляции.

Значение по умолчанию IFS - это пробел, табуляция, за которой следует новая строка, и она не подходит для нашей работы.

Далее часть sort <<<"${array[*]}"

<<<, называемый here strings, принимает расширение "${array[*]}", как описано выше, и подает его на стандартный ввод sort.

В нашем примере sort передается следующая строка:

a c
b
f
3 5

Так как sort сортирует, он производит:

3 5
a c
b
f

Далее, часть sorted=($(...))

Часть $(...), называемая подстановка команд, заставляет ее содержимое (sort <<<"${array[*]}) запускаться как обычную команду, в то время как полученный стандартный вывод выводится как литерал, который идет куда угодно $(...).

В нашем примере это производит нечто похожее на простое написание:

sorted=(3 5
a c
b
f
)

sorted затем становится массивом, который создается путем разбиения этого литерала на каждой новой строке.

Наконец, unset IFS

Это сбрасывает значение IFS на значение по умолчанию, и это просто хорошая практика.

Это сделано для того, чтобы мы не создавали проблем с чем-либо, что опирается на IFS позже в нашем скрипте. (В противном случае нам нужно помнить, что мы все изменили - что может быть непрактично для сложных сценариев.)

Ответ 2

Оригинальный ответ:

array=(a c b "f f" 3 5)
readarray -t sorted < <(for a in "${array[@]}"; do echo "$a"; done | sort)

выход:

$ for a in "${sorted[@]}"; do echo "$a"; done
3
5
a
b
c
f f

Примечание. Эта версия соответствует значениям, содержащим специальные символы или пробелы (кроме строк новой строки)

Примечание readarray поддерживается в bash 4+.

Изменить. Основываясь на предложении @Dimitre, я обновил его до:

readarray -t sorted < <(printf '%s\0' "${array[@]}" | sort -z | xargs -0n1)

который имеет преимущество даже в понимании элементов сортировки с символами новой строки, встроенными правильно. К сожалению, как правильно сигнализировал @ruakh, это не означало, что результат readarray был бы правильным, потому что readarray не имеет возможности использовать NUL вместо обычных новых строк как разделители строк.

Ответ 3

Здесь используется чистая реализация Bash quicksort:

#!/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")'

Эта реализация рекурсивна... так что здесь итеративный quicksort:

#!/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=("[email protected]")
   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=("[email protected]")
   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

чтобы файлы в текущей папке отсортировались по времени модификации (сначала самые новые).

Примечание. Эти функции являются чистыми Bash! никаких внешних утилит и никаких подоболочек! они безопасны по любым смешным символам, которые у вас могут быть (пробелы, символы новой строки, символы глобуса и т.д.).

Ответ 4

Если вам не нужно обрабатывать специальные символы оболочки в элементах массива:

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

В bash вам понадобится внешняя программа сортировки.

С zsh не требуются внешние программы и легко обрабатываются специальные символы оболочки:

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

ksh имеет set -s для сортировки ASCIIbetically.

Ответ 5

В 3-часовой поездке на поезде из Мюнхена во Франкфурт, с которой мне трудно было добраться, потому что Октоберфест начинается завтра), я думал о своем первом посте. Использование глобального массива - гораздо лучшая идея для общей функции сортировки. Следующая функция обрабатывает суровые строки (новые строки, пробелы и т.д.):

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=("[email protected]")
    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[@]}

Обратите внимание, что, вероятно, Bash внутренне использует интеллектуальные указатели, поэтому операция свопинга может быть дешевой (хотя я сомневаюсь). Однако bubble_sort демонстрирует, что более продвинутые функции, такие как merge_sort, также доступны для языка оболочки.

Ответ 6

tl; dr:

Сортировка массива a_in и сохранение результата в a_out (элементы не должны иметь встроенных строк новой строки [1] ):

Bash v4 +:

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

Bash v3:

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

Преимущества для антик-решения:

  • Вам не нужно беспокоиться о случайном чередовании (случайная интерпретация элементов массива как шаблонов имен файлов), поэтому для отключения перетаскивания (set -f и set +f для восстановления позже) не требуется дополнительная команда.

  • Вам не нужно беспокоиться о сбросе IFS с помощью unset IFS. [2]

Дополнительное чтение: пояснение и пример кода

Вышеупомянутый сочетает Bash с внешней утилитой sort для решения, которое работает с произвольными однострочными элементами и лексической или числовой сортировкой (необязательно по полю):

  • Производительность. Для около 20 элементов или более это будет быстрее, чем чистое решение Bash - значительно и все чаще, когда вы получаете около 100 элементов.
    (Точные пороговые значения будут зависеть от вашего конкретного входа, машины и платформы.)

    • Причина заключается в том, что он избегает Bash циклов.

  • printf '%s\n' "${a_in[@]}" | sort выполняет сортировку (лексически, по умолчанию - см. sort POSIX spec):

    • "${a_in[@]}" безопасно расширяет элементы массива a_in как отдельные аргументы, независимо от того, что они содержат (включая пробелы).

    • printf '%s\n' затем печатает каждый аргумент, т.е. каждый элемент массива - в своей собственной строке, как есть.

  • Обратите внимание на использование подстановки процесса (<(...)), чтобы предоставить отсортированный результат как вход в read/readarray (путем перенаправления на stdin, <), поскольку read/readarray должен выполняться в текущей оболочке (не должен запускаться в подоболочке) чтобы выходная переменная a_out была видимой для текущей оболочки (для того, чтобы переменная оставалась определенной в остальной части script).

  • Чтение sort вывода в переменную массива:

    • Bash v4 +: readarray -t a_out считывает отдельные строки, выводимые sort в элементы переменной массива a_out, не включая конечный \n в каждом элементе (-t).

    • Bash v3: readarray не существует, поэтому read необходимо использовать:
      IFS=$'\n' read -d '' -r -a a_out сообщает read читать в массив (-a) переменную a_out, считывая весь ввод, по строкам (-d ''), но разбивая его на элементы массива на строки новой строки (IFS=$'\n'. $'\n', который создает литеральную новую строку (LF), представляет собой так называемую строку с цитированием ANSI C).
      (-r, параметр, который должен использоваться всегда с read, отключает неожиданную обработку символов \.)

Аннотированный пример кода:

#!/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[@]}"

Из-за использования sort без параметров это дает лексическую сортировку (цифры сортируются перед буквами, а цифровые последовательности обрабатываются лексически, а не как числа):

*
10
5
a c
b
f

Если вам нужна цифровая сортировка по 1-ому полю, вы должны использовать sort -k1,1n вместо sort, который дает (сортировка не чисел для чисел и чисел сортируется правильно):

*
a c
b
f
5
10

[1] Для обработки элементов со встроенными новыми строками используйте следующий вариант (Bash v4 +, с GNU sort):
readarray -d '' -t a_out < <(printf '%s\0' "${a_in[@]}" | sort -z).
Полезный ответ Michał Górny содержит решение Bash v3.

[2] Пока IFS установлен в варианте Bash v3, это изменение относится к команде.
Напротив, то, что следует IFS=$'\n'  в ответе на antak, - это назначение, а не команда, и в этом случае изменение IFS является глобальным.

Ответ 7

Другое решение, использующее внешний sort, и справляется с любыми специальными символами (кроме NULs:)). Должен работать с bash -3.2 и GNU или BSD sort (к сожалению, POSIX не включает -z).

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

Сначала посмотрите на перенаправление ввода в конце. Мы используем встроенный printf для записи элементов массива с нулевым завершением. Цитирование гарантирует, что элементы массива передаются как есть, а спецификация оболочки printf заставляет его повторно использовать последнюю часть строки формата для каждого оставшегося параметра. То есть, это эквивалентно чем-то вроде:

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

Список элементов с нулевым завершением затем передается в sort. Опция -z заставляет ее считывать элементы с нулевым символом, сортировать их и выводить также нуль-конец. Если вам нужно получить только уникальные элементы, вы можете передать -u, поскольку он более переносимый, чем uniq -z. LC_ALL=C обеспечивает стабильный порядок сортировки независимо от локали - иногда полезен для скриптов. Если вы хотите, чтобы sort уважал языковой стандарт, удалите его.

Конструкция <() получает дескриптор для чтения из порожденного конвейера, а < перенаправляет на него стандартный ввод цикла while. Если вам нужен доступ к стандартным входам внутри канала, вы можете использовать другой дескриптор - упражнение для читателя:).

Теперь вернемся к началу. Встроенный модуль read считывает выходные данные из перенаправленного stdin. Установка пустого IFS отключает разделение слов, которое здесь не нужно - в результате read считывает всю "строку" ввода в одну предоставленную переменную. Параметр -r отключает также обработку нежелательной обработки. Наконец, -d '' устанавливает разделитель строки в NUL, то есть сообщает read читать строки с нулевым завершением.

В результате цикл выполняется один раз для каждого последующего элемента массива с нулевым завершением, причем значение сохраняется в e. Пример просто помещает элементы в другой массив, но вы можете их обработать напрямую:).

Конечно, это только один из многих способов достижения одной и той же цели. Как я вижу, это проще, чем реализовать полный алгоритм сортировки в bash, а в некоторых случаях он будет быстрее. Он обрабатывает все специальные символы, включая новые строки, и должен работать на большинстве общих систем. Самое главное, это может научить вас чему-то новому и удивительному в отношении bash:).

Ответ 8

попробуйте следующее:

echo ${array[@]} | awk 'BEGIN{RS=" ";} {print $1}' | sort

Выход будет:

3
5
a
b
c
f

Проблема решена.

Ответ 9

мин сортировать:

#!/bin/bash
array=(.....)
index_of_element1=0

while (( ${index_of_element1} < ${#array[@]} )); do

    element_1="${array[${index_of_element1}]}"

    index_of_element2=$((index_of_element1 + 1))
    index_of_min=${index_of_element1}

    min_element="${element_1}"

        for element_2 in "${array[@]:$((index_of_element1 + 1))}"; do
            min_element="'printf "%s\n%s" "${min_element}" "${element_2}" | sort | head -n+1'"      
            if [[ "${min_element}" == "${element_2}" ]]; then
                index_of_min=${index_of_element2}
            fi
            let index_of_element2++
        done

        array[${index_of_element1}]="${min_element}"
        array[${index_of_min}]="${element_1}"

    let index_of_element1++
done

Ответ 10

Если вы можете вычислить уникальное целое число для каждого элемента массива, например:

tab='0123456789abcdefghijklmnopqrstuvwxyz'

# build the reversed ordinal map
for ((i = 0; i < ${#tab}; i++)); do
    declare -g ord_${tab:i:1}=$i
done

function sexy_int() {
    local sum=0
    local i ch ref
    for ((i = 0; i < ${#1}; i++)); do
        ch="${1:i:1}"
        ref="ord_$ch"
        (( sum += ${!ref} ))
    done
    return $sum
}

sexy_int hello
echo "hello -> $?"
sexy_int world
echo "world -> $?"

тогда вы можете использовать эти целые числа как индексы массивов, потому что Bash всегда использует разреженный массив, поэтому не нужно беспокоиться о неиспользуемых индексах:

array=(a c b f 3 5)
for el in "${array[@]}"; do
    sexy_int "$el"
    sorted[$?]="$el"
done

echo "${sorted[@]}"
  • Pros. Быстро.
  • Cons. Дублированные элементы объединяются, и невозможно сопоставить содержимое с 32-битными уникальными целыми числами.

Ответ 11

array=(a c b f 3 5)
new_array=($(echo "${array[@]}" | sed 's/ /\n/g' | sort))    
echo ${new_array[@]}

Содержание эха new_array будет:

3 5 a b c f

Ответ 12

Я не уверен, что вам понадобится внешняя программа сортировки в Bash.

Вот моя реализация для простого алгоритма сортировки пузырьков.

function bubble_sort()
{   #
    # Sorts all positional arguments and echoes them back.
    #
    # Bubble sorting lets the heaviest (longest) element sink to the bottom.
    #
    local array=([email protected]) max=$(($# - 1))
    while ((max > 0))
    do
        local i=0
        while ((i < max))
        do
            if [ ${array[$i]} \> ${array[$((i + 1))]} ]
            then
                local t=${array[$i]}
                array[$i]=${array[$((i + 1))]}
                array[$((i + 1))]=$t
            fi
            ((i += 1))
        done
        ((max -= 1))
    done
    echo ${array[@]}
}

array=(a c b f 3 5)
echo " input: ${array[@]}"
echo "output: $(bubble_sort ${array[@]})"

Это напечатает:

 input: a c b f 3 5
output: 3 5 a b c f

Ответ 13

a=(e b 'c d')
shuf -e "${a[@]}" | sort >/tmp/f
mapfile -t g </tmp/f

Ответ 14

Существует обходной путь для обычной проблемы пространств и строк:

Используйте символ, который не находится в исходном массиве (например, $'\1' или $'\4' или аналогичный).

Эта функция выполняет задание:

# Sort an Array may have spaces or newlines with a workaround (wa=$'\4')
sortarray(){ local wa=$'\4' IFS=''
             if [[ $* =~ [$wa] ]]; then
                 echo "$0: error: array contains the workaround char" >&2
                 exit 1
             fi

             set -f; local IFS=$'\n' x nl=$'\n'
             set -- $(printf '%s\n' "${@//$nl/$wa}" | sort -n)
             for    x
             do     sorted+=("${x//$wa/$nl}")
             done
       }

Это отсортирует массив:

$ array=( a b 'c d' $'e\nf' $'g\1h')
$ sortarray "${array[@]}"
$ printf '<%s>\n' "${sorted[@]}"
<a>
<b>
<c d>
<e
f>
<gh>

Это будет жаловаться на то, что исходный массив содержит обходной символ:

$ array=( a b 'c d' $'e\nf' $'g\4h')
$ sortarray "${array[@]}"
./script: error: array contains the workaround char

Описание

  • Мы установили две локальные переменные wa (обходной путь char) и нулевой IFS
  • Затем (с ifs null) мы проверяем, что весь массив $*.
  • Не содержит никаких проблем char [[ $* =~ [$wa] ]].
  • Если это так, поднимите сообщение и сообщите об ошибке: exit 1
  • Избегайте расширений имен файлов: set -f
  • Задайте новое значение IFS (IFS=$'\n') переменной цикла x и новой строки var (nl=$'\n').
  • Мы печатаем все значения полученных аргументов (входной массив [email protected]).
  • но мы заменяем любую новую строку обходным способом char "${@//$nl/$wa}".
  • отправьте эти значения для сортировки sort -n.
  • и поместите все отсортированные значения в позиционные аргументы set --.
  • Затем мы назначаем каждый аргумент один за другим (для сохранения новых строк).
  • в цикле for x
  • в новый массив: sorted+=(…)
  • внутри кавычек для сохранения любой существующей новой строки.
  • восстановление обходного пути к новой строке "${x//$wa/$nl}".
  • сделано

Ответ 15

sorted=($(echo ${array[@]} | tr " " "\n" | sort))

В духе bash/linux я буду использовать лучший инструмент командной строки для каждого шага. sort выполняет основное задание, но требует ввода, разделенного новой строкой, а не пространства, поэтому простой проложенный конвейер просто делает:

Содержимое массива Echo → заменить пространство с помощью новой строки → sort

$() должен отражать результат

($()) заключается в том, чтобы поместить "эхо-результат" в массив

Примечание: как @sorontar упоминается в comment к другому вопросу:

В отсортированной = ($ (...)) части используется оператор split и glob. Вы должны отключить glob: set -f или set -o noglob или shopt -op noglob, или элемент массива вроде * будет расширен до списка файлов.