Comment trier un tableau en Bash

réponse originale:

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

sortie:

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

Note cette version fonctionne avec des valeurs qui contient des caractères spéciaux ou des espaces ( sauf les retours à la ligne)

Note readarray est supporté en bash 4+.

modifier sur la base de la suggestion de @Dimitre Je l'avais mis à jour à:

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

qui a l'avantage de même comprendre tri éléments avec des caractères newline intégré correctement. Malheureusement, comme indiqué correctement par @ruakh cela ne signifie pas que le résultat de readarray serait correct , parce que readarray n'a pas d'option pour utiliser NUL au lieu de newlines comme séparateurs de ligne.

Ici est un pur Bash implémentation rapide:

#!/bin/bash

# quicksorts positional arguments
# return is in array qsort_ret
qsort() {
   local pivot i smaller=() larger=()
   qsort_ret=()
   (($#==0)) && return 0
   pivot=
   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[@]}" )
}

utiliser comme, p.ex.,

$ 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")'

cette implémentation est récursive... alors voici un quicksort itératif:

#!/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
}

dans les deux cas, vous pouvez changer l'ordre que vous utilisez: j'ai utilisé des comparaisons de chaîne, mais vous pouvez utiliser des comparaisons arithmétiques, comparer le temps de modification de fichier wrt, etc. suffit d'utiliser le test approprié; vous pouvez même faire plus générique, et ont il utilise un premier argument qui est la fonction de test utiliser, par exemple,

#!/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=
   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
}

alors vous pouvez avoir cette fonction de comparaison:

compare_mtime() { [[  -nt  ]]; }

et utilisation:

$ qsort compare_mtime *
$ declare -p qsort_ret

pour avoir les fichiers dans le dossier courant triés par le temps de modification (la plus récente d'abord).

NOTE. Ces fonctions sont pures Bash! aucun des utilitaires externes, et pas de sous-coquille! ils sont sûrs wrt tous les symboles drôles que vous pouvez avoir (espaces, newline personnages, personnages globulaires,etc.).

si vous n'avez pas besoin de gérer les caractères spéciaux de l'interpréteur de commandes dans les éléments du tableau:

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

avec bash vous aurez besoin d'un programme de tri externe de toute façon.

avec zsh aucun programme externe n'est nécessaire et les caractères spéciaux de l'interpréteur de commandes sont facilement manipulés:

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

KSH a set -s pour trier Asciibétiquement .

dans le voyage de trois heures en train de Munich à Francfort (que j'ai eu du mal à atteindre parce que L'Oktoberfest commence demain) je pensais à mon premier poste. Employant un tableau global est une bien meilleure idée pour une fonction de tri. La fonction suivante s'occupe des cordes arbitaires(lignes, blancs, etc.):

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[@]}

Cette affiche:

3 5 a b c z y

la même sortie est créée à partir de

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

