Come ordinare una matrice in Bash

Ho una matrice in Bash, ad esempio:

array=(acbf 3 5) 

Ho bisogno di ordinare l’array. Non solo visualizzare il contenuto in modo ordinato, ma per ottenere un nuovo array con gli elementi ordinati. La nuova matrice ordinata può essere completamente nuova o vecchia.

Non hai davvero bisogno di tutto quel codice:

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

Supporta gli spazi bianchi negli elementi (purché non sia una nuova riga) e funziona in Bash 3.x.

per esempio:

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

Nota: @sorontar ha sottolineato che è necessario prestare attenzione se gli elementi contengono caratteri jolly come * o ? :

La parte ordinata = ($ (...) utilizza l'operatore "split and glob". Dovresti distriggersre glob: set -f o set -o noglob o set -o noglob shopt -op noglob o un elemento dell'array come * verrà espanso in un elenco di file.

Cosa sta succedendo:

Il risultato è un culmine di sei cose che accadono in questo ordine:

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

Innanzitutto, l' IFS=$'\n'

Questa è una parte importante della nostra operazione che influisce sul risultato di 2 e 5 nel modo seguente:

Dato:

  • "${array[*]}" espande in ogni elemento delimitato dal primo carattere di IFS
  • sorted=() crea elementi dividendo su ogni carattere di IFS

IFS=$'\n' imposta le cose in modo che gli elementi vengano espansi usando una nuova riga come delimitatore, e successivamente creati in modo che ogni linea diventi un elemento. (cioè dividere su una nuova riga.)

La delimitazione di una nuova riga è importante perché è così che opera la classificazione (ordinamento per riga). La divisione solo di una nuova riga non è così importante, ma è necessario preservare elementi che contengono spazi o tabulazioni.

Il valore predefinito di IFS è uno spazio , una scheda , seguito da una nuova riga e non adatto alla nostra operazione.

Successivamente, l' sort <<<"${array[*]}" parte

<<< , chiamato stringhe qui , prende l'espansione di "${array[*]}" , come spiegato sopra, e lo inserisce nell'input standard di sort .

Con il nostro esempio, sort viene alimentato con questa stringa seguente:

 ac b f 3 5 

Dal momento che ordina , produce:

 3 5 ac b f 

Successivamente, la parte sorted=($(...))

La parte $(...) , chiamata sostituzione del comando , fa sì che il suo contenuto ( sort <<<"${array[*]} ) venga eseguito come un normale comando, mentre prende lo standard output risultante come il letterale che va dove mai $(...) era.

Nel nostro esempio, questo produce qualcosa di simile alla semplice scrittura:

 sorted=(3 5 ac b f ) 

sorted diventa quindi un array creato dividendo questo letterale su ogni nuova riga.

Infine, l' unset IFS

Ciò reimposta il valore di IFS sul valore predefinito ed è solo una buona pratica.

È per garantire che non causiamo problemi con qualcosa che si basa su IFS più avanti nel nostro script. (Altrimenti dovremmo ricordare che abbiamo cambiato le cose - qualcosa che potrebbe non essere pratico per script complessi.)

Risposta originale:

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

produzione:

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

Nota che questa versione gestisce i valori che contengono caratteri speciali o spazi bianchi ( eccetto le nuove linee)

Nota readarray è supportato in bash 4+.


Modifica In base al suggerimento di @Dimitre l'ho aggiornato a:

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

che ha il vantaggio di comprendere anche gli elementi di ordinamento con caratteri newline incorporati correttamente. Sfortunatamente, come correttamente segnalato da @ruakh, ciò non significava che il risultato di readarray sarebbe corretto , perché readarray non ha alcuna opzione per usare NUL invece delle normali righe nuove come separatori di riga.

Ecco una pura implementazione quicksort di 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[@]}" ) } 

Utilizzare come, ad esempio,

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

Questa implementazione è ricorsiva ... quindi ecco un quicksort iterativo:

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

In entrambi i casi, è ansible modificare l'ordine che si utilizza: ho usato confronti di stringhe, ma è ansible utilizzare i confronti aritmetici, confrontare il tempo di modifica del file wrt, ecc. Basta usare il test appropriato; puoi persino renderlo più generico e usare un primo argomento che usi la funzione di test, ad es.

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

Quindi puoi avere questa funzione di confronto:

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

e usare:

 $ qsort compare_mtime * $ declare -p qsort_ret 

per avere i file nella cartella corrente ordinati per ora di modifica (prima i più recenti).

NOTA. Queste funzioni sono pure Bash! nessuna utilità esterna e nessuna sottotitola! sono al sicuro tutti i simboli divertenti che si possono avere (spazi, caratteri newline, caratteri glob, ecc.).

Se non è necessario gestire caratteri speciali della shell negli elementi dell’array:

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

Con bash avrai comunque bisogno di un programma di smistamento esterno.

Con zsh non sono necessari programmi esterni e i caratteri speciali della shell sono facilmente gestibili:

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

ksh ha set -s per ordinare ASCIIeticamente .

Nel viaggio in treno di 3 ore da Monaco a Francoforte (che ho avuto difficoltà a raggiungere perché l’Oktoberfest inizia domani) stavo pensando al mio primo post. L’utilizzo di un array globale è un’idea molto migliore per una funzione di ordinamento generale. La seguente funzione gestisce le stringhe arbitary (newlines, spazi vuoti, ecc.):

 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 acb 'zy' 3 5 echo ${BSORT[@]} 

Questo stampa:

 3 5 abczy 

Lo stesso output è stato creato da

 BSORT=(acb 'zy' 3 5) bubble_sort echo ${BSORT[@]} 

Si noti che probabilmente Bash utilizza internamente puntatori intelligenti, quindi l’operazione di swap potrebbe essere economica (anche se ne dubito). Tuttavia, bubble_sort dimostra che anche funzioni più avanzate come merge_sort sono alla portata del linguaggio della shell.

tl; dr :

Ordina array a_in e memorizza il risultato in a_out (gli elementi non devono avere a_out incorporate [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) 

Vantaggi rispetto alla soluzione di antak :

  • Non è necessario preoccuparsi del globbing accidentale (interpretazione accidentale degli elementi dell'array come pattern del nome del file), quindi non è necessario alcun comando aggiuntivo per disabilitare il globbing ( set -f e set +f per ripristinarlo successivamente).

  • Non devi preoccuparti di resettare IFS con unset IFS . [2]


Lettura opzionale: spiegazione e codice di esempio

Quanto sopra combina il codice Bash con l' sort esterno per una soluzione che funziona con elementi di singola riga arbitrari e ordinamento lessicale o numerico (facoltativamente per campo) :

  • Prestazioni : per circa 20 elementi o più , questo sarà più veloce di una pura soluzione Bash, in modo significativo e sempre più importante una volta superato oltre 100 elementi.
    (Le soglie esatte dipenderanno dall'input, dalla macchina e dalla piattaforma specifici.)

    • Il motivo per cui è veloce è che evita i loop di Bash .
  • printf '%s\n' "${a_in[@]}" | sort printf '%s\n' "${a_in[@]}" | sort esegue l'ordinamento (in modo lessicale, per impostazione predefinita, vedere le specifiche POSIX di sort ):

    • "${a_in[@]}" espande in modo sicuro agli elementi dell'array a_in come singoli argomenti , qualunque cosa contengano (compresi gli spazi bianchi).

    • printf '%s\n' quindi stampa ogni argomento, cioè ogni elemento dell'array, sulla propria linea, così com'è.

  • Notare l' uso di una sostituzione di processo ( <(...) ) per fornire l'output ordinato come input a read / readarray (tramite reindirizzamento a stdin, < ), poiché read / readarray deve essere eseguito nella shell corrente (non deve essere eseguito in una subshell ) affinché la variabile di output a_out sia visibile alla shell corrente (affinché la variabile rimanga definita nel resto dello script).

  • Lettura dell'output sort in una variabile array :

    • Bash v4 +: readarray -t a_out legge le singole righe in output per sort negli elementi della variabile di matrice a_out , senza includere il trailing \n in ogni elemento ( -t ).

    • Bash v3: readarray non esiste, quindi deve essere read :
      IFS=$'\n' read -d '' -r -a a_out indica read to read alla variabile array ( -a ) a_out , leggendo l'intero input, attraverso le righe ( -d '' ), ma suddividendolo in elementi array by newlines ( IFS=$'\n' . $'\n' , che produce una letterale newline (LF), è una cosiddetta stringa quotata ANSI C ).
      ( -r , un'opzione che dovrebbe essere sempre utilizzata con read , disabilita la gestione inaspettata di \ caratteri.)

Codice di esempio annotato:

 #!/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=( 'ac' bf 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[@]}" 

A causa dell'uso di sort senza opzioni, questo produce l' ordinamento lessicale (le cifre vengono ordinate prima delle lettere e le sequenze di cifre vengono trattate in modo lessicale, non come numeri):

 * 10 5 ac b f 

Se si desidera l' ordinamento numerico per il 1 ° campo, si utilizzerà sort -k1,1n anziché solo sort , che produce (ordinamento non numerico prima dei numeri e numeri ordinati correttamente):

 * ac b f 5 10 

[1] Per gestire elementi con nuove linee incorporate, utilizzare la seguente variante (Bash v4 +, con sort GNU ):
readarray -d '' -t a_out < <(printf '%s\0' "${a_in[@]}" | sort -z) .
La risposta utile di Michał Górny ha una soluzione Bash v3.

[2] Mentre IFS è impostato nella variante Bash v3, la modifica viene portata al comando .
Al contrario, ciò che segue IFS=$'\n' nella risposta di antak è un'assegnazione piuttosto che un comando, nel qual caso la modifica IFS è globale .

Un’altra soluzione che utilizza l’ sort esterno e gestisce qualsiasi carattere speciale (ad eccezione di NUL :). Dovrebbe funzionare con bash-3.2 e GNU o BSD sort (purtroppo POSIX non include -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) 

Guarda prima il reindirizzamento dell'input alla fine. Stiamo usando printf integrato per scrivere gli elementi dell'array, terminati a zero. Il quoting fa in modo che gli elementi dell'array vengano passati così com'è, e le specifiche della shell printf lo fanno riutilizzare l'ultima parte della stringa di formato per ogni parametro rimanente. Cioè, è equivalente a qualcosa come:

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

L'elenco di elementi con terminazione null viene quindi passato per sort . L'opzione -z fa in modo che legga gli elementi con terminazione null, li ordina e li restituisce anche con terminazione null. Se hai bisogno di ottenere solo gli elementi unici, puoi passare -u dato che è più portatile di uniq -z . LC_ALL=C garantisce un ordinamento stabile indipendentemente dalle impostazioni locali, a volte utile per gli script. Se vuoi che l' sort rispetti le impostazioni locali, rimuovilo.

Il costrutto <() ottiene il descrittore da leggere dalla pipeline generata e < reindirizza lo standard input del ciclo while ad esso. Se è necessario accedere allo standard input all'interno della pipe, è ansible utilizzare un altro descrittore - exercise for the reader :).

Ora, torniamo all'inizio. Il read incorporato viene emesso dallo stdin reindirizzato. L'impostazione di IFS vuoto disabilita la divisione delle parole che non è necessaria qui - di conseguenza, legge l'intera "linea" di input alla variabile singola fornita. -r opzione -r disabilita anche l'elaborazione di escape indesiderata. Infine, -d '' imposta il delimitatore di riga su NUL, ovvero dice read per leggere stringhe con terminazione zero.

Di conseguenza, il ciclo viene eseguito una volta per ogni elemento di matrice a terminazione zero successivo, con il valore memorizzato in e . L'esempio mette gli oggetti in un altro array ma potresti preferirli processarli direttamente :).

Naturalmente, questo è solo uno dei tanti modi per raggiungere lo stesso objective. A mio avviso, è più semplice implementare l'algoritmo di ordinamento completo in bash e in alcuni casi sarà più veloce. Gestisce tutti i caratteri speciali inclusi i newline e dovrebbe funzionare sulla maggior parte dei sistemi comuni. Soprattutto, potrebbe insegnarti qualcosa di nuovo e fantastico su bash :).

prova questo:

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

L’output sarà:

 3
 5
 un
 B
 c
 f

Problema risolto.

Se è ansible calcolare un intero univoco per ogni elemento dell’array, in questo modo:

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

quindi, puoi usare questi numeri interi come indici di array, perché Bash usa sempre array sparsi, quindi non devi preoccuparti di indici inutilizzati:

 array=(acbf 3 5) for el in "${array[@]}"; do sexy_int "$el" sorted[$?]="$el" done echo "${sorted[@]}" 
  • Professionisti. Veloce.
  • Cons. Gli elementi duplicati vengono uniti e può essere imansible mappare il contenuto a numeri interi univoci a 32 bit.
 array=(acbf 3 5) new_array=($(echo "${array[@]}" | sed 's/ /\n/g' | sort)) echo ${new_array[@]} 

i contenuti di echo di new_array saranno:

 3 5 abcf 

min tipo:

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

Non sono convinto che avrai bisogno di un programma di ordinamento esterno in Bash.

Ecco la mia implementazione per il semplice algoritmo bubble-sort.

 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=(acbf 3 5) echo " input: ${array[@]}" echo "output: $(bubble_sort ${array[@]})" 

Questo deve stampare:

  input: acbf 3 5 output: 3 5 abcf 
 a=(eb 'c d') shuf -e "${a[@]}" | sort >/tmp/f mapfile -tg  

C’è una soluzione alternativa al solito problema di spazi e nuove righe:

Usa un personaggio che non è nell’array originale (come $'\1' o $'\4' o simili).

Questa funzione ha il compito di:

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

Questo ordinerà l’array:

 $ array=( ab 'cd' $'e\nf' $'g\1h') $ sortarray "${array[@]}" $ printf '<%s>\n' "${sorted[@]}"      

Questo si lamenterà che l’array sorgente contiene il carattere di soluzione alternativa:

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

descrizione

  • Impostiamo due variabili locali wa (workaround char) e un IFS null
  • Quindi (con ifs null) testiamo l’intero array $* .
  • Non contiene alcun carattere di woraround [[ $* =~ [$wa] ]] .
  • Se lo fa, solleva un messaggio e segnala un errore: exit 1
  • Evita le espansioni dei nomi dei file: set -f
  • Imposta un nuovo valore di IFS ( IFS=$'\n' ) una variabile di ciclo x e una nuova riga var ( nl=$'\n' ).
  • Stampiamo tutti i valori degli argomenti ricevuti (la matrice di input [email protected] ).
  • ma sostituiamo qualsiasi nuova riga con il carattere "${@//$nl/$wa}" .
  • invia quei valori da ordinare sort -n .
  • e posiziona tutti i valori ordinati negli argomenti posizionali set -- .
  • Quindi assegniamo ogni argomento uno per uno (per preservare le nuove linee).
  • in un ciclo for x
  • in un nuovo array: sorted+=(…)
  • all’interno di virgolette per preservare qualsiasi newline esistente.
  • ripristinare la soluzione alternativa a una nuova riga "${x//$wa/$nl}" .
  • fatto

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

Nello spirito di bash / linux, potrei usare il migliore strumento da riga di comando per ogni passaggio. sort il lavoro principale ma ha bisogno di input separati da newline invece di spazio, quindi la semplicissima pipeline sopra fa semplicemente:

Contenuto dell’array Echo -> sostituisci lo spazio con newline -> ordina

$() è per echeggiare il risultato

($()) significa mettere il “risultato echo” in una matrice

Nota : come @sorontar menzionato in un commento a un’altra domanda:

La parte ordinata = ($ (…) utilizza l’operatore “split and glob”. Dovresti distriggersre glob: set -f o set -o noglob o shopt -op noglob o un elemento dell’array come * verrà espanso in un elenco di file.