Function doesn’t update global array

Question

I wrote a simple quick sort algorithm. When I run it, it echoes the same array back.

#!/usr/bin/bash
arr=(1 8 3 9 4 5 7 2)
partition() {
 local low=1ドル
 local high=2ドル
 local pivot=${arr[low]}
 local i=$((low - 1))
 local j=$((high + 1))
 local temp
 while true; do
 ((i++))
 while ((arr[i] < pivot && i <= high)); do
 ((i++))
 done
 ((j--))
 while ((arr[j] > pivot && j >= 0)); do
 ((j--))
 done
 if ((i >= j)); then
 echo "$j"
 return
 fi
 temp=${arr[i]}
 arr[i]=${arr[j]}
 arr[j]=$temp
 done
}
quick_sort() {
 local low=1ドル
 local high=2ドル
 if ((low >= high)); then
 return
 fi
 
 local pivot
 pivot=$(partition "$low" "$high")
 quick_sort "$low" "$pivot"
 quick_sort $((pivot + 1)) "$high"
}
quick_sort 0 $((${#arr[@]} - 1))
echo "Sorted array: ${arr[*]}"

Output:

Sorted array: 1 8 3 9 4 5 7 2

I am on Windows so i tried it on git-bash and an online bash shell, the outcome was still the same

• Kamran: Your array is not being updated because pivot=$(partition ...) runs partition in a subshell. Any changes to arr inside that subshell are lost when it returns, which is why the array looks unchanged. To fix this issue, call partition directly so it mutates the global array, and only return the pivot index (writing it into REPLY or a global variable). Just for exxample: ` partition() { ... REPLY=$j; return; } partition "$low" "$high" pivot=$REPLY ` That way the swaps in partition persist and your quick sort works.
• Hi Byee: @KamranKhalid It worked, thank you so much

Answer 1

This line runs partition in a subshell.

pivot=$(partition "$low" "$high")

Variables aren't propagated from a subshell back to the parent shell.

You can insert

set -xv

at the beginning of the script to see what exactly the shell sees and executes.

• Barmar: This answer would be improved if it explained how to solve the problem, rather than just giving the reason why it fails.

Answer 2

Your function is running in the subshell created by $(...) and so cannot change the value of a variable in the shell it's called from. Here's an example of the problem:

$ cat tst.sh
#!/usr/bin/env bash
var=9
foo() {
 var=12
 echo '27'
}
ret=$(foo)
declare -p ret >&2
declare -p var >&2

$ ./tst.sh
declare -- ret="27"
declare -- var="9"

Note that var didn't retain its modified value (12) in the calling shell after foo() returned.

If you can modify foo() then you can get around this problem by creating a nameref variable that refers to ret so you don't need to call foo() in a subshell to populate ret with it's output:

$ cat tst0.sh
#!/usr/bin/env bash
var=9
foo() {
 local -n loc_ret="1ドル"
 var=12
 loc_ret=27
}
foo ret
declare -p ret >&2
declare -p var >&2

$ ./tst0.sh
declare -- ret="27"
declare -- var="12"

If you cannot modify foo() then here's a solution using a coprocess which doesn't require you to modify the function foo():

$ cat tst1.sh
#!/usr/bin/env bash
var=9
foo() {
 var=12
 echo '27'
}
coproc CAT { cat; }
foo >&${CAT[1]}
IFS= read -r ret <&${CAT[0]}
declare -p ret >&2
declare -p var >&2

$ ./tst1.sh
declare -- ret="27"
declare -- var="12"

In the last script above foo() is being run in the current shell instead of in a subshell and it's output is written to the coprocess we created named CAT, then we read its output back into the variable ret. With this approach var does retain its updated value in the calling shell after foo() returns.

You could, of course, use a temp file instead of a coprocess if you prefer:

$ cat tst2.sh
#!/usr/bin/env bash
var=9
foo() {
 var=12
 echo '27'
}
tmp=$(mktemp) || exit 1
trap 'rm -f "$tmp"; exit' EXIT
foo >"$tmp"
IFS= read -r ret <"$tmp"
declare -p ret >&2
declare -p var >&2

$ ./tst2.sh
declare -- ret="27"
declare -- var="12"