noter que probablement Bash utilise en interne smart-pointeurs, de sorte que le swap-opération pourrait être bon marché (bien que j'en doute). Cependant, bubble_sort démontre que des fonctions plus avancées comme merge_sort sont également à la portée du langage shell.

tl; dr :

Trier tableau a_in et stocker le résultat dans a_out (les éléments ne doivent pas avoir intégré newlines ^[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)

avantages par rapport à solution d'antak :

• vous n'avez pas à vous soucier de globbing accidentel (interprétation accidentelle des éléments du tableau comme des motifs de nom de fichier), donc aucune commande supplémentaire n'est nécessaire pour désactiver globbing ( set -f , et set +f pour le restaurer plus tard).

• vous n'avez pas à vous soucier de réinitialiser IFS avec unset IFS . ^[2]

mention facultative: explication et Code de l'échantillon

ce qui précède combine le code Bash avec l'utilité externe sort pour une solution qui fonctionne avec arbitraire simple - éléments de ligne et soit tri lexical ou numérique (optionnel par champ) :

• Performance : pour environ 20 éléments ou plus , ce sera 1519550920" plus rapide qu'une solution de Bash pure - de manière significative et de plus en plus une fois que vous obtenez au-delà d'environ 100 éléments.
  
  ^{(les seuils exacts dépendent de votre entrée, de votre machine et de votre plateforme.)}

  • la raison pour laquelle il est rapide est qu'il évite Bash boucles .

• printf '%s\n' "${a_in[@]}" | sort effectue le tri (lexicalement, par défaut-voir sort 's POSIX spec ):

  • "${a_in[@]}" étend en toute sécurité aux éléments du tableau a_in comme arguments individuels , tout ce qu'ils contiennent (y compris l'espace).

  • printf '%s\n' imprime ensuite chaque argument - i.e., chaque élément de tableau - sur sa propre ligne, telle quelle.

• Note The use of a process substitution ( <(...) ) pour fournir la sortie triée en entrée read / readarray (via une redirection vers stdin, < ), parce que read / readarray doit exécuter dans le current shell (ne doit pas exécuter dans un subshell ) afin que la variable de sortie a_out soit visible par le shell courant (pour que la variable reste définie dans le reste du script).

• lecture sort 'S sortie dans un tableau variable :

  • Bash v4+: readarray -t a_out lit les lignes individuelles sorties par sort dans les éléments de la variable de tableau a_out , sans inclure la suite \n dans chaque élément ( -t ).

  • Bash v3: readarray n'existe pas, donc read doit être utilisé:
    
    IFS=$'\n' read -d '' -r -a a_out indique read pour lire dans le tableau ( -a ) la variable a_out , en lisant l'entrée entière, à travers les lignes ( -d '' ), mais en le divisant en éléments de tableau par newlines ( IFS=$'\n' ). $'\n' , qui produit une nouvelle ligne littérale (LF), est une soi-disant chaîne ANSI C-quoted ).
    
    ( -r , une option qui devrait presque toujours être utilisée avec read , empêche la manipulation inattendue des caractères \ .)

échantillon annoté code:

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

en raison de l'utilisation de sort sans options, cela donne lexical tri (tri des chiffres avant les lettres, et les séquences de chiffres sont traités lexicalement, pas comme des numéros):

*
10
5
a c
b
f

si vous vouliez numérique Tri par le 1er champ, vous utiliseriez sort -k1,1n au lieu de simplement sort , ce qui donne (les non-nombres trient avant les nombres, et les nombres trient correctement):

*
a c
b
f
5
10

<sup>[1] pour manipuler des éléments avec des lignes de nouvelle encastrées, utilisez la variante suivante (Bash v4+, avec GNU sort ):

readarray -d '' -t a_out < <(printf '%s"1519460920"' "${a_in[@]}" | sort -z) .

Michał Górny de réponse utile a un Bash v3 solution.</sup>

<sup>[2] alors que IFS est placé dans la variante Bash v3, le changement est scopé à la commande .

En revanche, ce qui suit IFS=$'\n'  dans la réponse d'antak est une affectation plutôt qu'une commande, auquel cas le changement IFS est global .</sup>

une autre solution qui utilise des caractères spéciaux externes sort et qui copie avec tout (sauf pour NULs :)). Devrait fonctionner avec bash-3.2 et GNU ou BSD sort (malheureusement, POSIX n'inclut pas -z ).

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

regardez D'abord la redirection d'entrée à la fin. Nous utilisons printf intégré pour écrire les éléments du tableau, zéro-terminé. La citation permet de s'assurer que les éléments du tableau sont passés tels quels, et les spécificités du shell printf font en sorte qu'il réutilise la dernière partie de la chaîne de format pour chaque paramètre restant. C'est, c'est équivalent à quelque chose comme:

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

la liste des éléments Nuls est alors passée à sort . L'option -z lui fait lire les éléments à fin nulle, les trier et les afficher à fin nulle. Si vous avez besoin pour obtenir uniquement les éléments uniques, vous pouvez passer -u , car il est plus portable que uniq -z . Le LC_ALL=C assure un ordre de tri stable indépendamment de la locale - parfois utile pour les scripts. Si vous voulez que le sort respecte locale, supprimez cela.

la construction <() obtient le descripteur à lire à partir du pipeline frayé, et < redirige l'entrée standard de la boucle while vers elle. Si vous avez besoin d'accéder à l'entrée standard à l'intérieur du tuyau, vous pouvez utiliser un autre descripteur - exercice pour le lecteur :).

maintenant, retour au début. Le read intégré lit la sortie du STDIN redirigé. Le paramètre vide IFS désactive le dédoublement de mots qui est inutile ici - en conséquence, read lit toute la "ligne" d'entrée à la variable unique fournie. L'option -r désactive le traitement de l'évasion qui n'est pas souhaité ici aussi. Enfin, -d '' définit le délimiteur de ligne à NUL - c'est-à-dire qu'il indique read pour lire zéro-terminé chaîne.

en conséquence, la boucle est exécutée une fois pour chaque élément de tableau à zéro extrémité successif, la valeur étant stockée dans e . L'exemple met juste les éléments dans un autre tableau mais vous préférez peut-être les traiter directement :).

bien sûr, c'est juste l'une des nombreuses façons d'atteindre le même objectif. Comme je le vois, il est plus simple que la mise en œuvre de l'algorithme de tri complet dans bash et dans certains cas, il sera plus rapide. Il s'occupe de tous les caractères spéciaux, y compris les nouvelles lignes, et devrait fonctionner sur la plupart des systèmes communs. Plus important encore, il peut vous enseigner quelque chose de nouveau et génial sur bash :).

essayez ceci:

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

sortie sera:

3
5
a
b
c
f

Problème résolu.

min genre:

#!/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

Si vous pouvez calculer un entier unique pour chaque élément dans le tableau, comme ceci:

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 -> $?"

alors, vous pouvez utiliser ces entiers comme index de tableau, parce que Bash utilisent toujours tableau clairsemé, donc pas besoin de se soucier des index inutilisés:

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

echo "${sorted[@]}"

• Pros. Rapide.
• Cons. Les éléments dupliqués sont fusionnés, et il peut être impossible de mapper des contenus à des entiers uniques de 32 bits.

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

contenu echo de new_array sera:

3 5 a b c f

Je ne suis pas convaincu que vous aurez besoin d'un programme de tri externe à Bash.

Voici mon implémentation pour le simple algorithme de tri de bulles.

function bubble_sort()
{   #
    # Sorts all positional arguments and echoes them back.
    #
    # Bubble sorting lets the heaviest (longest) element sink to the bottom.
    #
    local array=($@) 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[@]})"

