Recursive function and arrays

Shell Programming and Scripting
1

I have the following function in a bash script that fails to return the sorted array. I think the problem lies in the recursion not correctly passing the arrays, but I can't tell what I'm doing wrong. Anyone see the problem?

function quicksort () {
    local array=( `echo "$1"` )
    local -a l
    local -a g
    local x=
    if [ ${#array[@]} -lt 2 ]; then
        echo ${array[@]}
    else
      local pivot=${array[0]}
      for x in ${array[@]}; do
          echo "$x, $pivot"
          if [ $x -lt $pivot ]; then
              l=( ${l[@]} $x )
          else 
              g=( ${g[@]} $x )
          fi
      done
      echo `quicksort "$l"` $pivot `quicksort "$g"`
    fi
}
2

The POSIX syntax for defining functions is quicksort() <compound command>.

The ksh syntax is function quicksort <compound command>.

What you are using is a hybrid that works only in bash (and, I think perhaps in zsh).

What do you expect in $1? Why are you using echo?

3

Yes, I'm using bash. I tried the POSIX version as well, to see if it made any difference.

$1 should contain the array passed to the function. I found this method searching the web. Is there a better method?

I suspect the problem may be related to this since when it descends to the first recursion level, the array length is seen as 1 and the function exits, returning only three numbers from the array. A check of $l and $g just prior to passing them to the recursive call shows them as they should be, so I'm not sure what the problem is.

4

It will only make a difference if you try to use the script in a different shell.

What do you mean by "the array"? Do you mean the name of the array? The elements of the array?

There's a lot of nonsense on the web.

If you want to pass the name of the array and then populate array with its elements, use:

local -a array
eval "array=( \"\${$1[@]}\" )"
5

True enough.

The elements. I tried the code you suggested and I get a "bad substitution" error. The original one I used does populate the "array" variable correctly, however. At least on the first pass.

6

That is the same as:

local array=( $1 )

...but much slower. Command substitution is slow.

Here you are not passing the entire array; "$l" or "$g" is only the first element of the array. To pass the full array:

echo `quicksort "${l[*]}"` $pivot `quicksort "${g[*]}"`
7

I figured it out.
I had a logic error in the partitioning loop that would send one of the branches into an endless loop. :o\ Using '*' instead of '@' worked also, although I don't fully understand why yet. Here's my final code and thanks for all your help. I learned a lot, which was the point after all.

quicksort () {
	local -a array=( $1 )
	local -a l
	local -a g
	if [ ${#array[@]} -lt 2 ]; then
		echo ${array[@]}
	else
	  pivot=${array[0]}
	  for x in ${array[@]}; do
		  if [ $x -lt $pivot ]; then
			  l=( ${l[@]} $x )
		  elif [ $x -gt $pivot ]; then
			  g=( ${g[@]} $x )
		  fi
	  done
	  echo `quicksort "${l[*]}"` $pivot `quicksort "${g[*]}"`
	fi
}
8 
printf "%s\n" "${array[*]}"  ## array expands to a single argument
printf "%s\n" "${array[@]}"  ## each element in the array is a separate argument