ceci doit être écrit:

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

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

il y a une solution pour le problème habituel des espaces et des nouvelles lignes:

Utiliser un caractère qui n'est pas dans le tableau d'origine (comme $'' ou $'' ou similaire).

Cette fonction obtient le travail fait:

# Sort an Array may have spaces or newlines with a workaround (wa=$'')
sortarray(){ local wa=$'' IFS=''
             if [[ $* =~ [$wa] ]]; then
                 echo ""151900920": 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
       }

cela va trier le tableau:

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

cela va se plaindre que le tableau source contient le caractère workaround:

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

description

• nous avons défini deux variables locales wa (contournement de char) et un "si nul
• ensuite (avec ifs null) nous testons que l'ensemble du tableau $* .
• ne contient pas de woraround char [[ $* =~ [$wa] ]] .
• si elle le fait, élever un message et signaler une erreur: exit 1
• éviter les extensions de noms de fichiers: set -f
• définit une nouvelle valeur de IFS ( IFS=$'\n' ), une variable boucle x et un var newline ( nl=$'\n' ).
• Nous imprimons toutes les valeurs des arguments reçus (le tableau d'entrée $@ ).
• mais nous remplaçons toute nouvelle ligne par le char de contournement "${@//$nl/$wa}" .
• envoyer ces valeurs pour être trié sort -n .
• et replacer toutes les valeurs triées dans les arguments de position set -- .
• puis nous assignons chaque argument un par un (pour préserver newlines).
• dans une boucle for x
• à un nouveau tableau: sorted+=(…)
• entre guillemets pour préserver toute nouvelle ligne existante.
• restauration de la solution à une nouvelle ligne "${x//$wa/$nl}" .
• fait

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

dans l'esprit de bash / linux, je piloterais le meilleur outil de ligne de commande pour chaque étape. sort fait le travail principal mais a besoin d'entrée séparée par newline au lieu de l'espace, de sorte que le pipeline très simple ci-dessus fait simplement:

contenu du tableau D'écho -- > remplacer l'espace par newline -- > trier

$() est l'écho du résultat

($()) est de mettre le "résultat repris" dans un array

Note : comme @sorontar a mentionné dans un commentaire à une question différente:

Le tri=($(...)) part utilise l'opérateur" split and glob". Vous devez désactiver glob: set-f ou set-o noglob ou shopt-op noglob ou un élément du tableau comme * sera étendu à une liste de fichiers.